# Registered Data

## [02440] Advances in Optimization I

**Session Date & Time**:- 02440 (1/3) : 2D (Aug.22, 15:30-17:10)
- 02440 (2/3) : 2E (Aug.22, 17:40-19:20)
- 02440 (3/3) : 3C (Aug.23, 13:20-15:00)

**Type**: Proposal of Minisymposium**Abstract**: The two minisymposia on Advances in Optimization I and II will bring together a diverse group of leading researchers and practitioners from both continuous and combinatorial optimization, theoretical and applied. One of the goals of these two minisymposia is to raise awareness to the most recent advances in optimization theory, algorithms, and applications, and to develop connections and encourage collaboration.**Organizer(s)**: Antoine Deza, Takashi Tsuchiya**Classification**:__90Cxx__,__49Mxx__,__65Kxx__,__52Bxx__,__52Cxx__**Speakers Info**:- Koichi Fujii (NTT DATA Mathematical Systems Inc.)
- Stephane Gaubert (INRIA and Ecole polytechnique)
- Jon Lee (University of Michigan)
- Zhi-Quan Luo (The Chinese University of Hong Kong, Shenzhen)
- Bento Natura (Georgia Tech)
- Yoshiyuki Sekiguchi (Tokyo University of Marine Science and Technology)
- Christoph Spiegel (Zuse Institute Berlin)
- Takahito Tanabe (NTTDATA Mathematical Systems Inc.)
- Ryoko Oishi-Tomiyasu (Kyushu University)
**Takashi Tsuchiya**(National Graduate Institute for Policy Studies)- Shuzhong Zhang (University of Minnesota)
- Yong Zhang (Huawei)

**Talks in Minisymposium**:**[03117] A role of semidefinite relaxation in mathematics of phase retrieval****Author(s)**:**Ryoko Oishi-Tomiyasu**(Kyushu University)

**Abstract**: In phase retrieval, a signal x is recovered from the amplitude |Ax| for a fixed linear operation A such as the Fourier transform. In crystallography, $x$ is a sum of finitely many Gaussian-like functions that represents the periodic discrete structure of atoms. We introduce that semidefinite relaxation works to determine the uniqueness of solutions and gain all the global solutions in this type of problem, mentioning an application found in a joint work with scientists.

**[03172] Computational challenges in Flag Algebra proofs****Author(s)**:- Aldo Kiem (Zuse Institute Berlin)
- Sebastian Pokutta (ZIB / TUB)
**Christoph Spiegel**(Zuse Institute Berlin)

**Abstract**: Introduced by Razborov in 2007, flag algebras are a potent tool for computer-assisted proofs in extremal combinatorics. They combine first-order logic, model theory, and semidefinite programming to tackle classical Turán and Ramsey theory problems. This talk explores computational challenges, symmetry exploitation, and optimization ideas to broaden the method's scope. We'll demonstrate its practical application by determining the 4-color Ramsey multiplicity of triangles.

**[03176] Exact Convergence Rate of Alternating Projections****Author(s)**:**Yoshiyuki Sekiguchi**(Tokyo University of Marine Science and Technology)- Hiroyuki Ochiai (Kyushu University)
- Hayato Waki (Kyushu University)

**Abstract**: We investigate the exact convergence rate of alternating projections for the nontransversal intersection of $S^n_+$ and an affine space. When the affine space is a line, we analyze the Newton polygon associated with the characteristic polynomial of the parametrizing matrix of the line and show that the convergence rate can be estimated by comparing ranks of submatrices of the basis matrix. We also investigate alternating projections for $S^3_+$ and a three dimensional affine space.

**[03673] Improving Lower Bounds for Large Scale QAPs****Author(s)**:**Koichi Fujii**(tokyo institute of technology)

