Optimization Online


A Cutting Surface Method for Uncertain Linear Programs with Polyhedral Stochastic Dominance Constraints

Tito Homem-de-Mello(tito***at***northwesten.edu)
Sanjay Mehrotra(mehrotra***at***iems.northwestern.edu)

Abstract: In this paper we study linear optimization problems with multi-dimensional linear positive second-order stochastic dominance constraints. By using the polyhedral properties of the second- order linear dominance condition we present a cutting-surface algorithm, and show its finite convergence. The cut generation problem is a difference of convex functions (DC) optimization problem. We exploit the polyhedral structure of this problem to present a novel branch-and-cut algorithm that incorporates concepts from concave minimization and binary integer programming. A linear programming problem is formulated for generating concavity cuts in our case, where the polyhedra is unbounded. We also present duality results for this problem relating the dual multipliers to utility functions, without the need to impose constraint qualifications, which again is possible because of the polyhedral nature of the problem. Numerical examples are presented showing the nature of solutions of our model.

Keywords: Linear Programming, Stochastic Ordering, Stochastic Dominance, Utility Functions,

Category 1: Stochastic Programming

Category 2: Global Optimization

Category 3: Linear, Cone and Semidefinite Programming

Citation: Report, IEMS Department, Northwestern University, Evanston, IL 60208 (November 2008).

Download: [PDF]

Entry Submitted: 11/06/2008
Entry Accepted: 11/06/2008
Entry Last Modified: 11/06/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society