# Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?

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-as in - 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 a single linear constraint 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)?

Details: Example Formulation 1) Minimize $Tr(X^TAX)$ over $X$ under a constraint that $X^TX=I$

Example Formulation 2) Minimize $Tr(X^TAX)$ over $X$ under a single linear constraint, $Tr~X^TC=b$ over $X$ where $A$ is a known p.s.d matrix , $b$ is a constant (scalar) $\in \mathbb{R^+}$ and $C$ is a constant matrix with real-entries. Hence making $Tr(X^TAX)$ convex.

The dimension of $X$ in this problem setting varies from 5000 by 2 and up until 50000 by 3. So, the number of columns are not many. $A$ is a sparse matrix, with the amount of sparsity dependent on a tuning parameter of a kernel function that generates the matrix $A$. On a holistic sense the sparsity does range a lot from very sparse to not too sparse and is data and problem dependent.

Which would be the fastest to solve and by what factor!? And what are the example -fastest possible methods you would use for each individual problem-while coming to this conclusion. Would you come to this conclusion from a theoretical aspect- in terms of how the problem were formulated? If so, please go over that too.

• It would help if you edited the question to describe the problem in mathematical formulas. In addition, is there anything you know about $L(X)$? Is it quadratic, linear, ...? Oct 16, 2012 at 23:58
• L(X) is quadratic. Would add in more -in the edit. Oct 17, 2012 at 0:07

For a symmetric and positive definite matrix $A$, the problem $\min Tr~X^TAX$ subject to $Tr~X^TC=b [\in R_+]$ can be solved by introducing a Lagrange multipliers and setting the gradient of the Lagrangian to zero. The result is $X=\lambda Z$, where $Z=A^{-1}C$. Inserting this into the constraints gives the multiplier $\lambda=b/Tr~C^TA^{-1}C$. As $C$ has only a few columns, the dominant work is therefore that for computing $Z$, which means a solve for a fixed positive definite matrix with a few right hand sides. (If there were $s$ linear constraints, one would end up with an $s\times s$ system for the multiplier vector.)
If the sparsity of $A$ is such that upon reordering you can compute a Cholesky factor $R$, so that $A=R^TR$ then solving $R^TY=C$ and $RZ=Y$ gives the solution $X=\lambda Z$, where $\lambda=b/||Y||^2$ (in the Frobenius norm). If a factorization is too expensive, you need to employ conjugate gradients.

For a symmetric and positive definite matrix $G$, the problem $\min Tr~X^TGX$ subject to $X^TX=1$ is solved (for an $m\times n$ matrix $X$) by taking as columns of $X$ orthogonal eigenvectors corresponding to the $n$ smallest eigenvalues of $G$. This is more expensive to compute when $A$ can be factored, but if a factorization is not feasible, the Lanczos iteration will have complexity comparable to that for the other problem, and this will become better the more columns $X$ has.

• I have only one linear constraint $Tr(XA)=b$, i.e only a single pair of $A$ and $b$ and $A$ is sparse. Any pointers to a solver that I can use to benchmark this setting using the sparsity? I can easily find a standard eigen-decomposition routine to compute a series of experiments and look at the running times. Also, the size of my problem-is large-as in > 10000 rows. Some pointers would be appreciated. Am a statistician and my expertise isnt in numerical analysis or HiPC computing, hence big thanks for any such pointer! Oct 17, 2012 at 11:16
• @VSPC: In the question you wrote about constraints, so you'd correct that. - What is the size of $X$? - As you can see, everything is standard linear algebra, but if $G$ is large and sparse, fast computation of the computation of the trace is tricky. Are the sparsity of (my) $A_1$ and $G$ related? Oct 17, 2012 at 15:11
• What is the underlying problem that can be solved in these two (to me not at all equivalent looking) problems? Oct 17, 2012 at 15:12
• they are equivalent ;) In the domain am working on. That is why- I was surprised and was eager to see how a reasonable (or the best) solver would compare w.r.t a standard eigen decomposition solver- to see if the improvement in speed is of a factor-that makes any reasonable impact. I would be very free to acknowledge your input on setting up the optimization front. Am a statistician- and not a numerical analyst. Oct 17, 2012 at 15:17
• Have added it in the question. Also, I have included that the constant $b$ in the linear constraint $\in \mathbb{R^+}$; which I have also mentioned. Oct 17, 2012 at 15:22

Minimizing $Tr(X^TAX)$ subject to a linear constraint on $X$ is clearly a simpler problem than minimizing it subject to a quadratic constraint. You can do the former in a single step -- the solution is simply the solution of a single, linear, saddle point problem.

• Thanks for reinforcing my thoughts. Is this the fastest approach-or can this be formulated as an input to a sparse linear solver? I am looking for industrial level scalability-hence looking for the fastest way to solve formulation 2. Thanks. Oct 17, 2012 at 2:46
• simpler on the surface only, as the quadratic constraint has very special, exploitable structure. And simpler does not necessarily mean faster. Oct 17, 2012 at 9:30
• True. But as a general rule for a general question, linear constraints are still simpler to treat than nonlinear ones. For the latter, as you point out in your answer, there are sometimes special techniques; yet, they depend on the particular form of the nonlinear constraint, whereas quadratic optimization problems with linear constraints are always relatively simple to solve since their optimality conditions are linear. Oct 17, 2012 at 11:31