0

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:

  1. What is the class of problems called where there are multiple min/max statements? Such as $\min_{x} \ \min_{y} \ \cdots$.
  2. 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
jmd
  • 57
  • For fixed $x$, the constraint implies that $y=-x$, so the problem reduces to $\max_x \left(-f(x)+g(-x)\right)$, which is equivalent to $-\min_x \left(f(x)-g(-x)\right)$. – RobPratt Dec 23 '23 at 03:26
  • Hi @RobPratt thank you for your response. The transformation you suggested is great! I have two quick follow-up questions. (1) I understand that $-\min_{\mathbf{x}}\left(-h(\mathbf{x})\right)=\max_{\mathbf{x}}h(\mathbf{x})$, but I'm confused about how that corresponds to things like slide 4.33 in these notes, where they say that the optimization problem is equivalent without the leading negative sign on the entire expression. – jmd Dec 23 '23 at 16:07
  • (2) Just for future reference: if there wasn't the equality constraint in the original problem $\mathbf{x} + \mathbf{y} = 0$, then would you just apply the max and min operations to the two distinct parts of the expression? So would $\max_{\mathbf{x}} \ \min_{\mathbf{y}} \ -f(\mathbf{x}) + g(\mathbf{y})$ become $\max_{\mathbf{x}} \ \left( -f(\mathbf{x})\right) + \min_{\mathbf{y}} \ \left(g(\mathbf{y})\right)$? Thank you so much for your help! – jmd Dec 23 '23 at 16:10
  • 1
    "Equivalent" means the two problems have the same set of optimal solutions. The leading negative sign is just to recover the optimal objective value of the original problem. – RobPratt Dec 23 '23 at 16:11
  • 1
    Yes, without the constraints, the problem would be separable by $x$ and $y$. – RobPratt Dec 23 '23 at 16:14
  • Thank you very much @RobPratt! – jmd Dec 23 '23 at 16:16

0 Answers0