Linear, Cone and Semidefinite Programming

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 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

    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

    A generalization of the Lowner-John’s ellipsoid theorem

  • Jean-Bernard Lasserre
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming

    We address the following generalization $P$ of the Lowner-John’s ellipsoid problem. Given a (non necessarily convex) compact set $K\subset R^n$ and an even integer $d, find an homogeneous polynomial $g$ of degree $d$ such that $K\subset G:=\{x:g(x)\leq1\}$ and $G$ has minimum volume among all such sets. We show that $P$ is a convex optimization problem … Read more

    Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization

  • Nicolas Gillis
  • Robert Luce
    • Categories Data-Mining, Linear Programming Tags , , , , ,

    Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, R\’e and Tropp (`Factoring nonnegative matrices with linear programs’, NIPS 2012) proposed a linear programming … Read more

    Novel update techniques for the revised simplex method

  • J. A. Julian Hall
  • Qi Huangfu
    • Categories Linear Programming

    This paper introduces three novel techniques for updating the invertible representation of the basis matrix when solving practical sparse linear programming (LP) problems using a high performance implementation of the dual revised simplex method, being of particular value when suboptimization is used. Two are variants of the product form update and the other permits multiple … Read more

    Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property

  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Semi-definite Programming Tags , , , , ,

    This paper addresses the following three topics: positive semidefinite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidefinite programming as unifying theme. Our main contribution is a sufficient condition for constructing partial psd matrices which admit a unique completion to a … Read more

    Strong duality in conic linear programming: facial reduction and extended duals

  • Gabor Pataki
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program (P) \sup { | Ax \leq_K b} in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana’s dual … Read more

    Extension of Completely Positive Cone Relaxation to Polynomial Optimization

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods … Read more

    Sparse Recovery on Euclidean Jordan Algebras

  • Lingchen Kong
  • Jie Sun
  • Jiyuan Tao
  • Naihua Xiu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We consider the sparse recovery problem on Euclidean Jordan algebra (SREJA), which includes sparse signal recovery and low-rank symmetric matrix recovery as special cases. We introduce the restricted isometry property, null space property (NSP), and $s$-goodness for linear transformations in $s$-sparse element recovery on Euclidean Jordan algebra (SREJA), all of which provide sufficient conditions for … Read more