114:00 — Extensions of constant rank qualification constraint condition to nonlinear conic programming

We present new constraint qualification conditions for nonlinear conic programming that extend some of the constant rank-type conditions from nonlinear programming. Specifically, we propose a general and geometric approach, based on the study of the faces of the cone, for defining a new extension of this condition to the conic context. We then compare these new conditions with some of the existing ones, including the nondegeneracy condition, Robinson’s constraint qualification, and the metric subregularity constraint qualification. The main advantage of the latter is that we are able to recast the strong second-order properties of the constant rank condition in a conic context. In particular, we obtain a second-order necessary optimality condition that is stronger than the classical one obtained under Robinson’s constraint qualification, in the sense that it holds for every Lagrange multiplier, even though our condition is independent of Robinson’s condition.

214:30 — Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity

We consider the problem of learning local quantum Hamiltonians given copies of their Gibbs state at a known inverse temperature, following Haah et al. [2108.04842] and Bakshi et al. [arXiv:2310.02243]. Our main technical contribution is a new flat polynomial approximation of the exponential function based on the Chebyshev expansion, which enables the formulation of learning quantum Hamiltonians as a polynomial optimization problem. This, in turn, can benefit from the use of moment/SOS relaxations, whose polynomial bit complexity requires careful analysis [O'Donnell, ITCS 2017]. Finally, we show that learning a k-local Hamiltonian, whose dual interaction graph is of bounded degree, runs in polynomial time under mild assumptions.

315:00 — Time-varying semidefinite programming: path-following a Burer-Monteiro factorization

We present an online algorithm for time-varying semidefinite programs (TV-SDPs), based on the tracking of the solution trajectory of a low-rank matrix factorization, also known as the Burer-Monteiro factorization, in a path-following procedure. There, a path-following algorithm solves a sequence of linearized systems. This requires the introduction of a horizontal space constraint to ensure the local injectivity of the low-rank factorization. The method produces a sequence of approximate solutions for the original TV-SDP problem, for which we show that they stay close to the optimal solution path if properly initialized. Numerical experiments for a time-varying max-cut SDP relaxation demonstrate the computational advantages of the proposed method for tracking TV-SDPs in terms of runtime compared to off-the-shelf interior point methods.

415:30 — Time-varying semidefinite programming: geometry of the trajectory of solutions

In many applications, solutions of convex optimization problems need to be updated on-line, in response to time-varying inputs. We study behaviours of the solution trajectory, defined as the set of solutions depending on the time parameter. First, we consider parametric semidefinite programs, which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on a time parameter. As our main result, we show that only six distinct behaviors can be observed at a neighborhood of a given point along the solution trajectory. Each possible behavior is illustrated by an example. Second, we mention extensions to other time-varying conic optimization problems, including linear programming and polynomial optimization, and applications in transmission-constrained problems in power systems.