Month: May 2016

A CVaR Scenario-based Framework: Minimizing Downside Risk of Multi-asset Class Portfolios

  • Kartik Krishnan Sivaramakrishnan
  • Robert Stamicar
    • Categories Applications - OR and Management Sciences, Finance and Economics, Stochastic Programming Tags , ,

    Multi-asset class (MAC) portfolios can be comprised of investments in equities, fixed-income, commodities, foreign-exchange, credit, derivatives, and alternatives such as real-estate and private equity. The return for such {\em non-linear} portfolios is {\em asymmetric} with significant tail risk. The traditional Markowitz Mean-Variance Optimization (MVO) framework, that linearizes all the assets in the portfolio and uses … Read more

    A feasible rounding approach for granular optimization problems

  • Christoph Neumann
  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    We introduce a new technique to generate good feasible points of mixed-integer nonlinear optimization problems. It makes use of the so-called inner parallel set of the relaxed feasible set, which was employed in O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, Vol. 156 (2016), 101-123, as well as O. Stein, Error … Read more

    Barzilai-Borwein Step Size for Stochastic Gradient Descent

  • Yu-Hong Dai
  • Shiqian Ma
  • Yuqiu Qian
  • Conghui Tan
    • Categories Convex Optimization, Stochastic Approaches Tags , ,

    One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step … Read more

    Piecewise Parametric Structure in the Pooling Problem – from Sparse Strongly-Polynomial Solutions to NP-Hardness

  • Radu Baltean-Lugojan
  • Ruth Misener
    • Categories Combinatorial Optimization, Quadratic Programming Tags , , , , , ,

    The standard pooling problem is a NP-hard sub-class of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity of the standard pooling problem in its p-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems … Read more

    How to choose what you lift

  • Amitabh Basu
  • Santanu S. Dey
  • Joseph Paat
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We explore the lifting question in the context of cut-generating functions. Most of the prior literature on lifting for cut-generating functions focuses on which cut-generating functions have the unique lifting property. Here we develop a general theory for under- standing how to do lifting for cut-generating functions which do not have the unique lifting property. … Read more

    A fresh CP look at mixed-binary QPs: New formulations and relaxations

  • Immanuel M. Bomze
  • Peter J.C. Dickinson
  • Abdel Lisser
  • Jianqiang Cheng
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , , , , ,

    Triggered by Burer’s seminal characterization from 2009, many copositive (CP) reformulations of mixed-binary QPs have been discussed by now. Most of them can be used as proper relaxations, if the intractable co(mpletely )positive cones are replaced by tractable approximations. While the widely used approximation hierarchies have the disadvantage to use positive-semidefinite (psd) matrices of orders … Read more

    A combinatorial approach for small and strong formulations of disjunctive constraints

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations … Read more

    Randomized Primal-Dual Proximal Block Coordinate Updates

  • Xiang Gao
  • Yangyang Xu
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such … Read more

    The complexity of simple models – a study of worst and typical hard cases for the Standard Quadratic Optimization Problem

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Game Theory, Global Optimization Theory, Quadratic Programming

    In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. … Read more

    Distributionally Robust Optimization with Principal Component Analysis

  • Richard Chen
  • Habib Najm
  • Jean-Paul Watson
  • Jianqiang Cheng
  • Ali Pinar
  • Cosmin Safta
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization (DRO) is widely used, because it offers a way to overcome the conservativeness of robust optimization without requiring the specificity of stochastic optimization. On the computational side, many practical DRO instances can be equivalently (or approximately) formulated as semidefinite programming (SDP) problems via conic duality of the moment problem. However, despite being … Read more