Probabilistically constrained quadraticprogramming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconve...
详细信息
Probabilistically constrained quadraticprogramming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixedintegerquadraticprogramming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation. (C) 2012 Elsevier B.V. All rights reserved.
暂无评论