linear programming

Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

  • Guanghui Lan
  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more

    Exact regularization of convex programs

  • Michael P. Friedlander
  • Paul Tseng
    • Categories Convex Optimization Tags , , , , , , , ,

    The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

    A Simpler and Tighter Redundant Klee-Minty Construction

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler … Read more

    Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP

  • Sunyoung Kim
  • Masakazu Kojima
  • Kazuhiro Kobayashi
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient … Read more

    Central path curvature and iteration-complexity for redundant Klee-Minty cubes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more

    Implementation of Warm-Start Strategies in Interior-Point Methods for Linear Programming in Fixed Dimension

  • Elizabeth John
  • E. Alper Yildirim
    • Categories Linear Programming Tags , , ,

    We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify … Read more

    Representing the space of linear programs as a Grassmannian

  • Gongyun Zhao
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We represent the space of linear programs as the space of projection matrices. Projection matrices of the same dimension and rank comprise a Grassmannian, which has rich geometric and algebraic structures. An ordinary differential equation on the space of projection matrices defines a path for each projection matrix associated with a linear programming instance and … Read more

    Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

  • Raphael Hauser
  • Tobias Muller
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

    Dynamic Enumeration of All Mixed Cells

  • Masakazu Kojima
  • Tomohiko Mizutani
  • Akiko Takeda
    • Categories 0-1 Programming, Branch and Cut Algorithms, Polyhedra Tags , , , ,

    The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more

    Exact regularization of linear programs

  • Michael P. Friedlander
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We show that linear programs (LPs) admit regularizations that either contract the original (primal) solution set or leave it unchanged. Any regularization function that is convex and has compact level sets is allowed–differentiability is not required. This is an extension of the result first described by Mangasarian and Meyer (SIAM J. Control Optim., 17(6), pp. … Read more