1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ Thanks for this, as it has been tremendously helpful. I've validated the above approach using CVX to solve the projection, and it's plenty fast and fits in memory now that I can avoid the matrix-vector product implementation of $\mathbf{Rx}$. Also, thanks for CVX in general; it is such a boon to those of us who don't do optimization work regularly. $\endgroup$ – AnonSubmitter85 Jan 8 '14 at 21:12

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.