Robust Optimization

Lagrangean Decomposition for Mean-Variance Combinatorial Optimization

  • Frank Baumann
  • Christoph Buchheim
  • Anna Ilyina
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Robust Optimization Tags , ,

    We address robust versions of combinatorial optimization problems, focusing on the uncorrelated ellipsoidal uncertainty case, which corresponds to so-called mean-variance optimization. We present a branch and bound-algorithm for such problems that uses lower bounds obtained from Lagrangean decomposition. This approach allows to separate the uncertainty aspect in the objective function from the combinatorial structure of … Read more

    Polynomial time algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

  • Dong Li
  • Dolores Romero Morales
    • Categories Production and Logistics, Robust Optimization Tags , , ,

    We study the Minimax Regret Uncapacitated Lot Sizing (MRULS) model, where the production cost function and the demand are subject to uncertainty. We propose a polynomial time algorithm which solves the MRULS model in O(n^6) time. We improve this running time to O(n^5) when only the demand is uncertain, and to O(n^4) when only the … Read more

    Decision Making Based on a Nonparametric Shape-Preserving Perturbation of a Reference Utility Function

  • Jian Hu
    • Categories Finance and Economics, Robust Optimization, Stochastic Programming Tags , , , ,

    This paper develops a robust optimization based decision-making framework using a nonparametric perturbation of a reference utility function. The perturbation preserves the risk-aversion property but solves the problem of ambiguity and inconsistency in eliciting the reference utility function. We study the topology of the perturbation, and show that in the decision-making framework the price of … Read more

    Derivative-free Robust Optimization for Circuit Design

  • A. Ciccazzo
  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
  • V. Latorre
    • Categories Nonlinear Optimization, Robust Optimization Tags

    In this paper, we introduce a framework for derivative-free robust optimization based on the use of an efficient derivative-free optimization routine for mixed integer nonlinear problems. The proposed framework is employed to find a robust optimal design of a particular integrated circuit (namely a DC-DC converter commonly used in portable electronic devices). The proposed robust … Read more

    Robust Data-Driven Dynamic Programming

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

    In stochastic optimal control the distribution of the exogenous noise is typically unknown and must be inferred from limited data before dynamic programming (DP)-based solution schemes can be applied. If the conditional expectations in the DP recursions are estimated via kernel regression, however, the historical sample paths enter the solution procedure directly as they determine … Read more

    Conic Geometric Programming

  • Venkat Chandrasekaran
  • Parikshit Shah
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , , ,

    We introduce and study conic geometric programs (CGPs), which are convex optimization problems that unify geometric programs (GPs) and conic optimization problems such as linear programs (LPs) and semidefinite programs (SDPs). A CGP consists of a linear objective function that is to be minimized subject to affine constraints, convex conic constraints, and upper bound constraints … Read more

    Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

  • V. Jeyakumar
  • Guoyin Li
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more

    Ambiguous Probabilistic Programs

  • Jeff L Hong
  • Anthony Man-Cho So
  • Zhaolin Hu
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Probabilistic programs are widely used decision models. When implemented in practice, however, there often exists distributional ambiguity in these models. In this paper, we model the ambiguity using the likelihood ratio (LR) and use LR to construct various ambiguity sets. We consider ambiguous probabilistic programs which optimize under the worst case. Ambiguous probabilistic programs can … Read more

    A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives

  • Selin Damla Ahipasaoglu
  • Karthik Natarajan
  • Xiaobo Li
    • Categories Applications - OR and Management Sciences, Robust Optimization, Semi-definite Programming Tags , ,

    A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large and simulation is used to approximate the choice probabilities. … Read more

    Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization

  • Dimitris Bertsimas
  • Angelos Georghiou
    • Categories Applications - OR and Management Sciences, Integer Programming, Robust Optimization Tags , ,

    In recent years, decision rules have been established as the preferred solution method for addressing computationally demanding, multistage adaptive optimization problems. Despite their success, existing decision rules (a) are typically constrained by their a priori design and (b) do not incorporate in their modeling adaptive binary decisions. To address these problems, we first derive the … Read more