Free software or algorithm for Second-Order Cone Program

Question

I need to solve the following optimization problem:

$$ \mathbf{x}^\ast = \operatorname{argmin}_{\mathbf{x}} \Vert \mathbf{Rx} \Vert_2^2 \;\;\; \mathrm{s.t.} \;\;\; \mathbf{s}^\mathrm{H} \mathbf{x} = 1 \wedge \Vert \mathbf{x} \Vert_2 \leq \delta, $$

where $\mathbf{x}, \mathbf{s} \in \mathbb{C}^N$ and $\mathbf{R}\in\mathbb{C}^{M \times N}$.

The problem I am running into is one of size, viz. $\mathbf{R}$ is huge and cannot be stored in memory as required by free solvers like CVX. I am trying to understand the documentation for the underlying solver that CVX uses (SDPT3) but am struggling to make sense of its generality (it tries to be all things to all users) and do not even know if calling it directly will allow me to bypass the memory problems.

If anyone knows of a freely available solver that is relatively easy to use and will allow one to define the linear transform as a function pointer rather than a matrix stored in memory, I'd greatly appreciate the response. Also, if there is a well suited algorithm that I could code up myself, I'd greatly appreciate that as well.

Answer 1

I am the author of CVX, and I have no difficulty admitting that it is ill-suited for your problem!

I would suggest that instead you consider a projected gradient method. This involves repeated iterations of two steps: first, take a step along the gradient of the objective function; and second, project that result back onto the feasible set.

The gradient step is straightforward. If $f(x)=\|Rx\|_2^2$, then $\nabla f(x)=2R^TRx$, so $$ x^{+} = x - 2 \alpha R^TR x = ( I - 2 \alpha R^T R ) x. $$ The quantity $\alpha\in(0,1]$ is a step size that you will want to adjust at each iteration according to some sort of backtracking criterion, like an Armijo-Goldstein condition.

Now, obviously, an unconstrained gradient step is likely to make $x^{+}$ infeasible, hence the need for the second step: a projection $$ x = \mathop{\textrm{arg min}}_{z:s^Hz=1,\,\|z\|_2\leq \delta} \| z - x^{+} \|_2. $$ What I would do here is express this problem as follows: $$\begin{array}{ll}\text{minimize}_z & \|z-x^{+}\|_2^2 \\ \text{subject to} & s^H z = 1 \\ & \|z\|_2^2 \leq \delta^2 \end{array}$$ Then I would employ a Lagrange multiplier approach to solve the problem. I'm not sure there is an analytic solution, but with only two Lagrange multipliers, it should not be difficult to construct a heuristic approach that works great. (EDIT: to be clear, when I say "heuristic", I do not mean "approximate". I am confident that you can find a result that is exact to within reasonable precision, but you may need to employ an iterative approach to get there.)