File Exchange

image thumbnail

quadprog2 - convex QP solver

version 1.0.0.0 (9.4 KB) by Michael Kleder
Solves convex constrained quadratic programming (QP) using SOLVOPT.

10 Downloads

Updated 12 Jul 2005

No License

QUADPROG2 - Convex Quadratic Programming Solver
Featuring the SOLVOPT freeware optimizer

New for version 1.1:
* Significant speed improvement
* Geometric Preconditioning
* Improved Error Checking

USAGE:
[x,v] = quadprog2(H,f,A,b)
[x,v] = quadprog2(H,f,A,b,guess)
[x,v,opt] = ...

Minimizes the function v = 0.5*x'*H*x + f*x
subject to the constraint A*x <= b.
Initial guess is optional.

("opt" returns SOLVOPT data for advanced use. Details are available in
the SOLVOPT documentation at the website identified below.)

Notes:
(1) For a problem with 100 variables and 300 constraints, you will
often get a result in under 5 seconds. However, sometimes
the optimizer has to work longer (see below) for difficult
optimizations. Alerts are provided. (Note: The calculation
time is more sensitive to the number of variables than it is
to the number of contraints.)
(2) Geometric preconditioning is undertaken for 10 or more
dimensions to greatly reduce calculation time. (With fewer
than 10 dimensions, there is negligible benefit, so the
preconditioning calculations are omitted.)
(3) Geometric preconditioning can impair the convergence of some
difficult optimizations. When this occurs, the optimization
is attempted again without the preconditioning.
(4) x and guess are column vectors. f is a row vector.
They will be converted if necessary.
(5) This m-file incorporates the SOLVOPT version 1.1 freeware
optimizer, which has been wholly reproduced, except for
a few slight modifications for convenience in parameter passing.
(6) SolvOpt is a general nonlinear local optimizer,
written by Alexei Kuntsevich & Franz Kappel, and
is available (as of this writing) as freeware from:
http://www.uni-graz.at/imawww/kuntsevich/solvopt/
(7) This Matlab function requires a convex QP problem
with a positive-definite symmetric matrix H.
This is a somewhat trivial application of
a general solver like SOLVOPT, but the use of precomputed
gradient vectors herein makes the solution fast enough
to warrant use.
(8) Any local solution of a convex QP is also a global solution.
Hence, your results will be globally optimal.
(9) Relative precision in the objective function is set to 1e-6.
(10) Absolute precision in constraint violation is 1e-6 or better.
(11) This program does not require the Optimization Toolbox
(12) ver 1.0: intial writing, Michael Kleder, June 2005
(13) ver 1.1: geometric preconditioning, Michael Kleder, July 2005

EXAMPLE:
% Convex QP with 100 variables and 300 constraints:
n = 100;
c = 300;
H = rand(n);
H=H*H';
f=rand(1,n);
A=rand(c,n)*2-1;
b=ones(c,1);
tic
x = quadprog2(H,f,A,b)
toc

Cite As

Michael Kleder (2020). quadprog2 - convex QP solver (https://www.mathworks.com/matlabcentral/fileexchange/7860-quadprog2-convex-qp-solver), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (11)

Wittawat

How about using 2 inequality constraints to define 1 equality constraint ? Like...

ax <= b, ax >= b

That should be the same as ax=b ?

I have the same question. I need a QP solver for training SVM on face recognition. I need equality constraints( Aeq, beq) and lower uper bounds (lb, ub). Does quadprog2 provide this functionality? Thank you.

how to use this for equality constraints.

Good alternative to Matlab's quadprog.

Pete Jersen

Thanks for making a QP solver that doesn't require the optimization toolbox (like the "original quadprog" does.)

rifaldi oktrivianto

chris panos

seems to work fine but is slower than the original quadprog. I used the example which contains in the file.

The Author

Note: fmincon requires the optimization toolbox.

Aditya Dua

Easy to use! However, for my application the fmincon() function in Matlab was way faster!
I had 16 variables and 36 constraints.

sandeep san

how to use this for negative definite matrices??!!!
or in other words how to find maxima of positive definite??

Sven Zimmermann

Very fast algorithm!

Updates

1.0.0.0

New for version 1.1:
* Geometric Preconditioning
* Improved Error Checking

Added quick intial check to see if global minimizer is within the constraints. If so, solve immediately in closed form and exit.

MATLAB Release Compatibility
Created with R14SP1
Compatible with any release
Platform Compatibility
Windows macOS Linux