On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellens\”atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\”udgen) that certify positivity of a polynomial on an … Read more

Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations

It is well-known that any sum of squares (SOS) program can be cast as a semidefinite program (SDP) of a particular structure and that therein lies the computational bottleneck for SOS programs, as the SDPs generated by this procedure are large and costly to solve when the polynomials involved in the SOS programs have a … Read more

Minimizer extraction in polynomial optimization is robust

In this article we present a robustness analysis of the extraction of optimizers in polynomial optimization. Optimizers can be extracted by solving moment problems using flatness and the Gelfand-Naimark-Segal (GNS) construction. Here a modification of the GNS construction is presented that applies even to non-flat data, and then its sensitivity under perturbations is studied. The … Read more

Tightness of a new and enhanced semidefinite relaxation for MIMO detection

In this paper, we consider a fundamental problem in modern digital communications known as multi-input multi-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite relaxation (SDR) based algorithms have been proposed to solve the problem in the literature. In this paper, we … Read more

Robust Sensitivity Analysis for Linear Programming with Ellipsoidal Perturbation

Given an originally robust optimal decision and allowing perturbation parameters of the linear programming problem to run through a maximum uncertainty set controlled by a variable of perturbation radius, we do robust sensitivity analysis for the robust linear programming problem in two scenarios. One is to keep the original decision still robust optimal, the other … Read more

Maintaining a Basis Matrix in the Linear Programming Interior Point Method

To precondition the normal equation system from the linear programming (LP) interior point method, basis preconditioners choose a basis matrix dependent on column scaling factors. Two criteria for choosing the basis matrix are compared which yield a maximum volume or maximum weight basis. Finding a maximum volume basis requires a combinatorial effort, but it gives … Read more

Worst-case convergence analysis of gradient and Newton methods through semidefinite programming performance estimation

We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton’s method for self-concordant functions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori en Teboulle [Mathematical Programming, 145(1-2):451–482, 2014], and extends recent performance estimation results for the method of … Read more

Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions

We consider the stability of a class of parameterized conic programming problems which are more general than the C2-smooth parameterization. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order sucient condition (named as Jacobian uniqueness conditions here) are satis ed at a feasible point of … Read more

Perturbation analysis of nonlinear semidefinite programming under Jacobian uniqueness conditions

We consider the stability of a class of parameterized nonlinear semidefinite programming problems whose objective function and constraint mapping all have second partial derivatives only with respect to the decision variable which are jointly continuous. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order … Read more

Exploiting sparsity for the min k-partition problem

The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more