# Taylor expansion at infinity and optimal value at infinity of a function.

Given a function $f(x)$ that we need to minimize on the hold space, i.e., $$\mbox{minimize} \;\; f(x):\;\;\; \mbox{subject to }\; x\in X.$$ Suppose this function is bounded, i.e., $|f(x)|\leq \gamma$ for all $x\in X$ for some $\gamma$. I would like to find the optimal value of $f$ at infinity. i.e., among all directions we can choose to tend to infinity, which directions make the value of $f$ is minimal. The value of $f$ when $\|x\|\to +\infty$ in such a direction is called the optimal value at infinity.

Now consider the function $f(x)=\sum_{i=1}^pw_i \|x-a_i\|$ with $\sum_{i=1}^p w_i=0$. To find the optimal value of $f$ at infinity, I utilize the Taylor expansion at a point $x$ with $\|x\|$ is very large, we call $x$ is at infinity.

Define $\varphi(x)=\|x\|$. The gradient and Hessian of $\varphi$ at every $x\neq 0$ are given by $$\nabla \varphi(x) = \frac{x}{\|x\|} \;\; \mbox{ and }\; \; \nabla^2\varphi(x) = \frac{1}{\|x\|^3}\left(\|x\|^2I - xx^{T}\right).$$

Using three terms of Taylor expansion of $\varphi$ we can approximate $$\varphi(x-a)\approx \varphi(x)- \langle \nabla\varphi(x), a\rangle + \frac{1}{2}\langle \nabla^2\varphi(x)a, a\rangle.$$ This means

$$\|x-a\| \approx \|x\| - \langle \frac{x}{\|x\|}, a \rangle + \frac{1}{2} \langle \dfrac{\|x\|^2I - xx^{T}}{\|x\|^3}a, a\rangle$$

$$\; \; \; \approx \|x\| -\langle \frac{x}{\|x\|}, a \rangle + \frac{1}{2}(\dfrac{\|a\|^2}{\|x\|} - \dfrac{|\langle x, a\rangle|^2}{\|x\|^3})$$

Since $|\langle x, a\rangle|^2 \leq \|x\|^2 \|a\|^2$ by Cauchy-Schwarz inequality, when $\|x\|$ is large, the last two terms can be ignored and we have $$\|x-a\| \approx \|x\| -\bigg\langle \frac{x}{\|x\|}, a\bigg \rangle.$$

Thus, the value of $f(x)$ for a large $\|x\|$ is approximately:

$$\sum_{i=1}^p w_i \|x\| - \langle \frac{x}{\|x\|}, \sum_{i=1}^p w_ia_i\rangle$$

Since $\sum_{i=1}^p w_i=0$, the solution at infinity is obtained by maximizing $\langle \frac{x}{\|x\|}, \sum_{i=1}^p w_ia_i\rangle$, the Cauchy-Schwarz give us

$$\langle \frac{x}{\|x\|}, \sum_{i=1}^p w_ia_i\rangle \leq \|\sum_{i=1}^p w_ia_i\|.$$

The equality holds if $x=t\sum_{i=1}^p w_ia_i, \; t>0$. And I can conclude that the optimal value of $f$ at infinity is $-\|\sum_{i=1}^p w_ia_i\|$ when $x$ tends to infinity along with the direction $v=\sum_{i=1}^p w_ia_i$.

I wonder whether my argument as above is correct or not? The main key is that: In Taylor expansion, $f(x+h)=\ldots$, $x$ is often at finite, $h$ is near $0$ to ensure that $x+h$ is belongs to a small enough neighborhood of $x$. But my point $x$ is at infinity and the points $a_i$ is at finite?

-
Your idea is correct, but to add some rigor, it would be nice to use big-O estimates, as in my answer. – robjohn Apr 4 '14 at 22:46

