Optimization of a function of two variables.

Question

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant and convex in $\mathbf x$ when $\mathbf y$ is kept constant.

Can we then minimize with respect to $\mathbf x$ and $\mathbf y$ separately and find the solution to the initial problem?

Edit: $$g(y,x^*)= \text{min}_x f(x,y)$$ where $x^*$ is $$\text{argmin}_xf(x,y)$$ and $$y^*=\text{argmin}_yg(y,x^*),$$then can we say $$(x^*,y^*)=\text{argmin}_{x,y}f(x,y).$$

I would apriciate if someone can explain how this is true (if it is true) and also a reference where I can look it up, like an online note or a book. Thanks

Answer 1

This has nothing to do with convexity nor with the method used to determine minima; it is purely a matter of logic and order. It is with minimax problems that the real difficulties arise.

Note that your function $g$ depends only on the variable $y$. I'd argue as follows, neglecting questions of existence:

Given $$f:\quad X\times Y\to{\mathbb R},\qquad (x,y)\mapsto f(x,y)\ ,$$ put $$g(y):=\min_{x\in X} f(x,y)\quad(y\in Y)\ ,\qquad S(y):=\{x\in X\>|\>f(x,y)=g(y)\}\ .$$ The set $S(y)$ replaces your ${\rm argmin}_x f(x,y)$, and hopefully consists of only one point $x^*(y)\in X$.

Now we know on each " horizontal" $y={\rm const.}$ the minimal value taken by $f$ and the set of points where this minimal value is taken. We proceed to the second step: Put $$\mu:=\min_{y\in Y} g(y), \qquad T:=\{y\in Y\>|\>g(y)=\mu\}\ .$$ Then $\mu$ is the overall minimal value of $f$, and the set of $(x,y)$ where this value is taken is given by (check it!) $$f^{-1}(\mu)=\{(x,y)\>|\>y\in T, \ x\in S(y)\}\ .$$ When $S(y)=\{x^*(y)\}$ we have $g(y)=f\bigl(x^*(y),y\bigr)$, and when in the second step we find $T=\{y^*\}$, then $\mu=f\bigl(x^*(y^*),y^*\bigr)$, and we are allowed to write $${\rm argmin}\>f=\bigl(x^*(y^*),y^*\bigr)\ .$$

Edit: Side note concerning convexity with respect to several variables

In the situation considered by the OP the function $f$ is only separately convex in each of the two variables $x$ and $y$. In this case neither the function $f$ nor $g$ can be expected to be convex. Consider the example $$f(x,y):=x^2-4xy+y^2\ .$$ Then $f_{xx}=f_{yy}\equiv2$, so $f$ is convex in each of the two variables separately; but $$f(x,y)=(x-2y)^2-3y^2\tag{1}$$ shows that $f$ is not convex as a function of two variables. From $(1)$ we deduce $g(y)=-3y^2$, which certainly is not convex. (In this case $\inf_{y\in{\mathbb R}} g(y)=-\infty$; but I conjecture that one could cook an example of this kind with a finite minimum $\mu$.)

Answer 2

The above answer is correct but a little verbose. For all $(\mathbf{x}, \mathbf{y})$:

$$f (\mathbf{x}, \mathbf{y}) \ge \min_{\mathbf{y}} f(\mathbf{x}, \mathbf{y}) \ge \min_{\mathbf{x}} \min_{\mathbf{y}} f(\mathbf{x}, \mathbf{y}) \,.$$

Therefore, for any $(x^*, y^*)$ such that $$f(x^*, y^*) = \min_{\mathbf{x}} \min_{\mathbf{y}} f(\mathbf{x}, \mathbf{y})$$ we have that for all $(\mathbf{x}, \mathbf{y})$:

$$ f(\mathbf{x}, \mathbf{y}) \ge f(x^*, y^*) $$

so by definition $\DeclareMathOperator*{\argmin}{argmin}$

$$(x^*, y^*) \in \argmin_{\mathbf{x}, \mathbf{y}} f(\mathbf{x}, \mathbf{y}) \,.$$

Answer 3

The equality holds for every possible case whenever $x$ and $y$ are independent i.e.

\begin{equation}\label{eq:0} \min_{y}\min_{x} f(x,y) = \min_{x,y} f(x,y) \end{equation}

Proof: \begin{equation}\label{eq:1} f(x^*,y^*)=\min_{x,y}f(x,y) \leq \min_{y}\min_{x}f(x,y)\,\,(\text{this holds trivially})\tag{1} \end{equation} where $(x^*, y^*) = \text{argmin}_{x,y}f(x,y)$.

Now, \begin{equation}\label{eq:2} \min_y\min_x f(x,y) \leq \min_y f(x^*,y)\tag{2} \end{equation} because $\min_x f(x,y) \leq f(x^*, y) \, \forall y$

and also

\begin{equation}\label{eq:3} \min_y f(x^*,y) \leq f(x^*,y^*) \, \text{(holds trivially)}\tag{3} \end{equation}

Now $\eqref{eq:2}$ and $\eqref{eq:3}$ implies \begin{equation}\label{eq:4} \min_y\min_x f(x,y) \leq f(x^*,y^*)\tag{4} \end{equation}

Overall \eqref{eq:1} and \eqref{eq:4} implies \begin{equation} \min_{y}\min_{x} f(x,y) = \min_{x,y} f(x,y) \end{equation}

Please note that in this proof I haven't used any restrictions of convexity or smoothness. Thus the claim is true for all circumstances.