Optimization Online


An Alternating Direction Method for Chance-Constrained Optimization Problems with Discrete Distributions

Xiaodi Bai (xdbai***at***fudan.edu.cn)
Jie Sun (jsun***at***nus.edu.sg)
Xiaojin Zheng (xjzheng***at***tongji.edu.cn)
Xiaoling Sun (xls***at***fudan.edu.cn)

Abstract: We consider a chance-constrained optimization problem (CCOP), where the random variables follow finite discrete distributions. The problem is in general nonconvex and can be reformulated as a mixed-integer program. By exploiting the special structure of the probabilistic constraint, we propose an alternating direction method for finding suboptimal solutions of CCOP. At each iteration, this method solves a convex programming subproblem and a 0-1 knapsack subproblem, which can be computed in quasi-linear time in the case of equal probabilities. We establish the convergence of the method to a first-order stationary point under certain mild conditions. Preliminary computational results are reported for VaR-constrained portfolio selection problems and chance-constrained transportation problems. Numerical results show that the proposed method is promising for finding solutions of good quality and compares favorably with CPLEX and other existing approximation methods, especially for large-size problems.

Keywords: Chance-constrained optimization problem; finite discrete distribution; alternating direction method; augmented Lagrangian decomposition; first-order stationary point

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 04/26/2012
Entry Accepted: 04/26/2012
Entry Last Modified: 11/22/2013

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 Optimization Society