Optimizing a function with variable the solution of another optimization problem

Question

I am working on an optimization problem whose variables are the solution of another optimization problem. Formally, let $f:\mathbb{R}^{m\times n}\to\mathbb{R}$ and $g:\mathbb{R}^k\times\mathbb{R}^{m\times n}\to\mathbb{R}$ be known, where $m\leq n$. Consider the following optimization problem $$ \max_{w} f(Y(w)) $$ $$ s.t. $$ $$ Y(w) = \text{argmax}_{Y:YY^T=I_m} g(w,Y) $$ where $I_m$ is the $m\times m$ identity matrix. For each given $w$, the procedure to find $Y(w)$ is known. Is there any standard way to solve this kind of optimization problem? Any direction or pointing to literature would be appreciated. Thanks.

Answer 1

You have a bilevel optimization problem. Usually, these problems are quite hard. Even if the lower level problem and the upper level problems are convex, the full problem may be NP hard. However, you may find suitable algorithms under the name "bilevel optimization", but be prepared that this may get quite challenging. One simple approach: If the lower level solution $Y$ is unique, there exists a solution map which maps $\omega$ to $Y(\omega)$. To take the derivative of the upper level problem, you can use the chain rule, but then you need the derivative of the solution operator (or a weaker version of the derivative, in case the solution operator is not differentiable) and this may be obtain by a kind of implicit function theorem.

Answer 2

As mentioned in the previous comment this is a bilevel optimization problem and under some assumptions (usually involving differentiability of your $f$ and $Y$) you might be able to reduce it into a single level optimization problem at the cost of extra constraints, the KKT conditions for the lower-level problem.

Generically you have something like:

\begin{align} {\rm minimize} & \quad f(x,y)\\ {\text{subject to}} & \quad G(x) \leq 0 \\ & \quad y \in {\text {arg min}} _y \{ f(x,y) \,|\, g(x,y)\succeq 0 \} \end{align}

The lower-level problem is thus:

\begin{align} {\rm minimize}_y & \quad f(x,y) \\ {\text{subject to}} & \quad g(x,y)\succeq 0 \\ \end{align}

Assuming that $f,g$ are sufficient times differentiable, one can form the Lagrangian and following the discussion of Section 4 of SIAM J. Optim., 28(2), 1564–1587 one can show that global solutions of the initial bilevel problem are also global solutions of the re-formulated problem with the KKT conditions taking the place of the lower level optimisation problem.

Furthermore, for generic discussion of bilevel problems one can look at these:

https://arxiv.org/abs/1705.06270

https://arxiv.org/abs/1912.06376

https://arxiv.org/abs/1912.06380