Assuming $\frac{|a_i|}{|x|}\le\epsilon$ and since $|x-a_i|^2=|x|^2-2x\cdot a_i+|a_i|^2$, we have that $$|x-a_i|=|x|\left(1-\frac{x\cdot a_i}{|x|^2}+O\left(\epsilon^2\right)\right)\tag{1}$$ If we set $\bar{w}=\sum\limits_{i=1}^p|w_i|$ and $\bar{a}=\sum\limits_{i=1}^pw_ia_i$, then $(1)$ yields \begin{align} f(x) &=\sum_{i=1}^pw_i|x-a_i|\\ &=-\frac{x}{|x|}\cdot\bar{a}+|x|\bar{w}\,O\left(\epsilon^2\right)\tag{2} \end{align} Thus, the optimal value of $f$ is $-|\bar{a}|$ achieved in the direction of $\bar{a}$.

-
Please check $(1)$ in your answer, I don't know how to inply $(1)$. Can you make it more clearly! Thanks. – Richkent Apr 5 '14 at 3:11
@Richkent: The taylor series for $(1-x)^{1/2}=1-\frac12x+O(x^2)$, so \begin{align}\left(|x|^2-2x\cdot a_i+|a_i|^2\right)^{1/2} &=|x|\left(1-\frac{2x\cdot a_i}{|x|^2}+\frac{|a_i|^2}{|x|^2}\right)^{1/2}\\ &=|x|\left(1-\frac{x\cdot a_i}{|x|^2}+O\left(\epsilon^2\right)\right)\end{align} – robjohn Apr 5 '14 at 4:15
May be I've never used the big O notation, so I'm very embarrassed to do with it. What happens when we multiply $O(\epsilon^2)$ to a negative number. Why in your answer, you take the absolute values of $w_i$ to form $\bar{w}$, in my thinking, they doesn't change sign. – Richkent Apr 5 '14 at 6:39
@Richkent: $f(x)=O(g(x))$ as $|x|\to\infty$ means that there is a constant, $C$, so that for $|x|$ large enough, $|f(x)|\le g(x)$. Thus, if $f(x)=O\left(\epsilon^2\right)$, then $-f(x)=O\left(\epsilon^2\right)$. Read more here. – robjohn Apr 5 '14 at 6:54
If $\|x-a_i\| = \|x\|-\frac{\langle x, a_i\rangle}{\|x\|} + \|x\|O(\epsilon^2)$ then $-2\|x-a_i\| = -2\|x\|-\frac{\langle x, -2 a_i\rangle}{\|x\|} -2 \|x\|O(\epsilon^2)$. Then I take sum all these equalities, and $\bar{w}$ in your answer must $\sum w_i$. Ofcouser your are right, I'm wrong. But I don't know why we must take absolute value there. Thanks again. – Richkent Apr 5 '14 at 7:04

A Taylor series is difficult and may be overkill. There is a simpler method that I see using the reverse triangle inequality: $$|\,\|x\|-\|y\|\,| \le \|x-y\|$$ For example, $$|\,\|x-a\|-\|x-b\|\,| \le \|(x-a)-(x-b)\|=\|b-a\|.$$ Because your weights add up to 0, you should be able to regroup with some effort. For example, \begin{align} |\,\|x-a\|+\|x-b\|-2\|x-c\|\,| & \le |\,\|x-a\|-\|x-c\|\,|+|\,\|x-b\|-\|x-c\|\,| \\ & \le \|a-c\|+\|b-c\|. \end{align} I don't think I've said anything wrong, but I am prone to idiotic mistakes. The trick is to rearrange the bits until you can do what is suggested in this last step.

-
I would like to find the optimal value of $f$ at infinity. i.e., among all directions we can choose to tend to infinity, which directions make the value of $f$ is minimal. Your hint just proved that $f(x)\geq -\|\sum_{i=1}^pw_ia_i\|$. You must show that there exists a sequence $x_k$ tend to infinity and $f(x_k)$ tend to $-\|\sum_{i=1}^pw_ia_i\|$. How to prove this limit with the direction $v$ as I have shown above, i.e., with $x_k= k(\sum_{i=1}^p w_i a_i)$. My question is: That using Taylor expansion as above is right or wrong? And why? – Richkent Apr 4 '14 at 17:00