Hi All,
I have an optimization problem
$$ \min |\alpha|{1}$$ subject to
$$ |\Sigma\alpha - \beta|{\inf} \leq \tau$$
Is there anytime in the solution that $$\Sigma$$ is inverted?
Thanks.
I do not know CVX in detail but I doubt it inverts it but who knows what the optimizers (=SDPT3, SeDuMi, MOSEK,…) does. Maybe you should tell why that is relevant.
Sure, if \Sigma is diagonal, it’s possible that CVX’s presolve inverts it. But in general, no, it passes it to the underlying solvers unchanged. The solvers themselves are solving linear systems that involve \Sigma, but they don’t do full inversion.
Thanks Erling and Michael.
My question has to do with speed actually. I realized that if $$\Sigma$$ is multiplying the optimization variable as the case above, it’s slower than if I had the optimization constraint
$$|\alpha - \Sigma\beta|{\infty} \leq \tau$$
Here the constraint becomes
$$-\tau*1{p} + \Sigma\beta \leq \alpha \leq\tau*1_{p}-\Sigma\beta $$
while for the original the constraint is $$-\tau1_{p} + \beta \leq \Sigma\alpha \leq\tau1_{p}+\beta $$.
That got me thinking that maybe \Sigma is being inverted in the original constraint and may explain why its slow.
Well, “slow” is relative. Have you found solvers for your specific problem that are significantly faster than the ones CVX employs? If so, then by all means, you should use them—the solvers that CVX users are more general-purpose, so they will tend to be slower than ones designed for a specific problem.
If you haven’t found a solver that is significantly faster, then consider that perhaps the solvers aren’t actually “slow” at all: the model is complex!
Barring the ability to exploit some particular structure with a specialized algorithm, solving a convex optimization problem is typically going to take 10-100 times longer than a least squares problem of the same size and similar structure. That’s just the nature of it.