Linear, Cone and Semidefinite Programming

An (\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems

  • Wenbao Ai
  • Shuzhong Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more

    Solving nonconvex SDP problems of structural optimization with stability control

  • Michal Kočvara
  • Michael Stingl
    • Categories Constrained Nonlinear Optimization, Mechanical Engineering, Semi-definite Programming Tags , , ,

    The goal of this paper is to formulate and solve structural optimization problems with constraints on the global stability of the structure. The stability constraint is based on the linear buckling phenomenon. We formulate the problem as a nonconvex semidefinite programming problem and introduce an algorithm based on the Augmented Lagrangian method combined with the … Read more

    Interior Point and Semidefinite Approaches in Combinatorial Optimization

  • Kartik Krishnan
  • Tamás Terlaky
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more

    Boundedness Theorems for the Relaxation Method

  • Edoardo Amaldi
  • Raphael Hauser
    • Categories Linear Programming, Polyhedra Tags , , ,

    A classical theorem by Block and Levin says that certain variants of the relaxation method for solving systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying … Read more

    When LP is not a good idea – using structure in polyhedral optimization problems

  • Michael Osborne
    • Categories Convex Optimization, Linear Programming, Statistics Tags , , , , , , , , ,

    It has been known for almost 50 years that the discrete l_1 approximation problem can be solved effectively by linear programming. However, improved algorithms involve a step which can be interpreted as a line search, and which is not part of the standard LP solution procedures. l_1 provides the simplest example of a class of … Read more

    A New Computational Approach to Density Estimation with Semidefinite Programming

  • Tadayoshi Fushiki
  • Takashi Tsuchiya
  • Shingo Horiuchi
    • Categories Data-Mining, Semi-definite Programming, Statistics Tags , , , ,

    Density estimation is a classical and important problem in statistics. The aim of this paper is to develop a new computational approach to density estimation based on semidefinite programming (SDP), a new technology developed in optimization in the last decade. We express a density as the product of a nonnegative polynomial and a base density … Read more

    An Adaptive Self-Regular Proximity Based Large-Update IPM for LO

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best … Read more

    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

    A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Graphs and Matroids, Parallel Algorithms, Semi-definite Programming Tags , , , , ,

    A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more