Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, $\mathbf{A}$ is $M \times N$ and $\mathbf{X}$ is an $N \times 1$ vector. I'm trying to compute the complexity in terms of multiplications, but can not figure out how to approach it. I'd appreciate it if anyone can provide help/guidance or any references I can check. I'm using the interior point convex algorithm.

share|improve this question
1  
Since Q is positive definite and the constraints are linear, the problem is convex and so in theory can be solved in polynomial time. For any kind of more detailed answer we will need a lot more information about what algorithm you're using the solve the QP. –  user7530 Jan 2 '13 at 3:52
    
I'm using the interior point convex algorithm (updated question above). –  SoCal93 Jan 2 '13 at 4:00
    
Using bold, particularly blackboard bold, Q, C to denote matrices isn't a good idea... –  tomasz Jan 2 '13 at 4:11
    
Thanks. Question updated. –  SoCal93 Jan 2 '13 at 4:16
add comment

1 Answer 1

You asked for references...Convex Optimization by Boyd and Vandenberghe is a good jumping-off point. It's available online, at

http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

(be forewarned, it's a large PDF.) See in particular the start of section 11.8...what you do will partially depend whether Q is sparse.

share|improve this answer
    
Thank you for the reference. –  SoCal93 Jan 2 '13 at 4:42
    
@RussH, can you provide a link in the response? –  Amzoti Jan 2 '13 at 4:57
    
Done and done.. –  RussH Jan 2 '13 at 5:31
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.