A global optimization method for solving convex quadratic bilevel programming problems. (English) Zbl 1053.90104

Le Dung Muu; Nguyen Van Quy

J. Glob. Optim. 26, No. 2, 199-219 (2003).

The authors consider the bilevel problem \[ \min\{f_1(t, x): t\in T,\;x\text{ solves }(P)\}, \] where \((P)\) is the minimization problem: \[ \min\{f_2(t, x): x\in X,\,(t,x)\in C\}. \] Here \(f_1(t, x)\) is a convex quadratic function, \[ f_2(t,x)= \textstyle{{1\over 2}} x^\top Qx+ x^\top(Pt+ q), \] \(C= \{(t, x): At+ Bx+ b\leq 0\}\), \(C(t)= \{x\in X: At+ Bx+ b\leq 0\}\), and \(T\) and \(X\) are polyhedral convex sets with \(X\) being bounded. By using the merit function technique the above problem is formulated as a convex program with an additional nonconvex constraint defined by a function which is d.c. with respect to the decision variable of the first level-problem and convex with respect to the decision variable of the second level-problem. This problem is solved by designing a branch-and-bound procedure to an approximation of that convex-concave constraint.
Such an approach is illustrated by considering an optimization problem over the equilibrium points of an oligopolistic market problem.

Reviewer: Fabián Flores-Bazan (Concepción)

MSC:

90C20	Quadratic programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
91A10	Noncooperative games

Keywords:

Convex quadratic bilevel programming; Merit function; Saddle function; Branch-and-bound algorithm; Optimization over an equilibrium set