Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the improvement in speed by many factors!?

  1. Minimizing a convex function $L(X)$ in one matrix variable with orthogonality constraints over the matrix-essentially in my case this ends up to solving an eigen-decomposition.

  2. Minimizing the same convex function $L(X)$ with linear constraints in $X$.

I know that 2.) should be faster. But what is the direction of work I need to do- to compare the improvement in speed-especially in terms of using the fastest available eigen solver for 1.)-what would be the corresponding fastest approach to solve 2.)?

share|improve this question

migrated from cstheory.stackexchange.com Dec 6 '12 at 7:36

This question came from our site for theoretical computer scientists and researchers in related fields.

    
a single eigendecomposition might well be faster in practice than convex optimization with linear constraints –  Sasho Nikolov Dec 7 '12 at 0:14
add comment

1 Answer 1

Regarding the eigen-decomposition, often it is enough to just compute the first few eigenvalue/eigenvector pairs. In the case, Krylow-subspace methods can be blazingly fast.

For the convex minimization under linear constraints, the (preconditioned) Uzawa iteration is a typical Krylow-subspace method, which is often not bad. There exist probably more advanced algorithms for this problem now, but http://scicomp.stackexchange.com would be a better place to ask about these. Also Schur-complement methods, or just parameterization of the linear sub-space might work fine too. And in case the linear constraints is actually a bunch of linear inequalities, a state of the art linear/convex programming solver might be the way to go.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.