quadprog is too slow for a convex unconstrained quadratic problem

My algorithm contains solving a unconstrained quadratic problem. f(x) = 1/2*x'*A*x+b'*x, where A is a positive semidefinite matrix. Since the dimension of the matrix and vector is too large, the quadprog (using Interior point method in its iteration) runs too slow. Is there any more efficient algorithm package to solve this problem? Thanks very much for your help

Answer 1

[Kartik Saxena]

Hi,

I understand that you need a faster and more efficient alrorithm to solve unconstrained quadratic problems.

For solving large-scale unconstrained quadratic programming problems where the matrix ( A ) is positive semidefinite, you can often achieve better performance by using specialized algorithms that take advantage of the problem's structure. Here are a few alternatives to MATLAB's quadprog that you might consider:

1. Conjugate Gradient Method: This is an iterative method specifically designed for solving large systems of linear equations or large-scale unconstrained optimization problems, particularly when the matrix ( A ) is symmetric positive semidefinite. MATLAB's built-in 'pcg' (Preconditioned Conjugate Gradient) function can be used for this purpose. Refer to the following MathWorks documentation for detailed information about 'pcg' function: https://www.mathworks.com/help/matlab/ref/pcg.html
2. LSQR: The LSQR algorithm is an iterative method for solving large-scale linear systems and least-squares problems. Although it's not specifically designed for quadratic programming, it can be effective for large and sparse systems. MATLAB's built-in 'lsqr' function can be used. Refer to the following MathWorks documentation for detailed information about 'lsqr' function: https://www.mathworks.com/help/matlab/ref/lsqr.html

I hope this resolves your issue.