2

Imagine that:

$\vec{v}$ $\in$ {non-negative vector in $R^N$, such that $||\vec{v}||_1 = 1$ and $v_0 = v_N = 0$}.

We define a function on that space:

$f(\vec{v}) = \sum_{i=1}^{N}(v_i - v_{i-1})^2$

Question: What form should $\vec{v}$ take to minimize $f(\vec{v})$?

Any help would be greatly appreciated!

Remarks

  • $v_i$ stands for $i^{th}$ element of vector $\vec{v}$
  • By non-negative I mean that $\{\forall i: v_i \geq 0\}$
Novinator
  • 25
  • This is an interesting question. Based on intuition, I'd guess that $v$ should look like a plucked string. – littleO Apr 11 '21 at 07:55
  • @RicardoCavalcanti By non-negative - I mean that every element $v_i$ of the vector should be greater or equal to 0 – Novinator Apr 11 '21 at 12:25
  • @littleO Yeah like a centered plucked string - that is my intuition as well. The question now is how to prove it? LoL Also just ran a simulation using the cartesian product over $N=10$ and the minimum was found when the weights were all equal to each other and equal to $w_i = \frac{1}{N}$. Just FYI – Novinator Apr 11 '21 at 12:41

1 Answers1

0

If by non-negative vector you mean an element-wise concept, you can transform the constraint of unit 1-norm into a simple summation as $$ \sum_{i=1}^{N-1}v_i=1. $$ Hereafter, the Lagrange's multipliers method would work perfectly.

Mostafa Ayaz
  • 31,924
  • Yeah, that makes sense! However in the addition to unitary norm constrain - the inequalities for every $v_i \geq 0$ and for $j \in (0, N)$ $v_j = 0$ create a another layer of restrictions. Seems like Karush–Kuhn–Tucker might be the way to go - but not 100% sure... Let me know what you think! – Novinator Apr 11 '21 at 13:04
  • Yep, your observation is right. You can remove the $v_0$ and $v_N$ from your objective function and your constraints to make it as simple as possible and then apply the KKT method. – Mostafa Ayaz Apr 11 '21 at 14:22
  • Alright - yeah you are right - this was probably the easiest route to go! This solved it! Thank you! – Novinator Apr 11 '21 at 16:21
  • I'm happy I could help. Good luck! – Mostafa Ayaz Apr 11 '21 at 16:37