Solve a quadratic programming problem with constraint that is also an linear optimization problem

convex optimizationduality-theoremslinear programming

Let's say we have $n\times 1$ vector $f$ and $h$, $n\times n$ matrix $A$ and $B$, $m\times n$ matrix $R_1$ and $R_2$, $m\times 1$ vector $b_1$ and $b_2$. Now I try to solve the following problem:
$$\begin{align}&\max_{h,f} f^TAh\\s.t.& \quad R_1h\leq b_1\tag{1}\\&\quad f\in \arg\max f^TBh \tag{2} \\&\quad s.t. \quad R_2f\leq b_2\tag{3}.\end{align}$$
I know that if $f$ is given, then everything can be solved easily by duality of linear programming. But now I have constraint $(2)$, which is also an optimiazation problem itself. Is there also a convinient way to solve it?

Best Answer

It is called a bilevel program. There is no convenient way of solving it, if you by convenient mean fast in the general case. It is an intractable problem class theoretically.

The basics of a standard approach is to replace the optimality constraint with the resulting KKT conditions, which means adding complementarity constraints to the model (i.e. non-convex constraints). That in combination with the outer objective which is bilinear in $f$ and $h$ means the resulting problem is a non-convex quadratic problem.

This is one way of modelling it in the MATLAB toolbox YALMIP. To solve it you will either have to have an external non-convex quadratic solver such as Gurobi, or hope that the internal global non-convex solver manages it.

f = sdpvar(n,1);
h = sdpvar(n,1);
OuterObj = -f'*A*h
Outer_C = [R1*h<=b1];
InnerObj = -f'*B*h;
Inner_C = R2*f<=b2;
K = kkt(Inner_C,InnerObj,h);
optimize([Outer_C,K],OuterObj)
Related Question