**Abstract**: We report our progress on the project for solving large scale quadratic assignment problems (QAPs). Our main approach to solve QAPs is a parallel branch-and-bound method using the Ubiquity Generator framework (UG), utilizing Newton-bracketing method to solve doubly nonnegative cone (DNN) relaxations. In this talk, we present some preliminary numerical results of DNN-based branch-and-bound method and report the result that we have succeeded to update the lower bounds of instances in QAPLIB.

**[03941] Closing Nonzero Duality Gaps in SDPs through Perturbations****Author(s)**:**Takashi Tsuchiya**(National Graduate Institute for Policy Studies)- Bruno Lourenço (Institute of Statistical Mathematics)
- Masakazu Muramatsu (The University of Electro-Communication)
- Takayuki Okuno (Seikei University)

**Abstract**: Consider a primal-dual pair of SDP with nonzero duality gap. There are arbitrary small perturbations to make the pair strongly feasible with a common primal-dual optimal value $v$, say, zeroing duality gap. $v$ is not well-defined at zero (unperturbed problem) since the primal and dual have different optimal values, but it is continuous elsewhere. We analyze properties of $v$ around zero to demonstrate a few surprising and beautiful properties and establish connections to interior-point methods.

**[04074] Some Recent Developments on Solving Variational Inequality Problems****Author(s)**:**Shuzhong Zhang**(University of Minnesota)

**Abstract**: In this talk, we will present several solution methods for solving non-monotone VI problems. As the VI formulation is generalized from the optimality condition for optimization, the results are immediately applicable to nonconvex and constrained continuous optimization. The focus is placed on the conditions of the non-monotone VI models, under which the newly designed solution algorithms would converge with guaranteed rates of convergence.

**[04092] Maximum-Entropy Sampling: Algorithms and Application****Author(s)**:**Jon Lee**(University of Michigan)- Marcia Fampa (Federal University of Rio de Janeiro)

**Abstract**: The maximum-entropy sampling problem (MESP) is to select a subset, of given size s, from a set of correlated Gaussian random variables, so as to maximize the differential entropy. MESP sits at the intersection of optimization, data science and information theory, and so it has attracted a lot of recent attention. We will give a broad overview of algorithmic work, concentrating on the many useful techniques related to various convex relaxations.

**[04479] Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs****Author(s)**:**Bento Natura**(Georgia Tech)

**Abstract**: Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. For combinatorial LP beyond directed graphs this gap between exact and high-accuracy solvers is currently quadratic. We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor.

**[04577] Implementation of Interior Point Method for Nonlinear Programming for Real-life Applications.****Author(s)**:**Takahito Tanabe**(NTTDATA Mathematical Systems Inc.)

**Abstract**: In the modeling of real-life applications, we encounter some non-linearity. In such a case, interior-point algorithm is one approach to choose because it is good at finding locally optimal solutions quickly for large-scale mildly nonlinear problems. In this talk, we discuss some implementation issues related to interior-point method that originates from non-linearity, and review some applications.

**[04650] Tropical convexity: application to linear programming and mean-payoff games****Author(s)**:**Stephane Louis Gaubert**(INRIA and Ecole polytechnique)

**Abstract**: Tropical geometry sets up a bridge between linear programming and mean-payoff games, exploiting a correspondence between generic convex semi-algebraic programs over nonarchimedean fields and different classes of zero-sum repeated games. We will discuss the application of this correspondence to the complexity analysis of interior point methods, showing in particular that no self-concordant barrier interior point method is strongly polynomial. This is based on a series of works with Allamigeon, Benchimol, Joswig and Vandame.

**[05227] Monotone Variational Inequality (VI) for estimation and learning****Author(s)**:**Yao Xie**(Georgia Institute of Technology)

**Abstract**: We propose a new computational framework for estimating parameters in generalized generalized linear models (GGLMs), inspired by Juditsky and Nemirovsky's recent work. First, we extend GLMs to spatio-temporal data by accounting for dependencies among observations while using a monotone operator-based variational inequality method. We also present online instance-based bounds using martingale concentration inequalities and apply our algorithm to wildfire and police datasets. In addition, we demonstrate our approach to training neural networks.