We study $n\times n$ completely positive matrices $M$ on the boundary of the completely positive cone, namely those orthogonal to a copositive matrix $S$ which generates a quadratic form with finitely many zeroes in the standard simplex. Constructing particular instances of $S$, we are able to construct counterexamples to the famous Drew-Johnson-Loewy conjecture (1994) for … Read more
We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called infeasibility step and a few – at most three – centering steps. In this paper each iteration consists of only a infeasibility step, whereas the iteration bound improves the … Read more
We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the … Read more
We present a strongly polynomial algorithm for linear optimization problems of the form min{cx|Ax = b, x >= 0} having 0-1 vectors among their optimal solutions. The algorithm runs in time O(n^4*max\{m,log n}), where n is the number of variables and m is the number of equations. The algorithm also constructs necessary and sufficient optimality … Read more
In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional vector space endowed with an inner product, where the … Read more
Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and … Read more
We consider lift-and-project methods for combinatorial optimization problems and focus mostly on those lift-and-project methods which generate polyhedral relaxations of the convex hull of integer solutions. We introduce many new variants of Sherali–Adams and Bienstock–Zuckerberg operators. These new operators fill the spectrum of polyhedral lift-and-project operators in a way which makes all of them more … Read more
Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more
Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more
This is the “front matter” of a new open-source book on Linear Optimization. The book and associated Matlab/AMPL/Mathematica programs are freely available from: https://sites.google.com/site/jonleewebpage/home/publications/#book CitationJon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017.ArticleDownload View PDF