The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope can … Read more
Methods for updating the LU factors of simplex basis matrices are reviewed. An alternative derivation of the Fletcher and Matthews method is given. This leads to generalizations of their method which avoids problems with both the Bartels and Golub method and the Fletcher and Matthews method. The improvements are to both numerical stability and data … Read more
This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic n-dimensional polytope with v vertices is at least (nv)^(1/4) improving on previous lower bounds. For polygons with v vertices, we show that psd rank … Read more
In this paper we provide a generalization of two well-known positivstellensätze, namely the positivstellensatz from Pólya [Georg Pólya. Über positive darstellung von polynomen vierteljschr. In Naturforsch. Ges. Zürich, 73: 141-145, 1928] and the positivestellensatz from Putinar and Vasilescu [Mihai Putinar and Florian-Horia Vasilescu. Positive polynomials on semialgebraic sets. Comptes Rendus de l’Académie des Sciences – … Read more
In this note, we generalize the affine rank minimization problem and the vector cardinality minimization problem and show that the resulting generalized problem can be solved by solving a sequence of continuous concave minimization problems. In the case of the vector cardinality minimization problem, we show that it can be solved by solving the continuous … Read more
For linear optimization (LO) problems, we consider a curvature integral first introduced by Sonnevend et al. (1991). Our main result states that in order to establish an upper bound for the total Sonnevend curvature of the central path, it is sufficient to consider only the case when n = 2m. This also implies that the … Read more
Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. … Read more
In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verifi cation problem whose complexity is unknown. CitationApril 2013ArticleDownload View PDF
We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a Polynomial Optimization Problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by $(f^¥ast – ¥epsilon)$ and from above by $f^¥ast … Read more
We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more