Month: August 2009

All roads lead to Newton: Feasible second-order methods for equality-constrained optimization

  • Pierre-Antoine Absil
  • Ben Andrews
  • Robert Mahony
  • Jochen Trumpf
    • Categories Constrained Nonlinear Optimization

    This paper considers the connection between the intrinsic Riemannian Newton method and other more classically inspired optimization algorithms for equality-constrained optimization problems. We consider the feasibly-projected sequential quadratic programming (FP-SQP) method and show that it yields the same update step as the Riemannian Newton, subject to a minor assumption on the choice of multiplier vector. … Read more

    Risk-Averse Two-Stage Stochastic Linear Programming: Modeling and Decomposition

  • Naomi Miller
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , ,

    We formulate a risk-averse two-stage stochastic linear programming problem in which unresolved uncertainty remains after the second stage. The objective function is formulated as a composition of conditional risk measures. We analyze properties of the problem and derive necessary and sufficient optimality conditions. Next, we construct two decomposition methods for solving the problem. The first … Read more

    Phase Transitions for Greedy Sparse Approximation Algorithms

  • Jeffrey Blanchard
  • Coralia Cartis
  • Jared Tanner
  • Andrew Thompson
    • Categories Applications - Science and Engineering Tags , , ,

    A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven using the ubiquitous Restricted Isometry Property (RIP) [9] to have optimal-order uniform recovery guarantees. However, it is … Read more

    Compressed Sensing: How sharp is the RIP?

  • Jeffrey Blanchard
  • Coralia Cartis
  • Jared Tanner
    • Categories Applications - Science and Engineering Tags , , ,

    Consider a measurement matrix A of size n×N, with n < N, y a signal in R^N, and b = Ay the observed measurement of the vector y. From knowledge of (b,A), compressed sensing seeks to recover the k-sparse x, k < n, which minimizes ||b-Ax||. Using various methods of analysis — convex polytopes, geometric … Read more

    Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs

  • Binyuan Chen
  • Simge Küçükyavuz
  • Suvrajeet Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard … Read more

    Building a completely positive factorization

  • Immanuel M. Bomze
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Using a bordering approach, and building upon an already known factorization of a principal block, we establish sufficient conditions under which we can extend this factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions. Citation Preprint, Univ.of Vienna (2017), submitted Article Download View Building a completely positive factorization

    A new LP algorithm for precedence constrained production scheduling

  • Daniel Bienstock
  • Mark Zuckerberg
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    We present a number of new algorithmic ideas for solving LP relaxations of extremely large precedence constrained production scheduling problems. These ideas are used to develop an implementation that is tested on a variety of real-life, large scale instances; yielding optimal solutions in very practicable CPU time. Citation Unpublished. Columbia University, BHP Billiton, August 2009. … Read more

    Worst-Case Value-at-Risk of Non-Linear Portfolios

  • Daniel Kuhn
  • Berc Rustem
  • Steve Zymler
    • Categories Finance and Economics, Robust Optimization Tags , , , ,

    Portfolio optimization problems involving Value-at-Risk (VaR) are often computationally intractable and require complete information about the return distribution of the portfolio constituents, which is rarely available in practice. These difficulties are compounded when the portfolio contains derivatives. We develop two tractable conservative approximations for the VaR of a derivative portfolio by evaluating the worst-case VaR … Read more

    On the connection of the Sherali-Adams closure and border bases

  • Sebastian Pokutta
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , , ,

    The Sherali-Adams lift-and-project hierarchy is a fundamental construct in integer programming, which provides successively tighter linear programming relaxations of the integer hull of a polytope. We initiate a new approach to understanding the Sherali-Adams procedure by relating it to methods from computational algebraic geometry. Our main result is a refinement of the Sherali-Adams procedure that … Read more

    Stability of error bounds for semi-infinite convex constraint systems

  • Van Ngai Huynh
  • Alexander Y. Kruger
  • Michel Thera
    • Categories Convex Optimization Tags , ,

    In this paper, we are concerned with the stability of the error bounds for semi-infinite convex constraint systems. Roughly speaking, the error bound of a system of inequalities is said to be stable if all its “small” perturbations admit a (local or global) error bound. We first establish subdifferential characterizations of the stability of error … Read more