Convex Optimization

Convergence of infeasible-interior-point methods for self-scaled conic programming

  • Bharath Kumar Rangarajan
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) … Read more

    Lift-and-project for 0–1 programming via algebraic geometry

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories 0-1 Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Recently, tools from algebraic geometry have been successfully applied to develop solution schemes for new classes of optimization problems. A central idea in these constructions is to express a polynomial that is positive on a given domain in terms of polynomials of higher degree so that its positivity is readily revealed. This resembles the “lifting” … Read more

    The Reduced Density Matrix Method for Electronic Structure Calculations and the Role of Three-Index Representability Conditions

  • Bastiaan J. Braams
  • Mituhiro Fukuda
  • Michael L. Overton
  • Jerome K. Percus
  • Zhengji Zhao
    • Categories Basic Sciences Applications, Convex Optimization, Semi-definite Programming Tags

    The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more

    A Pivotting Procedure for a Class of Second-Order Cone Programming

  • Masakazu Muramatsu
    • Categories Convex Optimization, Second-Order Cone Programming Tags , , ,

    We propose a pivotting procedure for a class of Second-Order Cone Programming (SOCP) having one second-order cone. We introduce a dictionary, basic variables, nonbasic variables, and other necessary notions to define a pivot for the class of SOCP. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering to or … Read more

    The structured distance to ill-posedness for conic systems

  • Adrian Lewis
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a … Read more

    On the block-structured distance to non-surjectivity of sublinear mappings

  • Javier F. Peña
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , ,

    We show that the block-structured distance to non-surjectivity of a set-valued sublinear mapping equals the reciprocal of a suitable block-structured norm of its inverse. This gives a natural generalization of the classical Eckart and Young identity for square invertible matrices. Citation Mathematical Programming 103 (2005) pp. 561–573.

    Double-Regularization Proximal Methods, with Complementarity Applications

  • Jonathan Eckstein
  • Paulo J. S. Silva
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We consider the variational inequality problem formed by a general set-valued maximal monotone operator and a possibly unbounded “box” in $R^n$, and study its solution by proximal methods whose distance regularizations are coercive over the box. We prove convergence for a class of double regularizations generalizing a previously-proposed class of Auslender et al. We apply … Read more

    Convergence of string-averaging projection schemes for inconsistent convex feasibility problems

  • Yair Censor
  • Eli Tom
    • Categories Convex Optimization

    We study iterative projection algorithms for the convex feasibility problem of finding a point in the intersection of finitely many nonempty, closed and convex subsets in the Euclidean space. We propose (without proof) an algorithmic scheme which generalizes both the string-averaging algorithm and the block-iterative projections (BIP) method with fixed blocks and prove convergence of … Read more

    Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming

  • Levent Tunçel
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more

    Finding the projection of a point onto the intersection of convex sets via projections onto halfspaces

  • L.M. Bregman
  • Yair Censor
  • Simeon Reich
  • Y. Zepkowitz-Malachi
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    We present a modification of Dykstra’s algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a halfspace or onto the intersection of two halfspaces. Convergence of the algorithm is established and special choices of the halfspaces are proposed. The option to project onto halfspaces instead of general … Read more