linear programming

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

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

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

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

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

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

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

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

Existence of Equilibrium for Integer Allocation Problems

Categories Game Theory, Linear Programming Tags , , , ,

In this paper we show that if all agents are equipped with discrete concave production functions, then a feasible price allocation pair is a market equilibrium if and only if it solves a linear programming problem, similar to, but perhaps simpler than the one invoked in Yang (2001). Using this result, but assuming discrete concave … Read more

Further Development of Multiple Centrality Correctors for Interior Point Methods

Categories Linear Programming Tags , , ,

This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that … Read more

On warm starts for interior methods

Categories Constrained Nonlinear Optimization Tags , , ,

An appealing feature of interior methods for linear programming is that the number of iterations required to solve a problem tends to be relatively insensitive to the choice of initial point. This feature has the drawback that it is difficult to design interior methods that efficiently utilize information from an optimal solution to a “nearby” … Read more