A new decomposition algorithm for globally solving mathematical programs with affine equilibrium constraints

zbMATH Open1248.49042arXiv1105.3343MaRDI QIDQ445789FDOQ445789

Le Dung Muu, Pham Dinh Tao, Quoc Tran Dinh, Le Thi Hoai An

Publication date: 27 August 2012

Published in: Acta Mathematica Vietnamica (Search for Journal in Brave)

Abstract: A mathematical programming problem with affine equilibrium constraints (AMPEC) is a bilevel programming problem where the lower one is a parametric affine variational inequality. We formulate some classes of bilevel programming in forms of MPEC. Then we use a regularization technique to formulate the resulting problem as a mathematical program with an additional constraint defined by the difference of two convex functions (DC function). A main feature of this DC decomposition is that the second component depends upon only the parameter in the lower problem. This property allows us to develop branch-and-bound algorithms for globally solving AMPEC where the adaptive rectangular bisection takes place only in the space of the parameter. As an example, we use the proposed algorithm to solve a bilevel Nash-Cournot equilibrium market model. Computational results show the efficiency of the proposed algorithm.

Full work available at URL: https://arxiv.org/abs/1105.3343

Recommendations

• On branch-and-bound algorithms for global optimal solutions to mathematical programs with affine equilibrium constraints
• A branch-and-bound method for discretely-constrained mathematical programs with equilibrium constraints
• A Benders decomposition method for discretely-constrained mathematical programs with equilibrium constraints
• Global algorithm for solving stationary points for equilibrium programs with shared equilibrium constraints
• Methods for finding global optimal solutions to linear programs with equilibrium constraints

zbMATH Keywords

regularizationglobal optimizationbilevel convex quadratic programmingDC formulationmathematical programs with affine equilibrium constraintsNash-Cournot model

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Decomposition methods (49M27) Numerical methods for variational inequalities and related problems (65K15)

Cited In (5)

• DC Programming and DCA for General DC Programs
• Robust truss topology optimization via semidefinite programming with complementarity constraints: a difference-of-convex programming approach
• A study of the difference-of-convex approach for solving linear programs with complementarity constraints
• A Benders decomposition method for discretely-constrained mathematical programs with equilibrium constraints
• On branch-and-bound algorithms for global optimal solutions to mathematical programs with affine equilibrium constraints

This page was built for publication: A new decomposition algorithm for globally solving mathematical programs with affine equilibrium constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445789)