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

    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

    Solving PhaseLift by low-rank Riemannian optimization methods for complex semidefinite constraints

  • Kyle A. Gallivan
  • Wen Huang
  • Xiangxiong Zhang
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming

    A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers … Read more