2
$\begingroup$

I need to find the projection $x \in \mathbb{R}^{k}$ of a vector $z \in \mathbb{R}^{k}$ on the set defined by $Y \cdot x \geq 0$ where $Y$ is a (given but no specific property) matrix of size $m \cdot k$.

I first build the Lagrangian as follows :

$$L=\frac{1}{2} ||x-z||^2 -\sum_{i=1}^m \lambda_i Y(i,:)x$$ and set its gradient w.r.t. $x$ to $0$ which leads to $$x=z+\sum_{i=1}^m \lambda_i Y(i,:)^T$$

The inequality constraints add an additional KKT condition :

$$\lambda_i \cdot Y(i,:)x=0 \; \forall i=1,...,m$$

Replacing $x$ inside gives $$\lambda_i \cdot Y(i,:)[z+\sum_{i=1}^m \lambda_i Y(i,:)^T]=0 \; \forall i=1,...,m$$

It is where it becomes harder for me. I guess that either $\lambda_i$ or $Y(i,:)[z+\sum_{i=1}^m \lambda_i Y(i,:)^T]$ should be equal to $0$ but then I am stuck. Indeed, the second condition is a scalar product linking all the $\lambda_i$ and I don't know how to deal with it properly.

Any help appreciated

$\endgroup$

1 Answer 1

1
$\begingroup$

Unlike textbook examples, most optimization problems don't have closed form solutions for the KKT conditions. I believe the inequality constraint renders this such a case.

The projection you seek can be found as the solution of the convex optimization problem:

min $\|x - z\|_p$ w.r.t. $x$, subject to $Yx \ge 0$.

for some specified value of $p$.

If the 1 or infinity norms are chosen, this becomes and can be solved as a Linear Programming (LP) problem.

If the 2 norm is chosen, which I guess is what you want, this can be written and solved (squaring the objective function and ignoring the constant term) as a convex linear inequality-constrained Quadratic Programming (QP) problem:

min $x^Tx - 2x^Tz$ w.r.t. $x$, subject to $Yx \ge 0$.

This can be formulated and solved in CVX, for any specified p norm, $p \ge 1$ as:

cvx_begin
variable x(n)
minimize(norm(x - z),p))
Y*x >= 0
cvx_end

Just for for fun, if you want to minimize the number of components in the "projection" which are not exact fits (i.e., for which $x_i \ne z_i$), choose p = 0 (not a true norm). But this would be a non-convex combinatorial problem, and CVX could not by used as above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .