Linear, Cone and Semidefinite Programming

Interior Proximal Algorithm with Variable Metric for Second-Order Cone Programming: Applications to Structural Optimization and Support Vector Machines

  • Felipe Álvarez
  • Julio López
  • Héctor Ramírez
    • Categories Second-Order Cone Programming Tags , , , , ,

    In this work, we propose an inexact interior proximal type algorithm for solving convex second-order cone programs. This kind of problems consists of minimizing a convex function (possibly nonsmooth) over the intersection of an affine linear space with the Cartesian product of second-order cones. The proposed algorithm uses a distance variable metric, which is induced … Read more

    Covariance regularization in inverse space

  • Takashi Tsuchiya
  • Genta Ueno
    • Categories Data-Mining, Semi-definite Programming Tags , ,

    This paper proposes to apply Gaussian graphical models to estimate the large-scale normal distribution in the context of data assimilation from a relatively small number of data from the satellite. Data assimilation is a field which fits simulation models to observation data developed mainly in meteorology and oceanography. The optimization problem tends to be huge … Read more

    Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian

  • Frank Göring
  • Christoph Helmberg
  • Susanna Reiss
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes … Read more

    Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions

  • Nathan Krislock
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , ,

    The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion … Read more

    Iteration-complexity of first-order augmented Lagrangian methods for convex programming

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

    This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means … Read more

    Cutting Plane Methods and Subgradient Methods

  • John E. Mitchell
    • Categories Convex Optimization, Cutting Plane Approaches, Linear, Cone and Semidefinite Programming Tags , , , ,

    Interior point methods have proven very successful at solving linear programming problems. When an explicit linear programming formulation is either not available or is too large to employ directly, a column generation approach can be used. Examples of column generation approaches include cutting plane methods for integer programming and decomposition methods for many classes of … Read more

    A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part II: General Algorithm

  • Takanori Maehara
  • Kazuo Murota
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    An algorithm is proposed for finding the finest simultaneous block-diagonalization of a finite number of square matrices, or equivalently the irreducible decomposition of a matrix *-algebra given in terms of its generators. This extends the approach initiated in Part I by Murota-Kanno-Kojima-Kojima. The algorithm, composed of numerical-linear algebraic computations, does not require any algebraic structure … Read more

    The L1-Norm Best-Fit Hyperplane Problem

  • J. Paul Brooks
  • JH Dulá
    • Categories Data-Mining, Linear Programming, Statistics Tags , , ,

    We formalize an algorithm for solving the L1-norm best-fit hyperplane problem derived using first principles and geometric insights about L1 projection and L1 regression. The procedure follows from a new proof of global optimality and relies on the solution of a small number of linear programs. The procedure is implemented for validation and testing. This … Read more

    Row by row methods for semidefinite programming

  • Zaiwen Wen
  • Donald Goldfarb
  • Shiqian Ma
  • Katya Scheinberg
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , ,

    We present a row-by-row (RBR) method for solving semidefinite programming (SDP) problem based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n-1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order … Read more

    NESTA: A Fast and Accurate First-order Method for Sparse Recovery

  • Stephen Becker
  • Jerome Bobin
  • Emmanuel Candès
    • Categories Biomedical Applications, Nonsmooth Optimization, Second-Order Cone Programming Tags , , , , , ,

    Accurate signal recovery or image reconstruction from indirect and possibly under- sampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel fi rst-order methods in convex optimization, most notably Nesterov’s smoothing technique, this paper … Read more