1

I am implementing a projected gradient ascent technique. I suspect that the projection is computable in closed form but I am not able to derive it.

The projection can be formulated as

$$ \min_x \|x - x_0\| $$

$$\text{s.t.}\quad x^\intercal B x \leq k .$$

where $x \in \mathbb{R}^n$ and $B$ is an invertible matrix.

The Lagrangian is

$$\mathcal{L}(x,\lambda) = (x-x_0)^\intercal(x-x_0) + \lambda (x^\intercal Bx - k)$$,

hence, we have

$$\nabla_x \mathcal{L}(x,\lambda) = 0 \implies x = (I + \lambda B)^{-1}x_0$$ and

$$\frac{\mathrm{d}}{\mathrm{d}\lambda} \mathcal{L}(x,\lambda) = 0 \implies x^\intercal B x = k$$.

This leads to the following equation

$$x_0^\intercal(I + \lambda B)^{-\intercal} B (I + \lambda B)^{-1}x_0 = k$$.

The problem is that I cannot find an analytical solution for $\lambda$... I tried with the Woodburg identity (in my problem $B$ can be seen as $CC^\intercal$).

Sam
  • 357
  • 1
    Just a comment, in order $x^{\text{T}}Bx\le k$ to define a bounded convex set, it is not sufficient that $B$ is invertible, it must be positive definite. – Vítězslav Štembera Dec 15 '21 at 21:48
  • 1
    If you don't want to compute this projection numerically, it might be better to use a different optimization algorithm (such as ADMM / Douglas-Rachford or Chambolle-Pock) which avoids the need to compute this projection entirely. – littleO Dec 15 '21 at 22:32
  • 1
    If $B$ is rank one, then you can a closed-form solution. However, rank $> 1$, one has to find a solution numerically (or using an iterative algorithm such as ADMM / Douglas-Rachford as suggested by littleO). – user550103 Dec 16 '21 at 15:48

1 Answers1

2

If $C$ is invertible, then $B=CC^{\text{T}}$ is positive definite. Then the problem is equivalent to the point-to-ellipse projection in $\mathbb{R}^n$. Your calculation seems to be fine, however it seems that there is no analytical formula for this problem, see for example https://tcg.mae.cornell.edu/pubs/Pope_FDA_08.pdf, Chapter 8, where the same problem is solved only numerically.

Vítězslav Štembera
  • 2,213
  • 1
    Okay, at least now I know that there is no analytical solution! Numerical methods will work :). – Sam Dec 15 '21 at 22:44