Convex and Nonsmooth Optimization

Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem

  • Yair Censor
  • Tommy Elfving
    • Categories Convex Optimization, Linear Programming Tags , , , , ,

    We formulate a block-iterative algorithmic scheme for the solution of systems of linear inequalities and/or equations and analyze its convergence. This study provides as special cases proofs of convergence of (i) the recently proposed Component Averaging (CAV) method of Censor, Gordon and Gordon ({\it Parallel Computing}, 27:777–808, 2001), (ii) the recently proposed Block-Iterative CAV (BICAV) … Read more

    Smoothing Method of Multipliers for Sum-Max Problems

  • Michael Zibulevsky
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , ,

    We study nonsmooth unconstrained optimization problem, which includes sum of pairwise maxima of smooth functions. Minimum $l_1$-norm approximation is a particular case of this problem. Combining ideas Lagrange multipliers with smooth approximation of max-type function, we obtain a new kind of nonquadratic augmented Lagrangian. Our approach does not require artificial variables, and preserves sparse structure … Read more

    Lagrangean Duality Applied on Vehicle Routing with Time Windows

  • Brian Kallehauge
  • Jesper Larsen
  • Oli B.G. Madsen
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Transportation Tags , , , , ,

    This paper presents the results of the application of a non-differentiable optimization method in connection with the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an extension of the Vehicle Routing Problem. In the VRPTW the service at each customer must start within an associated time window. The Shortest Path decomposition of the … Read more

    The Volume Algorithm revisited: relation with bundle methods

  • Laura Bahiense
  • Claudia Sagastizábal
  • Nelson Maculan
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , ,

    We revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order … Read more

    A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations

  • Christoph Helmberg
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , ,

    The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more

    On Numerical Solution of the Maximum Volume Ellipsoid Problem

  • Liyan Gao
  • Yin Zhang
    • Categories Convex Optimization Tags ,

    In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in $\Re^n$ defined by a finite set of linear inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two … Read more

    Complexity of Convex Optimization using Geometry-based Measures and a Reference Point

  • Robert M. Freund
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more

    Strong semismoothness of eigenvalues of symmetric matrices and its application to inverse eigenvalue problems

  • Jie Sun
  • Defeng Sun
    • Categories Control Applications, Nonsmooth Optimization Tags , , , , ,

    It is well known that the eigenvalues of a real symmetric matrix are not everywhere differentiable. A classical result of Ky Fan states that each eigenvalue of a symmetric matrix is the difference of two convex functions. This directly implies that the eigenvalues of a symmetric matrix are semismooth everywhere. Based on a very recent … Read more

    Semi-infinite linear programming approaches to semidefinite programming problems

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Convex and Nonsmooth Optimization, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Interior point methods, the traditional methods for the $SDP$, are fairly limited in the sizes of problems they can handle. This paper deals with an $LP$ approach to overcome some of these shortcomings. We begin with a semi-infinite linear programming formulation of the $SDP$ and discuss the issue of its discretization in some detail. We … Read more

    On the Primal-Dual Geometry of Level Sets in Linear and Conic Optimization

  • Robert M. Freund
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    For a conic optimization problem: minimize cx subject to Ax=b, x \in C, we present a geometric relationship between the maximum norms of the level sets of the primal and the inscribed sizes of the level sets of the dual (or the other way around). CitationMIT Operations Research Center Working PaperArticleDownload View PDF