alpha-Conservative approximation for probabilistically constrained convex programs

作者：Takano Yuichi; Gotoh Jun ya^*

来源：Computational Optimization and Applications, 2010, 46(1): 113-133.

DOI：10.1007/s10589-008-9178-5

• Chance constraint
• DC optimization
• Branch-and-bound
• Value-at-risk minimization
• Probabilistically constrained program

In this paper, we address an approximate solution of a probabilistically constrained convex program (PCCP), where a convex objective function is minimized over solutions satisfying, with a given probability, convex constraints that are parameterized by random variables. In order to approach to a solution, we set forth a conservative approximation problem by introducing a parameter alpha which indicates an approximate accuracy, and formulate it as a D.C. optimization problem.
As an example of the PCCP, the Value-at-Risk (VaR) minimization is considered under the assumption that the support of the probability of the associated random loss is given by a finitely large number of scenarios. It is advantageous in solving the D.C. optimization that the numbers of variables and constraints are independent of the number of scenarios, and a simplicial branch-and-bound algorithm is posed to find a solution of the D.C. optimization. Numerical experiments demonstrate the following: (i) by adjusting a parameter alpha, the proposed problem can achieve a smaller VaR than the other convex approximation approaches; (ii) when the number of scenarios is large, a typical 0-1 mixed integer formulation for the VaR minimization cannot be solved in a reasonable time and the improvement of the incumbent values is slow, whereas the proposed method can achieve a good solution at an early stage of the algorithm.

• 出版日期2010-5