2
$\begingroup$

This is a refinement of the question Minimal representation of element in convex hull of $v_1,...,v_n\in\mathbb{R}^n$

Let $C$ a convex polyhedron in $\mathbb{R}^n$ and $v_1,..,v_k$ its extreme points and $x\in C$. Is there always a unique minimal representation of $x$ with respect to $v_1,...,v_k$ in $||.||_2$ the euclidean norm in the sense that, there is a unique $t=(t_1,...,t_k)\in[0,1]^k$ with $$x = \sum_i t_iv_i$$ and $||t||_2^2$ minimal over $[0,1]^n$? Seen through the lense of optimization, this transforms to the problem with $n+1$ linear constraints $$\min_{t_1,...,t_k\in[0,1]^k}\sum_{i} t_i^2$$ $$x = \sum_i t_iv_i$$ $$\sum_i t_i=1$$

Since $x\in C$, the feasible set of the problem is not empty and, therefore, by standard theory of convex optimization, such a $t\in[0,1]^k$ exists. But can I ensure uniqueness? I should get a global minimum for the $t$, so either a second $t'$ would attain the same value or there is none. By a feeling, everything here looks like a parabola, so there should be no second $t'$ but I am stuck how to show it.

$\endgroup$
4
  • 2
    $\begingroup$ you should add the condition $\sum_i t_i=1$. $\endgroup$ Commented Oct 23 at 17:45
  • $\begingroup$ Yes, definitely, thank you $\endgroup$ Commented Oct 23 at 19:21
  • $\begingroup$ Can the $v_i$ be contained in an $n-1$-plane? Or are they in general position? And is it intentional that the number of points is the same as the dimension? $\endgroup$ Commented Oct 23 at 19:36
  • $\begingroup$ Oh, no, the number of points and the dimension do not need to be the same. I adjust it $\endgroup$ Commented Oct 24 at 3:50

1 Answer 1

2
$\begingroup$

Yes, the solution of this problem exists and is unique: you minimize a strictly convex function on a closed convex set.

$\endgroup$
3
  • $\begingroup$ Does the point x have to be strictly interior, i.e. not on the boundary of the polyhedron? $\endgroup$ Commented Oct 23 at 21:03
  • $\begingroup$ @Alex No conditions, $x$ in the convex hull of those $v_i$ is enough, since then the minimization problem has feasible points. The uniqueness of solutions is a convexity argument. $\endgroup$ Commented Oct 24 at 6:16
  • $\begingroup$ @dawI deleted my counterexample, after I saw your smaller norm solution. $\endgroup$ Commented Oct 24 at 18:53

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.