# Solving a One Dimensional Problem with Interpolation of Vectors

I have the following optimization problem.

$$\operatorname*{argmax}_{w} \|(1-w)\boldsymbol{X} -w\boldsymbol{Y}\|^2 \\ s.t. \quad 0<w<1$$

How can I find the solution of this problem? May be can I apply gradient descent?

$J = \|(1-w)X -wY\|^2 + \mu (w-1)+\lambda w\\\frac{\partial J}{\partial w} = 0$

Is it correct? should I use $\lambda \quad \text{and} \quad \mu$ ?

$X$ and $Y$ are known, one dimensional vectors, their values are bounded in a known range.

• Please provide more context about $X$ and $Y$, where they are living, what size, etc. Furthermore this looks like a second degree polynomial in $w$ which could be solved in closed form.
– Surb
Aug 13, 2014 at 10:37
• So dont I need any gradient descent? If it closed form how can I solve it? (I am not very familiar with optimization) Could you please provide me more information. Aug 13, 2014 at 10:41
• Do $\| \cdot \|$ means the euclidian $2$-norm?
– Surb
Aug 13, 2014 at 10:44
• It is just absolute value. (I am not sure whether it should be just brackets. I need to find w such that the weighted difference between the two vectors X and Y should me maximized.) Aug 13, 2014 at 10:47
• Expand the objective function using FOIL, and you'll see you have a quadratic function of $w$, which you must maximize over an interval. Just graph the parabola. Aug 13, 2014 at 10:59

Since $X,Y \in \mathbb{R}$, we can restate your problem as $$w^* :=\arg \max_{0\leq w\leq 1} (a+bw)^2$$ where $a = X$ and $b = -(X+Y)$. Now, with $f(w) = (a+bw)^2$, we now that this convex parabola has a zero at $-\frac{a}{b}$ (where the minimum is reached). So we want to go the further as possible from the minimum. Therefore we have $$w^* = 1 \quad \text{ if } -\frac{b}{a}\leq\frac{1}{2},\quad \text{ and } \quad w^* = 0 \quad \text{ if } -\frac{b}{a}>\frac{1}{2}.$$ See the figure below to get a better intuition.

In blue $-\frac{b}{a} \leq \frac{1}{2}$ and in red $-\frac{b}{a} \geq \frac{1}{2}$.

• More simply, the solution is $w=0$ or $w=1$ depending on which of $\mathbf X^2$ and $\mathbf Y^2$ is the largest.
– user65203
Aug 13, 2014 at 11:21
• Hi I have one problem here. I need only one w which maximizes the sum of the differences between the weighted vectors. $argmax_i\sum_i |(1-w)X_i - wY_i|$ Aug 13, 2014 at 11:32
• @user570593 Note that if $X,Y$ are vectors then for $A = X, B=-(X+Y),$ we have $f(w) = \|A+Bw\|_2^2 = \langle A+Bw,A+wB \rangle = w^2 \|B\|_2^2 + 2w \langle A,B \rangle + \|A\|_2^2 = \alpha w^2 +\beta x + \gamma$. Again this is a convex parabola, so just check which of $w=0$ or $w=1$ is the best. Things that you can do by hand also :), finding if the zero of $f$ is at the left or the right of 1/2. Now if $\|\cdot \|$ is the $1$-norm (like in your comment), you should maybe post a new question (because it's very different).
– Surb
Aug 13, 2014 at 12:11

The objective function is a quadratic function of $w$, as can be seen using FOIL. The graph of this quadratic function is a parabola that opens upwards. The maximum value of this quadratic function over $[0,1]$ must occur either at $w = 0$ or $w = 1$. So just check those two possibilities.