Linear, Cone and Semidefinite Programming

A New and Efficient Large-Update Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of … Read more

    Convex optimization problems involving finite autocorrelation sequences

  • Brien Alkire
  • Lieven Vandenberghe
    • Categories Applications - Science and Engineering, Convex Optimization, Semi-definite Programming Tags , , , ,

    We discuss convex optimization problems where some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in … Read more

    An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs

  • Michael J. Todd
  • E. Alper Yildirim
    • Categories Linear Programming Tags , ,

    We consider the interior-point approach to sensitivity analysis in linear programming (LP) developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special degeneracy, we show that these bounds have the same nice relationship with the optimal partition bounds as in the nondegenerate case. We prove … Read more

    Improved linear programming bounds for antipodal spherical codes

  • Kurt M. Anstreicher
    • Categories Basic Sciences Applications, Linear Programming Tags , , , ,

    Let $S\subset[-1,1)$. A finite set $C=\{x_i\}_{i=1}^M\subset\Re^n$ is called a {\em spherical S-code} if $||x_i||=1$ for each $i$, and $x_i^T x_j\in S$, $i\ne j$. For $S=[-1,.5]$ maximizing $M=|C|$ is commonly referred to as the {\em kissing number} problem. A well-known technique based on harmonic analysis and linear programming can be used to bound $M$. We consider … Read more

    On implementing a primal-dual interior-point method for conic quadratic optimization

  • Cornelis Roos
  • Erling D. Andersen
  • Tamás Terlaky
    • Categories Convex Optimization, Other Topics, Second-Order Cone Programming Tags , , , ,

    Conic quadratic optimization is the problem of minimizing a linear function subject to the intersection of an affine set and the product of quadratic cones. The problem is a convex optimization problem and has numerous applications in engineering, economics, and other areas of science. Indeed, linear and convex quadratic optimization is a special case. Conic … Read more

    Augmented self concordant barriers and nonlinear optimization problems with finite complexity

  • Yurii Nesterov
  • Jean-Philippe Vial
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we study special barrier functions for the convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center … Read more

    Hyper-sparsity in the revised simplex method and how to exploit it

  • J. A. Julian Hall
  • Kenneth McKinnon
    • Categories Linear Programming Tags , ,

    The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems … Read more

    Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\’asz-Schrijver Lift-and-Project Procedure

  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations … Read more

    On duality theory of conic linear problems

  • Alexander Shapiro
    • Categories Cone Programming, Convex Optimization, Infinite Dimensional Optimization

    In this paper we discuss duality theory of optimization problems with a linear objective function and subject to linear constraints with cone inclusions, referred to as conic linear problems. We formulate the Lagrangian dual of a conic linear problem and survey some results based on the conjugate duality approach where the questions of “no duality … Read more

    Notes on the Dual Simplex Method

  • Robert Fourer
    • Categories Linear Programming Tags ,

    0. The standard dual simplex method. 1. A more general and practical dual simplex method. 2. Phase I for the dual simplex method. 3. Degeneracy in the dual simplex method. 4. A generalized ratio test for the dual simplex method. Citation Draft, Department of Industrial Engineering andManagement Sciences, Northwestern University, 1994. Article Download View Notes … Read more