1
$\begingroup$

Consider the unconstrained programming problem with a high-dimensional, smooth function $f(x_1,x_2,\ldots x_N)$.

Because $N$ is large, such kind of heuristics is sometimes used:

-- Fix $x_2…x_N$ to 0, and minimize $x_1\rightarrow f(x1, 0, 0,..0)$. Suppose this step happens to get the true minimum point $x_1^*$.

-- Fix $x_3,….X_N$ to 0, and minimize $x_2\rightarrow f(x_1^*, x_2, 0,..0)$. Suppose this step happens to get the true minimum point $x_2^*$.

-- Eventually, after $x_1^*, ….x_{N-1}^*$ are calculated, we can get $x_N^*$.

My question is: under which condition does $(x_1^*,x_2^*…x_N^*)$ coincide with a global minimum point of $f$?

$\endgroup$

1 Answer 1

3
$\begingroup$

The simplest case that I can think of is: $$ f(X) = \sum_ig_i(x_i) $$ where $X=\{x_1, x_2, ..., x_N\}$. That is, the function $f(X)$ is a sum of independent functions of the $x_i$'s. You can see intuitively why this meets your criteria, because the only way for the sum to be minimal is if all the individual terms are also at their minimum. If one term could be reduced further, then that would decrease the sum, so we wouldn't be at the minimum. Thus, minimizing the composite function is equivalent to minimizing the individual components separately.

Formally, you can work it out by noting that at the minimum of a function, its derivative is equal to 0, and the derivative of a sum of functions is equal to the sum of the derivatives, i.e.: $$ \frac{\delta f(X)}{\delta x_i}=\sum_j\frac{\delta g_j(x_j)}{\delta x_i} $$ Since only the $i$-th function actually depends on $x_i$, all derivatives where $j\neq i$ are 0, such that the expression simplifies to: $$ \frac{\delta f(X)}{\delta x_i}=\frac{d g_i(x_i)}{d x_i} $$ and thus: $$ \frac{\delta f(X)}{\delta x_i}=0 \iff \frac{d g_i(x_i)}{d x_i}=0 $$ which means that the derivative of $f(X)$ is 0 if and only if we find the $x_i$'s for which the derivatives of each of the component functions $g_i(x_i)$ are 0, which we can do separately for each component function because each only depends on its own $x_i$.

Note that I'm assuming here that the component functions $g_i(x_i)$ have a single unique minimum. If one of the components has multiple local minima, then those are also local minima of $f(X)$, and so the solution the algorithm finds may be not be the global minimum.

$\endgroup$
3
  • 3
    $\begingroup$ This is a reasonable observation. It may be of interest to note that you can use this solution to demonstrate it is only a very special case: given the $g_j$, each with a global minimum value of $\gamma_j$, just consider $$f(x_1,\ldots,x_N)=\sum_{j=1}^N g_j(x_j)+\left(\prod_{j=1}^N (g_j(x_j)-\gamma_j)\right)^2.$$This cannot be expressed as a linear combination of functions of single variables, but it too enjoys the same property that one cycle of univariate minimizations takes you to the global minimum. $\endgroup$
    – whuber
    Dec 13, 2017 at 15:30
  • $\begingroup$ It also works with $f(X)=\prod_i g_i(x_i)$, iff each function $g_i(x_i)$ is strictly greater than 0, or strictly less than 0 (and we keep the condition that there are no local minima). In that case you have $\frac{df(X)}{dx_i}=\frac{dg_i(x_i)}{dx_i}\prod_{j\neq i}g_j(x_j)$, which can only be 0 if $\frac{dg_i(x_i)}{dx_i}=0$ (as we stipulated that $g_j(x_j)\neq0$). A common example of this is a product of independent Gaussians (i.e. a multivariate Gaussian with a diagonal covariance matrix). $\endgroup$ Dec 13, 2017 at 16:30
  • $\begingroup$ Yes, but the product is not intrinsically different than the sum, because the logarithm converts the product to a sum. The example I gave cannot generally be converted to a sum under any transformation, and so is of an inherently different nature. $\endgroup$
    – whuber
    Dec 13, 2017 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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