Linear, Cone and Semidefinite Programming

On a generalization of Pólya’s and Putinar-Vasilescu’s Positivstellensätze

  • Peter J.C. Dickinson
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming

    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

    On Finding a Generalized Lowest Rank Solution to a Linear Semi-definite Feasibility Problem

  • Chee-Khian Sim
    • Categories Linear, Cone and Semidefinite Programming

    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

    Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming

  • Amitabh Basu
  • Kipp Martin
  • Christopher Thomas Ryan
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-infinite Programming Tags , , , ,

    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

    Which Nonnegative Matrices Are Slack Matrices?

  • João Gouveia
  • Volker Kaibel
  • R. Grappe
  • K. Pashkovich
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear Programming, Polyhedra Tags , , ,

    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

    A Perturbed Sums of Squares Theorem for Polynomial Optimization and its Applications

  • Masakazu Muramatsu
  • Levent Tunçel
  • Hayato Waki
    • Categories Convex Optimization, Quadratic Programming, Semi-definite Programming

    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

    An Augmented Lagrangian Method for Conic Convex Programming

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    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

    The s-Monotone Index Selection Rule for Criss-Cross Algorithms of Linear Complementarity Problems

  • Nagy Adrienn
  • Zsolt Csizmadia
  • Tibor Illés
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we introduce the s-monotone index selection rules for the well-known crisscross method for solving the linear complementarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algorithms (or polynomial complexity … Read more

    Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

  • Nagy Adrienn
  • Tibor Illés
    • Categories Linear Programming, Optimization Software Benchmark Tags , , ,

    Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more

    The Trust Region Subproblem with Non-Intersecting Linear Constraints

  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Second-Order Cone Programming Tags , , ,

    This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more