# About the “Optimizing over some variables” in Boyd's book.

Boyd says in his book [convex optimization,Ch 4.1.3] that "we can always minimize a function by first minimizing over some of the variables, and then minimizing over the remaining ones."

For example, $\mathop {\min }\limits_{ x_1}\mathop {\min }\limits_{x_2}f(x_1,x_2)=\mathop {\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 like this $\mathop {\min }\limits_{ x_1}\mathop {\min }\limits_{x_2}\cdots\mathop {\min }\limits_{x_K}f(x_1,x_2,\cdots,x_K)=\mathop {\min }\limits_{ x_1,x_2,\cdots,x_K}f(x_1,x_2,\cdots,x_K)$?

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...

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.

• Thank you. By the way, can I say that $f_1$ is only the function of $x_1$? A – Dave Jul 10 '17 at 12:58
• @Dave yes, you can – Red shoes Jul 14 '17 at 3:17

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.