Suppose I have a convex optimization problem of the form $$\min_x f(x) ~~s.t.\\x\in X$$. Say that $f(x)$ and its (sub)gradient are not given in a closed form, but are determined by solving a convex sub-problem of the form $$\min_y g(x,y)~~s.t.\\y\in Y(x)$$ where $Y(x)$ is a convex feasible region that depends on $x$. Just to drive the point home, let's say that $g$ and its (sub)gradient are also not given in a closed form, but are determined by solving the convex sub-problem $$\min_z h(x,y,z) ~~s.t.\\z\in Z(x,y)$$, and this last sub-problem does have closed form expressions for the objective function and (sub) gradient. So, our whole problem effectively has three "levels". What can I say about the complexity of my original problem? How does the potential for numerical error propagate back up through the inner problems?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
This is known as bilevel optimization. My impression is that it is considerably harder than usual convex optimization, even numerically.
