How do you usually describe the following problem and how to solve it ?

\begin{equation*} \begin{aligned} & \underset{x,y}{\min} & & f(x,y) + z, \\ & \text{s.t.} & & z = \underset{w}{\min}\quad g(x,y,w). \end{aligned} \end{equation*} Here, $f(x,y)$ is linear in $x$ and convex in $y$. $z$ is linear in $w$. Also, it is impossible to solve the problem as, \begin{equation*} \underset{x,y,w}{\min} \quad f(x,y) + g(x,y,w). \end{equation*}

  • $\begingroup$ This isn't really a bilevel optimization problem. A bilevel problem has constraints of the form $z\in\arg\min_wg(x,y,w)$ (in this case, $z$ is a vector, not a scalar). This problem is just an unconstrained optimization problem. Define the function $G(x,y)=\min_wg(x,y,w)$. Then you just wish to solve $\min_{x,y}f(x,y)+G(x,y)$. The solution approach to this problem depends significantly on the size of the problem and the structure of the function $g$. Can you provide more information about that? $\endgroup$ – David M. Aug 12 '18 at 15:16

Your Answer

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

Browse other questions tagged or ask your own question.