Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

  • Grani A. Hanasusanto
  • Daniel Kuhn
    • Categories Robust Optimization Tags , , ,

    Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, … Read more

    Optimal Deterministic Algorithm Generation

  • Ioannis G. Kevrekidis
  • Alexander Mitsos
  • Jaromił Najman
    • Categories Applications - Science and Engineering, Global Optimization, Other Topics Tags , ,

    A formulation for the automated generation of algorithms via mathematical programming (optimization) is proposed. The formulation is based on the concept of optimizing within a parameterized family of algorithms, or equivalently a family of functions describing the algorithmic steps. The optimization variables are the parameters – within this family of algorithms- that encode algorithm design: … Read more

    A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning

  • Aleksandr Y. Aravkin
  • Damek Davis
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    Machine learning theory typically assumes that training data is unbiased and not adversarially generated. When real training data deviates from these assumptions, trained models make erroneous predictions, sometimes with disastrous effects. Robust losses, such as the huber norm are designed to mitigate the effects of such contaminated data, but they are limited to the regression … Read more

    Under-relaxed Quasi-Newton acceleration for an inverse fixed-point problem coming from Positron-Emission Tomography

  • José Mario Martínez
  • Tiara Martini
  • Louise Reips
    • Categories Applications - Science and Engineering Tags , ,

    Quasi-Newton acceleration is an interesting tool to improve the performance of numerical methods based on the fixed-point paradigm. In this work the quasi-Newton technique will be applied to an inverse problem that comes from Positron Emission Tomography, whose fixed-point counterpart has been introduced recently. It will be shown that the improvement caused by the quasi-Newton … Read more

    A recursive semi-smooth Newton method for linear complementarity problems

  • Philipp Hungerländer
  • Joaquim J. Júdice
  • Franz Rendl
    • Categories Bound-constrained Optimization, Convex Optimization, Quadratic Programming Tags , , , ,

    A primal feasible active set method is presented for finding the unique solution of a Linear Complementarity Problem (LCP) with a P-matrix, which extends the globally convergent active set method for strictly convex quadratic problems with simple bounds proposed by [P. Hungerlaender and F. Rendl. A feasible active set method for strictly convex problems with … Read more

    An Infeasible Active Set Method with Combinatorial Line Search for Convex Quadratic Problems with Bound Constraints

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Convex Optimization, Quadratic Programming Tags , , , ,

    The minimization of a convex quadratic function under bound constraints is a fundamental building block for more complicated optimization problems. The active-set method introduced by [M. Bergounioux, K. Ito, and K. Kunisch. Primal-Dual Strategy for Constrained Optimal Control Problems. SIAM Journal on Control and Optimization, 37:1176–1194, 1999.] and [M. Bergounioux, M. Haddou, M. Hintermüller, and … Read more

    An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

  • Fabio Furini
  • Ivana Ljubić
  • Markus Sinnl
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

    Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more

    A universal and structured way to derive dual optimization problem formulations

  • Marleen Balvert
  • Dick den Hertog
  • Bram L. Gorissen
  • Cornelis Roos
    • Categories Convex Optimization Tags , , , ,

    The dual problem of a convex optimization problem can be obtained in a relatively simple and structural way by using a well-known result in convex analysis, namely Fenchel’s duality theorem. This alternative way of forming a strong dual problem is the subject in this paper. We recall some standard results from convex analysis and then … Read more

    On deterministic reformulations of distributionally robust joint chance constrained optimization problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Convex Optimization, Robust Optimization, Stochastic Programming Tags , , ,

    A joint chance constrained optimization problem involves multiple uncertain constraints, i.e., constraints with stochastic parameters, that are jointly required to be satisfied with probability exceeding a prespecified threshold. In a distributionally robust joint chance constrained optimization problem (DRCCP), the joint chance constraint is required to hold for all probability distributions of the stochastic parameters from … Read more

    Optimization with stochastic preferences based on a general class of scalarization functions

  • Nilay Noyan
  • Gabor Rudolf
    • Categories Multi-Criteria Optimization, Stochastic Programming

    It is of crucial importance to develop risk-averse models for multicriteria decision making under uncertainty. A major stream of the related literature studies optimization problems that feature multivariate stochastic benchmarking constraints. These problems typically involve a univariate stochastic preference relation, often based on stochastic dominance or a coherent risk measure such as conditional value-at-risk (CVaR), … Read more