1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

This is known as bilevel optimization. My impression is that it is considerably harder than usual convex optimization, even numerically.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.