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.
[04074] Some Recent Developments on Solving Variational Inequality Problems
Format : Talk at Waseda University
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.
[05227] Monotone Variational Inequality (VI) for estimation and learning
Format : Talk at Waseda University
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.
[04577] Implementation of Interior Point Method for Nonlinear Programming for Real-life Applications.
Format : Talk at Waseda University
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
Format : Talk at Waseda University
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.
[04479] Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
Format : Talk at Waseda University
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.
[03172] Computational challenges in Flag Algebra proofs
Format : Talk at Waseda University
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.
[03673] Improving Lower Bounds for Large Scale QAPs
Format : Talk at Waseda University
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
Format : Talk at Waseda University
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.
[04092] Maximum-Entropy Sampling: Algorithms and Application
Format : Talk at Waseda University
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.
[03117] A role of semidefinite relaxation in mathematics of phase retrieval
Format : Talk at Waseda University
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.
[03176] Exact Convergence Rate of Alternating Projections
Format : Talk at Waseda University
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.
[05522] Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds
Format : Talk at Waseda University
Author(s) :
Zhiquan Luo
Zhi-Quan Luo (The Chinese University of Hong Kong, Shenzhen)
Abstract : Risk-sensitive decision-making is vital in high-stakes fields like finance and medicine. Risk-sensitive reinforcement learning maximizes a risk measure instead of expected return. The exponential risk measure is widely used but involves complex algorithms and regret analysis. We propose a novel distributional reinforcement learning (DRL) algorithm for RSRL with a regret guarantee. Our approach utilizes risk-sensitive distributional dynamic programming and provides a regret upper bound via distributional optimism, while fixing and tightening the minimax lower bound.
