About "optimizing over some variables" in Boyd & Vandenberghe

Question

In section 4.1.3 of Convex Optimization, Boyd & Vandenberghe wrote the following:

we can always minimize a function by first minimizing over some of the variables, and then minimizing over the remaining ones.

For example,

$$\min\limits_{ x_1}\min\limits_{x_2}f(x_1,x_2) = \min\limits_{ x_1,x_2} f(x_1,x_2)$$

Then my questions are follows.

1. When I first handle $\mathop {\min }\limits_{x_2}f(x_1,x_2)$, how should I choose the value $x_1$? Any value?

2. If I have a problem with $K$ variables, then can I optimize the variables one by one as follows?

$$\min\limits_{ x_1}\min\limits_{x_2}\cdots\min \limits_{x_K} f(x_1, x_2, \cdots, x_K) = \min\limits_{x_1, x_2, \cdots, x_K} f(x_1, x_2, \cdots, x_K)$$

Answer 1

Let $h(x_1) := \mathop {\min }\limits_{x_2}f(x_1,x_2)$. I assumed by handling $\mathop {\min }\limits_{x_2}f(x_1,x_2)$ you meant finding the function $h$.

Now to minimize $f$ in both variable you only need minimize $h$. Let $x_1^*$ be minimizer of $h$ then you show that $h(x_1^*) = \mathop {\min }\limits_{x_1,x_2}f(x_1,x_2)$

Question $2$, similarly...

Answer 2

The point is: what happens when you partially minimize a function (i.e., with respect to a subset of the variables)? What you really obtain is a new function of the remaining variables. In your simple case you obtain

$$ f_1(x_1) = \min_{x_2} f(x_1, x_2). $$

Note that $f_1$ is only implicitly defined and does not have an analytical expression in general. Similarly, you can define

$$ f_2(x_2) = \min_{x_1} f(x_1, x_2), $$

and what the book really says is that

$$ \min_{x_1} f_1(x_1) = \min_{x_2} f_2(x_2) = \min_{x_1,x_2}f(x_1, x_2). $$

You can clearly generalize this to $K>2$ variables.

Answer 3

For your first question, you have to express $x_2$ in terms of $x_1$.

Yes, for your second question, however, you have to express $x_k$ in terms of $x_1, \ldots, x_{k-1}$ and so on.