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
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
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
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
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
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
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
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
We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them … Read more
In this paper we study bipartite quantum correlations using techniques from tracial polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum … Read more