This paper proposes a bilevel hierarchy of strengthened complex moment relaxations for complex polynomial optimization. The key trick entails considering a class of positive semidefinite conditions that arise naturally in characterizing the normality of the so-called shift operators. The relaxation problem in this new hierarchy is parameterized by the usual relaxation order as well as … Read more
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for instances with n nodes, where n is small. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ($P^{n}_{ASEP}$) and its vertices. The … Read more
We propose an inexact infeasible arc-search interior-point method for solving linear optimization problems. The method combines an arc-search strategy with inexact solutions to Newton systems and admits a polynomial iteration complexity bound. In existing inexact infeasible interior-point methods, both the linearization error of the central path and the inexactness of the Newton system accumulate along … Read more
Data Collaboration (DC) enables multiple parties to jointly train a model by sharing only linear projections of their private datasets. The core challenge in DC is to align the bases of these projections without revealing each party’s secret basis. While existing theory suggests that any target basis spanning the common subspace should suffice, in practice, … Read more
We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations are … Read more
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more
This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize sequences, … Read more
We study T-semidefinite programming (SDP) relaxation for constrained polynomial optimization problems (POPs). T-SDP relaxation for unconstrained POPs was introduced by Zheng, Huang and Hu in 2022. In this work, we propose a T-SDP relaxation for POPs with polynomial inequality constraints and show that the resulting T-SDP relaxation formulated with third-order tensors can be transformed into … Read more
We present a linear cutting-plane relaxation approach that rapidly proves tight lower bounds for the Alternating Current Optimal Power Flow Problem (ACOPF). Our method leverages outer-envelope linear cuts for well-known second-order cone relaxations for ACOPF along with modern cut management techniques. These techniques prove effective on a broad family of ACOPF instances, including the largest … Read more
We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices \(xx^{\mathrm{H}}\), where the elements of \(x \in \mathbb{C}^n\) are \(m\)th unit roots. These polytopes have applications in \({\text{MAX-3-CUT}}\), digital communication technology, angular synchronization and more generally, complex quadratic programming. For \({m=2}\), the complex cut polytope corresponds to the well-known cut polytope. … Read more