1 — 16:20 — On randomly signed sums of vectors
A randomly signed sum of vectors is a random variable of the form
2 — 16:50 — Reducing Sum-of-Squares constraints over a domain
Numerous applications require verifying the nonnegativity of a polynomial over a set defined by polynomial equalities and inequalities. A classical approach is to search for multipliers that would constitute a Sum-of-Squares certificate of the nonnegativity. While this corresponds to a hierarchy of convex programs, the size of these programs grows rapidly with the total degree of the multipliers. If a Gröbner basis for the ideal generated by the equalities is known, it would allow to drastically reduce the size of the program to solve. Such basis is however NP-hard to compute. Using information from the null space of a Macaulay matrix, we show how to reduce the size of the programs for any degree. While the program size converges to the size that would be obtained by the Gröbner basis approach, our approach does not need Gröbner basis to be computed and is therefore not limited to small size problems. Furthermore, we show how to also compute reduced gram bases for the multipliers associated to the inequalities by exploiting both properties of a Macaulay null space and Newton polytopes. We show applications of these results to the analysis of descriptor systems.
3 — 17:20 — Approximate Karush-Kuhn-Tucker 2 conditions for nonlinear second-order cone optimization problems
The sequential optimality conditions, which improve algorithm convergence assumptions, have been studied over the past two decades. In particular, by considering the second-order information, the so-called approximate Karush-Kuhn-Tucker 2 (AKKT2) conditions for nonlinear programming problems were also proposed. While studies on a more general conic problem have been conducted, an explicit definition for AKKT2 has not been proposed in the literature. This work addresses this gap by providing a precise definition of AKKT2 conditions for second-order cone programming problems. We prove that the proposed AKKT2 conditions hold at local optimal points, without any constraint qualifications. Moreover, we show two algorithms based on augmented Lagrangian and sequential quadratic programming approaches that generate points satisfying these conditions.