# 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, ...? – Wolfgang Bangerth Oct 16 '12 at 23:58
• L(X) is quadratic. Would add in more -in the edit. – hearse Oct 17 '12 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! – hearse Oct 17 '12 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? – Arnold Neumaier Oct 17 '12 at 15:11
• What is the underlying problem that can be solved in these two (to me not at all equivalent looking) problems? – Arnold Neumaier Oct 17 '12 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. – hearse Oct 17 '12 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. – hearse Oct 17 '12 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. – hearse Oct 17 '12 at 2:46
• simpler on the surface only, as the quadratic constraint has very special, exploitable structure. And simpler does not necessarily mean faster. – Arnold Neumaier Oct 17 '12 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. – Wolfgang Bangerth Oct 17 '12 at 11:31