Solving sparse polynomial optimization problems with chordal structure using the sparse, bounded-degree sum-of-squares hierarchy

  • Joachim Dahl
  • Etienne de Klerk
  • Ahmadreza Marandi
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser, Lasserre and Toh [arXiv:1607.01151,2016] constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proven by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality … Read more

    CONVEX GEOMETRY OF THE GENERALIZED MATRIX-FRACTIONAL FUNCTION

  • James V. Burke
  • Tim Hoheisel
  • Yuan Gao
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Generalized matrix-fractional (GMF) functions are a class of matrix support functions introduced by Burke and Hoheisel as a tool for unifying a range of seemingly divergent matrix optimization problems associated with inverse problems, regularization and learning. In this paper we dramatically simplify the support function representation for GMF functions as well as the representation of … Read more

    Optimal Control of MDP’s with Unbounded Cost on Infinite Horizon

  • Kerem Ugurlu
    • Categories Applications - OR and Management Sciences Tags , , ,

    We use Markov risk measures to formulate a risk averse version of a total cost problem on a controlled Markov process in infinite horizon. The one step costs are in $L^1$ but not necessarily bounded. We derive the conditions for the existence of the optimal strategies and present the robust dynamic programming equations. We illustrate … Read more

    Comparison of Lasserre’s measure–based bounds for polynomial optimization to bounds obtained by simulated annealing

  • Etienne de Klerk
  • Monique Laurent
    • Categories Global Optimization, Nonlinear Optimization, Semi-definite Programming

    We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, … Read more

    A semi-analytical approach for the positive semidefinite Procrustes problem

  • Nicolas Gillis
  • Punit Sharma
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The positive semidefinite Procrustes (PSDP) problem is the following: given rectangular matrices $X$ and $B$, find the symmetric positive semidefinite matrix $A$ that minimizes the Frobenius norm of $AX-B$. No general procedure is known that gives an exact solution. In this paper, we present a semi-analytical approach to solve the PSDP problem. First, we characterize … Read more

    An extension of Yuan’s Lemma and its applications in optimization

  • Gabriel Haeser
    • Categories Nonlinear Optimization Tags , ,

    We prove an extension of Yuan’s Lemma to more than two matrices, as long as the set of matrices has rank at most 2. This is used to generalize the main result of [A. Baccari and A. Trad. On the classical necessary second-order optimality conditions in the presence of equality and inequality constraints. SIAM J. … Read more

    A successive linear programming algorithm with non-linear time series for the reservoir management problem

  • Erick Delage
  • Charles Gauvin
  • Michel Gendreau
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    This paper proposes a multi-stage stochastic programming formulation based on affine decision rules for the reservoir management problem. Our approach seeks to find a release schedule that balances flood control and power generation objectives while considering realistic operating conditions as well as variable water head. To deal with the non-convexity introduced by the variable water … Read more

    Exploiting Negative Curvature in Deterministic and Stochastic Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although some prior work has established convergence results for algorithms that integrate both descent and negative curvature directions, there has not yet been numerical evidence showing that such methods offer significant performance improvements. In … Read more

    Algorithmic Differentiation for Piecewise Smooth Functions: A Case Study for Robust Optimization

  • Sabrina Fiege
  • Andreas Griewank
  • Kshitij Kulshreshtha
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , ,

    This paper presents a minimization method for Lipschitz continuous, piecewise smooth objective functions based on algorithmic differentiation (AD). We assume that all nondifferentiabilities are caused by abs(), min(), and max(). The optimization method generates successively piecewise linearizations in abs-normal form and solves these local subproblems by exploiting the resulting kink structure. Both, the generation of … Read more

    An Augmented Lagrangian Proximal Alternating Method for Sparse Discrete Optimization Problems

  • Xiaoliang Song
  • Yue Teng
  • Li Yang
  • Bo Yu
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Finance and Economics

    In this paper, an augmented Lagrangian proximal alternating (ALPA) method is proposed for two class of large-scale sparse discrete constrained optimization problems in which a sequence of augmented Lagrangian subproblems are solved by utilizing proximal alternating linearized minimization framework and sparse projection techniques. Under the Mangasarian-Fromovitz and the basic constraint qualification, we show that any … Read more