I am trying to solve the following optimization problem: $$ \max_{\mathbf{x}} \ \min_{\mathbf{y}} \ -f(\mathbf{x}) + g(\mathbf{y}) \\ \qquad \ \mathrm{s.t.} \quad \mathbf{x} + \mathbf{y} = 0 \; , \tag{1} $$ where $f(\mathbf{x})$ is a convex function and $g(\mathbf{y})$ is a convex function.
My first instinct is to turn the optimization problem into a separable minimization problem by the following manipulation: $$ \min_{\mathbf{x}} \ \min_{\mathbf{y}} \ f(\mathbf{x}) + g(\mathbf{y}) \\ \qquad \ \ \mathrm{s.t.} \quad \mathbf{x} + \mathbf{y} = 0 \; , \tag{2} $$ but I'm not sure if the transformation from (1) to (2) is valid. Intuitively, because the two functions in the objective function are separable (they depend on different variables), I thought I could change the first the maximization over $\mathbf{x}$ into a minimization over $\mathbf{x}$ by flipping the sign of the part of the objective function that depended on $\mathbf{x}$.
I know that once I get the optimization problem into the form of (2), then I can use the fact that it is separable to solve it (see Example 5.4 in Ref. 1). However, I would need my transformation from (1) to (2) to be valid.
Some Additional Questions:
- What is the class of problems called where there are multiple min/max statements? Such as $\min_{x} \ \min_{y} \ \cdots$.
- From slide 4.33 of Ref. 2, I know that we can change a maximization problem of a concave function to a minimization problem by taking the negative of the concave objective function. This makes sense, but the objective function value in the "transformed" problem does not equal the objective function value in the original problem. For example, $\max_x \ \left\{-x^2 + 1\right\} \neq \min_x \ \left\{x^2 - 1\right\}$. For the two objective functions to be equal, we would need to use $-\min_{\mathbf{x}} \left( -f(\mathbf{x}) \right) = \max_{\mathbf{x}} f(\mathbf{x})$. I'm confused about when I need to take the negative of the objective function value. I know that in the example I just gave, the two prolbmes have the same optimal value, $x^\star$, but they have different objective function values.
Thank you for any and all help!
Some references:
- Convex Optimization (Example 5.4, pg. 248), Boyd and Vandenberghe
- These Convex Optimization slides (slide 4.33)
- These notes on optimization function decomposition
- These additional notes on decomposition
- This Math.SE post