QCQP Solvers
Two little programs here
attempt to solve a quadratically constrained quadratic
program (QCQP) in different ways. They both are simple
wrappers which make calls to
cvxopt.
QCQP
The function 'qcqp' will try to solve the
convex program
| Minimize | `(A_0 x+b_0)^t(A_0 x + b_0) - c_0^t x - d_0 ` | |
| subject to | `(A_k x+b_k)^t(A_k x + b_k) - c_k^t x - d_k ≤ 0,` | `1≤ k< N` |
| `A x = b` |
QCQPREL
The function 'qcqprel' will try to solve the (possibly
nonconvex) semidefinite relaxation of the QCQP
| Minimize | `x^t P_0 x + b_0^tx + c_0 ` | |
| subject to | `x^t P_k x + b_k^tx + c_k ≤ 0,` | `1 ≤ k < N` |
| `x^t P_k x + b_k^tx + c_k = 0,` | ` N ≤ k < M` |
Files here are written in Python and require a working
installation of
cvxopt. Scroll
down to get them.
Requirements: a working copy
of
cvxopt. The
files below were developed using cvxopt version 1.1.1.
The Files
These files were updated
on May 26, 2009.
Comments
The function 'qcqp' solves the problem by casting it as
an SDP --- it makes no attempt to convert it to an
SOCP. This is fine for toy problems, but probably not
ideal for larger problems.
Essentially no error checking is done with the input ---
this should be improved.
The files are named '*_py' instead of '*.py' because the
current web server tries to execute the '*.py' files
instead of sending them.
If you find bugs, please tell
me. jeffery.kline @ gmail com
License
You can redistribute software here
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either
version 3 of the
License, or (at your option) any later version.
Files
here are distributed in the hope that they will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.