I am interested in the linear least square problem with the solution with the following constraints :
$$
\begin{alignat*}{3}
\arg \min_{x} & \quad & \frac{1}{2} \left\| A x – b \right\|_{2}^{2} \\
\text{subject to} & \quad & \boldsymbol{1}^{T} x = 1 \\
& \quad & {x}_{i} \in \left[ 0, 1 \right], \; \forall i
\end{alignat*}
$$
Because of the second constraint, we know the optimal $x$ should lie in the convex region (simplex) whose vertices are the rows of the identity matrix $I_n$. I wanted to try an iterative algorithm where I start off with the $n$ points, namely the rows of $I_n$, compute the costs at each of these $n$ points, and then contract the convex region somehow, so as to reduce the volume, but still retain the optimal point(s). So I am looking for a set of rules that I can use to contract the convex region. For instance, I could compute the cost at the centroid of these $n$ points, and perhaps, replace the worst cost point with the centroid. That probably doesn't even guarantee convexity of the resulting region. So what are the set of rules that I can use that guarantee convexity, retains the optimal region, reduces the volume (possibly by a lot), and after a few iterations, results in a zero volume region (or a very very small region) that I can just pick the optimal point from?
Best Answer
Observing that in the context of the problem the following 2 problems are equivalent:
Problem 001
$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & \boldsymbol{1}^{T} x = 1 \\ & \quad & {x}_{i} \in \left[ 0, 1 \right], \; \forall i \end{alignat*} $$
Problem 002
$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & \boldsymbol{1}^{T} x = 1 \\ & \quad & x \succeq 0 \end{alignat*} $$
The second one is basically Least Squares constrained to the Unit Simplex.
There is no closed form solution to that but it can be solved using Projected Gradient Descent.
The reason is that there efficient techniques to project onto the Simplex.
For a full solution you can find in my answer to Least Squares with Unit Simplex Constraint.