Linear, Cone and Semidefinite Programming

Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming

  • Deren Han
  • Defeng Sun
  • Liwei Zhang
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we aim to provide a comprehensive analysis on the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a certain error bound condition, we establish the global linear rate of convergence for a more general semi-proximal ADMM with the dual steplength … Read more

    A priori bounds on the condition numbers in interior-point methods

  • Florian Jarre
    • Categories Linear Programming, Semi-definite Programming Tags , ,

    Interior-point methods are known to be sensitive to ill-conditioning and to scaling of the data. This paper presents new asymptotically sharp bounds on the condition numbers of the linear systems at each iteration of an interior-point method for solving linear or semidefinite programs and discusses a stopping test which leads to a problem-independent “a priori” … Read more

    Mixed Integer Second-Order Cone Programming for the Horizontal and Vertical Free-flight Planning Problem

  • Liana Amaya Moreno
  • Armin Fügenschuh
  • Anton Kaier
  • Amina Mollaysa
  • Swen Schlobach
  • Zhi Yuan
    • Categories Airline Optimization, Second-Order Cone Programming Tags , ,

    In the past, travel routes for civil passenger and cargo air traffic were aligned to the air traffic network (ATN). To resolve the network congestion problem, the free-flight system has recently been introduced in more and more regions around the globe, allowing flight operations to make full use of the four space-and-time dimensions. For the … Read more

    Semidefinite approximations of the polynomial abscissa

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Tiên-So'n Pham
  • Roxana Hess
    • Categories Control Applications, Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

    Given a univariate polynomial, its abscissa is the maximum real part of its roots. The abscissa arises naturally when controlling linear differential equations. As a function of the polynomial coefficients, the abscissa is H\”older continuous, and not locally Lipschitz in general, which is a source of numerical difficulties for designing and optimizing control laws. In … Read more

    Closing the gap in pivot methods for linear programming

  • Venkat Narayan
    • Categories Linear Programming Tags , , , , ,

    We propose pivot methods that solve linear programs by trying to close the duality gap from both ends. The first method maintains a set $\B$ of at most three bases, each of a different type, in each iteration: a primal feasible basis $B^p$, a dual feasible basis $B^d$ and a primal-and-dual infeasible basis $B^i$. From … Read more

    Simplified semidefinite and completely positive relaxations

  • Felix Lieder
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the … Read more

    The Jordan Algebraic Structure of the Circular Cone

  • Baha Alzalg
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming

    In this paper, we study and analyze the algebraic structure of the circular cone. We establish a new efficient spectral decomposition, set up the Jordan algebra associated with the circular cone, and prove that this algebra forms a Euclidean Jordan algebra with a certain inner product. We then show that the cone of squares of … Read more

    On the upper Lipschitz property of the KKT mapping for nonlinear semidefinite optimization

  • Liwei Zhang
  • Yule Zhang
    • Categories Semi-definite Programming Tags , , , ,

    In this note, we prove that the KKT mapping for nonlinear semidefinite optimization problem is upper Lipschitz continuous at the KKT point, under the second-order sufficient optimality conditions and the strict Robinson constraint qualification. Article Download View On the upper Lipschitz property of the KKT mapping for nonlinear semidefinite optimization

    Robust truss optimization using the sequential parametric convex approximation method

  • Alfredo Canelas
  • Miguel Carrasco
  • Julio López
    • Categories Global Optimization, Multidisciplinary Design Optimization, Second-Order Cone Programming Tags , , ,

    We study the design of robust truss structures under mechanical equilibrium, displacements and stress constraints. Our main objective is to minimize the total amount of material, for the purpose of finding the most economic structure. A robust design is found by considering load perturbations. The nature of the constraints makes the mathematical program nonconvex. In … Read more

    Using the Johnson-Lindenstrauss lemma in linear and integer programming

  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , ,

    The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we … Read more