Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

That was my great trouble? Please help me to know this. Thanks in advance.

share|improve this question
    
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 at 22:46

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Please check $(1)$ in your answer, I don't know how to inply $(1)$. Can you make it more clearly! Thanks. –  Richkent Apr 5 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 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 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 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 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.

share|improve this answer
    
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 at 17:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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