1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Surb
    Aug 13, 2014 at 10:37
  • $\begingroup$ 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. $\endgroup$
    – user570593
    Aug 13, 2014 at 10:41
  • $\begingroup$ Do $\| \cdot \|$ means the euclidian $2$-norm? $\endgroup$
    – Surb
    Aug 13, 2014 at 10:44
  • $\begingroup$ 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.) $\endgroup$
    – user570593
    Aug 13, 2014 at 10:47
  • $\begingroup$ 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. $\endgroup$
    – littleO
    Aug 13, 2014 at 10:59

2 Answers 2

3
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • 1
    $\begingroup$ More simply, the solution is $w=0$ or $w=1$ depending on which of $\mathbf X^2$ and $\mathbf Y^2$ is the largest. $\endgroup$
    – user65203
    Aug 13, 2014 at 11:21
  • $\begingroup$ 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|$ $\endgroup$
    – user570593
    Aug 13, 2014 at 11:32
  • $\begingroup$ @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). $\endgroup$
    – Surb
    Aug 13, 2014 at 12:11
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .