Optimal solution to non-linear program

Question

Find an optimal solution to the following problem:

$$\min_{x\in \mathbb{R}^n} \sum_{i=1}^{n}\frac{1}{2}(x_i-1)^2$$ $$\text{s.t. } x\ge0 \text{ and } \sum_{i=1}^{n}x_i=1.$$

Answer 1

If we let $e=(1,...,1)$ the the problem becomes $\min_{e^T x = 1, x \ge 0 } { 1\over 2} \|x-e\|^2$ which we can see is projecting the point $e$ onto the simplex.

One nice characteristic of this problem is that it is convex, and first order conditions are necessary and sufficient.

One approach is to solve a more relaxed problem and if this is a solution then it solves the more constrained problem.

Solving $\min_{e^T x = 1 } { 1\over 2} \|x-e\|^2$ gives $(x-e) + \lambda e = 0$, or $x=(1-\lambda) e$ and from the constraint we have $e^T x = 1 = (1-\lambda) e^T e = n (1-\lambda)$ and so $(1-\lambda) = {1 \over n}$ which gives $x = {1 \over n} e$. Since $x>0$ this solves the original problem.

Answer 2

First, to answer your question regarding $\lambda_i = 0 \ \forall i$, I would suggest a simpler argument, as follows.

Assume that $\lambda_i > 0$ for some $i$, then $$x_i=0\implies\mu-1=-\lambda_1< 0\implies x_j-\lambda_j<0\forall j \implies \lambda_j > 0\ \forall j \implies x_j=0\ \forall j,$$ which is of course not feasible.

Second, there's a simple and elementary proof for the problem in the question. Notice that $(x_i-1/n)^2 \ge 0$, we have that $x_i^2 \ge ax_i+b$ for some $a,b$. Sum up this inequality for all $i$ we see that the objective function in the equation is no smaller than a constant, with equality iff $x_i=1/n\ \forall i$.