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.

  • $\begingroup$ Thank you. By the way, can I say that $f_1$ is only the function of $x_1$? A $\endgroup$ – Dave Jul 10 '17 at 12:58
  • $\begingroup$ @Dave yes, you can $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.