DASC: a Decomposition Algorithm for multistage stochastic programs with Strongly Convex cost functions

  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce DASC, a decomposition method akin to Stochastic Dual Dynamic Programming (SDDP) which solves some multistage stochastic optimization problems having strongly convex cost functions. Similarly to SDDP, DASC approximates cost-to-go functions by a maximum of lower bounding functions called cuts. However, contrary to SDDP, the cuts computed with DASC are quadratic functions. We also … Read more

    The extensions of Yuan’s lemma and applications in S-lemma

  • Qingzhi Yang
  • Wang Zhongwen
  • Yang Zhou
    • Categories Quadratic Programming

    In this paper we extend a lemma due to Yuan from several aspects. A new proof of Yuan’s lemma is given. A rank-one decomposition of positive semidefinite matrix is further developed. With the extended rank-one de- composition results, we generalize the Yuan’s lemma to general quadratic function systems, interval quadratic function systems and quadratic matrix … Read more

    Computational Aspects of Bayesian Solution Estimators in Stochastic Optimization

  • Gérard Cornuéjols
  • Danial Davarnia
  • Burak Kocuk
    • Categories Statistics, Stochastic Approaches, Stochastic Programming Tags , , , ,

    We study a class of stochastic programs where some of the elements in the objective function are random, and their probability distribution has unknown parameters. The goal is to find a good estimate for the optimal solution of the stochastic program using data sampled from the distribution of the random elements. We investigate two common … Read more

    Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

  • Florian Jarre
  • Ya-Feng Liu
  • Felix Lieder
  • Cheng Lu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more

    Characterizing and testing subdifferential regularity for piecewise smooth objective functions

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , , , ,

    Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT … Read more

    The robust stabilization problem for discrete-time descriptor systems

  • Claudiu Dinicu
    • Categories Robust Optimization Tags , ,

    In this paper the robust stabilization problem for linear discrete-time descriptor systems is investigated. This means that the transfer function matrix of the system at hand is allowed to be improper or even polynomial, as the uncertainty acts on normalized coprime factors. The main results comprising explicit analytical formulas for the maximum stability margin and … Read more

    Weak Stability of $\ell_1hBcminimization Methods in Sparse Data Reconstruction

  • H. Jiang
  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Linear Programming Tags , , , , ,

    As one of the most plausible convex optimization methods for sparse data reconstruction, $\ell_1$-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, … Read more

    A partial outer convexification approach to control transmission lines

  • Simone Göttlich
  • Andreas Potschka
  • Claus Teuber
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs Tags , ,

    In this paper we derive an efficient optimization approach to calculate optimal controls of electric transmission lines. These controls consist of time-dependent inflows and switches that temporarily disable single arcs or whole subgrids to reallocate the flow inside the system. The aim is then to find the best energy input in terms of boundary controls … Read more

    Generalized Dual Dynamic Programming for Infinite Horizon Problems in Continuous State and Action Spaces

  • Paul Beuchat
  • John Lygeros
  • Joseph Warrington
    • Categories Control Applications, Dynamic Programming Tags , , ,

    We describe a nonlinear generalization of dual dynamic programming theory and its application to value function estimation for deterministic control problems over continuous state and action (or input) spaces, in a discrete-time infinite horizon setting. We prove that the result of a one-stage policy evaluation can be used to produce nonlinear lower bounds on the … Read more

    Probabilistic Variational Formulation of Binary Programming

  • Juan Banda
  • Arturo Berrones
  • Jonás Velasco
    • Categories 0-1 Programming, Quadratic Programming Tags , ,

    A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more