Month: May 2012

A Probabilistic Model for Minmax Regret in Combinatorial Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories Combinatorial Optimization

    In this paper, we propose a probabilistic model for minimizing the anticipated regret in combinatorial optimization problems with distributional uncertainty in the objective coefficients. The interval uncertainty representation of data is supplemented with information on the marginal distributions. As a decision criterion, we minimize the worst-case conditional value-at-risk of regret. The proposed model includes the … Read more

    On the non-homogeneity of completely positive cones

  • M. Seetharama Gowda
  • Roman Sznajder
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Given a closed cone C in the Euclidean n-space, the completely positive cone of C is the convex cone K generated by matrices of the form uu^T as u varies over C. Examples of completely positive cones include the positive semidefinite cone (when C is the entire Euclidean n-space) and the cone of completely positive … Read more

    Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

  • Marianna Eisenberg-Nagy
  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , , ,

    We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of … Read more

    Covering Linear Programming with Violations

  • Shabbir Ahmed
  • Santanu S. Dey
  • Feng Qiu
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. In order to improve the performance of mixed-integer programming (MIP) based schemes for these problems, we introduce and analyze a … Read more

    Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential.

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    We prove that uniform second order growth, tilt stability, and strong metric regularity of the subdifferential — three notions that have appeared in entirely different settings — are all essentially equivalent for any lower-semicontinuous, extended-real-valued function. Citation Cornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May … Read more

    Scenario Trees – A Process Distance Approach

  • Raimund Kovacevic
  • Alois Pichler
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Stochastic Programming Tags , ,

    The approximation of stochastic processes by trees is an important topic in multistage stochastic programming. In this paper we focus on improving the approximation of large trees by smaller (tractable) trees. The quality of the approximation is measured by the nested distance, recently introduced in [Pflug]. The nested distance is derived from the Wasserstein distance. … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Primal-Dual Methods and Cubic Regularization

  • Hande Benson
  • David F. Shanno
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a … Read more

    Open versus closed loop capacity equilibria in electricity markets under perfect and oligopolistic competition

  • Julian Barquín
  • Daniel Ralph
  • E. Centeno
  • Benjamin Hobbs
  • S. Wogrin
    • Categories Applications - OR and Management Sciences, Game Theory

    We consider two game-theoretic models of the generation capacity expansion problem in liberalized electricity markets. The first is an open loop equilibrium model, where generation companies simultaneously choose capacities and quantities to maximize their individual profit. The second is a closed loop model, in which companies first choose capacities maximizing their profit anticipating the market … Read more