Session: Advances in Semidefinite Programming: Relaxations, Hierarchies, and Optimization Techniques
Chair: Makoto Yamashita & Sunyoung Kim
Cluster: Conic and Semidefinite Optimization
Talk 1: Well-conditioned primal-dual interior-point method for accurate low-rank semidefinite programming
Speaker: Hong-Ming Chiu
Abstract: We describe how the low-rank structure in an SDP can be exploited to reduce the per-iteration cost of a convex primal-dual interior-point method down to cubic time and quadratic memory, even at very high accuracies. A traditional difficulty is the dense Newton subproblem at each iteration, which becomes progressively ill-conditioned as progress is made towards the solution. Preconditioners have previously been proposed to improve conditioning, but these can be expensive to set up, and become ineffective as the preconditioner itself becomes increasingly ill-conditioned at high accuracies. Instead, we present a well-conditioned reformulation of the Newton subproblem that is cheap to set up, and whose condition number is guaranteed to remain bounded over all iterations. In theory, applying an inner iterative method to the reformulation reduces the per-iteration cost of the outer interior-point method to cubic time and quadratic memory. We also present a well-conditioned preconditioner that greatly improves the convergence of the inner iterations.
Talk 2: Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints
Speaker: Sunyoung Kim
Abstract: We study exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi- infinite QCQPs). Specifically, we present two sufficient conditions on the feasible region under which the QCQP, with any quadratic objective function over the feasible region, is equivalent to its SDP relaxation. The first condition is an extension of a result recently proposed by the authors (arXiv:2308.05922, to appear in SIAM J. Optim.) from finitely constrained quadratic programs to semi-infinite QCQPs. The newly introduced second condition offers a clear geometric characterization of the feasible region for a broad class of QCQPs that are equivalent to their SDP relaxations. Several illustrative examples, including quadratic programs with ball-, parabola-, and hyperbola-based constraints, are also provided.
Talk 3: Semidefinite Programming Relaxation Hierarchy Using Third-Order Tensors for Constrained Polynomial Optimization
Speaker: Makoto Yamashita
Abstract: Exploiting the computational structure of third-order tensors, Zheng et al. (2022) proposed a semidefinite programming (SDP) hierarchy of relaxations for unconstrained polynomial optimization problems (POPs). We extend this by employing the Lagrange function to propose a hierarchy of SDP relaxation for constrained polynomial optimization problems involving third-order tensors. This relaxation can be computationally efficient, as it can be transformed into an SDP problem with a block diagonal matrix structure via the discrete Fourier transformation. Additionally, we show under a mild assumption, the objective value of the hierarchy converges to the optimal value of the POP as the degree of relaxation increases.
