0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Perhaps I was not clear on the constraints. $0 \le x_i \le 1$ and $\Sigma_i^n=1$ are all constraints on the components of $x$. Basically I want the L1 norm of the solution to be exactly 1. $\endgroup$ – keveman Sep 16 '14 at 20:15
  • 1
    $\begingroup$ Just curious, but is there a reason why you don't want to use a standard method like projected gradient descent? $\endgroup$ – p.s. Sep 17 '14 at 0:46
  • 1
    $\begingroup$ Yes, I'd have the same question. Projected gradient descent wouldn't necessarily be my immediate thought here; I'd take advantage of the constant Hessian if I can. But an active set or simplex-inspired method comes to mind. And of course there are a variety of off-the-shelf general purpose algorithms and codes out there to solve this, so why reinvent the wheel? $\endgroup$ – Michael Grant Sep 17 '14 at 1:13
  • 1
    $\begingroup$ If I am not wrong there are specialized algorithms due to Kiwiel. Check it searching for "kiwiel knapsack". $\endgroup$ – AndreaCassioli Sep 17 '14 at 8:45
  • $\begingroup$ @AndreaCassioli, Are you talking about Variable Fixing Algorithms for the Continuous Quadratic Knapsack Problem? $\endgroup$ – Royi Feb 25 '20 at 6:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.