Complexity of a quadratic program

[Socal93]

I'm trying to compute the complexity of the quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$
A is MxN and X is Nx1. Q is positive definite and I'm using the interior point method. Any help in computing the complexity would be appreciated.

 

[lavinia]

You have caught my curiosity. What is meant by the complexity of a quadratic program?

 

[Socal93]

I'm trying to determine the computational complexity or the time it takes to solve the above problem.

 

[lavinia]

I'm trying to determine the computational complexity or the time it takes to solve the above problem.

Don't know anything about that. I do know that the Wolf algorithm reduces the quadratic program to a finite sequence of linear programs.

 

[blue_raver22]

The complexity of a quadratic program, such as the one described in the content, can be determined by analyzing the algorithm used to solve it. In this case, the interior point method is being used, which is a popular and efficient method for solving quadratic programs. The complexity of this method is typically O(n^3), where n is the number of decision variables.

In this specific problem, there are N decision variables and M constraints, so the complexity would be O(N^3 + MN^2). This is because the interior point method requires solving a linear system of equations in each iteration, which has a complexity of O(n^3), and the number of iterations is determined by the number of decision variables and constraints.

Furthermore, the complexity can also be affected by the specific characteristics of the problem, such as the positive definiteness of the matrix Q and the size of the matrices A and Y. Generally, the larger these matrices are, the higher the complexity will be.

In summary, the complexity of a quadratic program can vary depending on the specific problem and the algorithm used to solve it. However, in this case, with the interior point method and the given parameters, the complexity can be estimated to be O(N^3 + MN^2).