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?
Solve a quadratic programming problem with constraint that is also an linear optimization problem
convex optimizationduality-theoremslinear programming
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.