Quadratically constrainted quadratic programming (QCQP) in MATLAB

Question

Recently I have run into a Quadratically constrainted quadratic programming (QCQP) problem in my research. I have found something useful in MATLAB optimization toolbox, i.e. 'fmincon' function (general nonlinear optimization with nonlinear constraints), it use 'interior point algorithm' to solve my problem, which contains 8 variables, 1 equality quadratic constraint and 1 inequality quadratic constraint. 'fmincon' with or without 'Hessian' and 'Gradient' provide quite good solution, the only thing I am not satisfied is the efficiency, since I need to call it like million times in my main code. I need to find something which may be more specific to QCQP, possibly efficiency may improved. However I have found a lot of information from netlib and wiki, but I have no judgement on which one I should use, and it would be tedious to try things one by one, I really need some suggestions. By the way, I am mostly programming in MATLAB for this problem, but suitable c/fortran are also useful.

-Yan

If the problem is quadratic use 'quadprog'. Beside that you are going to have to provide more information on the spesific problem in order for the rest of the people to talk about possibly faster algorithms. — Alex Botev
The MATLAB 'quadprog' is a quadratic programming solver, however it only takes linear equality and non-equality constraints and boundaries. My question concerns the nonlinear constraints which can't be handled by it. MATLAB 'fmincon' is very good for my problem, but I am looking for something more efficient, since I need to call millions of time this function. — ywang

Patrick Sanan Patrick Sanan · Accepted Answer · 2013-08-16T19:05:29

An alternative is to use CVX, available here, which works nicely for QCQPs (amongst many other types of problems). Here is a code snippet which solves a QCQP:

close all; clear; clc
n = 10;
H = rand(n); H = H*H'; % make spsd
f = -rand(n,1);
Q = rand(n); Q = Q*Q'; % make spsd
g = -rand(n,1);
cvx_begin
    variable x(n)
    0.5*x'*Q*x+g'*x <=0
    x >= 0
    minimize(0.5*x'*H*x + f'*x)
cvx_end

Quadratically constrainted quadratic programming (QCQP) in MATLAB

1 Answers