3.Examples and Demos
We use the following two quadratic programs as an example on each of the interfaces for the rest of the documentation.
The following problem shows a standard QP with both equality and inequality constraints
The solution for the above QP is [0.833 −0.583 1.000]'
The following problem shows a standard QP with only inequality constraints
The solution for the above QP is [0.450 −0.200 1.000]'
The demo file for C/C++ interface via sparse matrices can be found in runqp.c. To interface with the qpSWIFT function, add the header file
#include "qpSWIFT.h"
qpSWIFT has three main functions, QP_SETUP, QP_SOLVE, and QP_CLEANUP. Initialize the QP struct with
QP* myQP
The basic algorithmic skeleton for qpSWIFT is as follows
QP *myQP;
myQP = QP_SETUP(n, m, p, Pjc, Pir, Ppr, Ajc, Air, Apr, Gjc, Gir, Gpr, c, h, b,
sigma_d, Permut);
/* settings can be changed at this point */
qp_int ExitCode = QP_SOLVE(myQP);
/* solution and solution statistics can be accessed now */
QP_CLEANUP(myQP);
Initially, a pointer for the QP structure is defined. The data fields of the QP structure and the necessary memory are allocated using the first function QP_SETUP. Any custom settings, for example, the maximum number of iterations, can be set after invoking the QP_SETUP function. The second function QP_SOLVE computes the actual solution. At this stage, the solution is accessible using myQP->x. The third function QP_CLEANUP clears the entire setup. The description of the input arguments for each of the functions is provided below.
The first function, QP_SETUP, has the following input arguments
qp_int n /* number of decision Variables */
qp_int m /* number of inequality constraints */
qp_int p /* number of equality constraints */
qp_int* Pjc /* jc vector of P Matrix in CCS format */
qp_int* Pir /* ir vector of P Matrix in CCS format */
qp_real* Ppr /* pr vector of P Matrix in CCS format */
qp_int* Ajc /* jc vector of A Matrix in CCS format */
qp_int* Air /* ir vector of A Matrix in CCS format */
qp_real* Apr /* pr vector of A Matrix in CCS format */
qp_int* Gjc /* jc vector of G Matrix in CCS format */
qp_int* Gir /* ir vector of G Matrix in CCS format */
qp_real* Gpr /* pr vector of G Matrix in CCS format */
qp_real* c /* cost function vector */
qp_real* h /* inequality constraints vector */
qp_real* b /* equality constraints vector */
qp_int sigma_d /* desired sigma*/
qp_int Permut /* permutation vector of KKT Matrix */
Here, qpSWIFT accepts matrices in Compressed Column Storage format. sigma_d is set to zero. The last argument, Permut, refers to the permutation matrix of the KKT matrix. This can be set to NULL if you want to use the inbuilt AMD routines to compute the permutation matrix. More info regarding CCS format and Permutation matrices can be found in Appendix. If there are no equality constraints in the QP problem, then set the arguments Ajc, Air, Apr, b to a NULL pointer and the number of equality constraints as p = 0. After invoking this function, the solver settings for the QP can now be changed using
myQP->settings->maxit /* Maximum number of Iterations of QP */
myQP->settings->reltol /* Relative Tolerance */
myQP->settings->abstol /* Absolute Tolerance */
myQP->settings->sigma /* sigma desired */
myQP->settings->verbose /* Verbose Levels || 0 :: No Print */
/* || >0 :: Print Everything */
The default for these settings can be found in GlobalOptions.h. The function QP_SOLVE performs the actual solution
Exit_Code = QP_SOLVE(myQP)
The Exit_Code has the exit flag of the qpSWIFT. The following flags are set for ExitCode
QP_OPTIMAL (0) /* optimal solution found */
QP_KKTFAIL (1) /* failure in solving LDL' factorization */
QP_MAXIT (2) /* maximum number of iterations exceeded */
QP_FATAL (3) /* unknown problem in solver */
The solution can be accessed via the pointer
myQP->x /* Primal Solution a.k.a solution of the QP */
myQP->y /* Dual Solution of the QP (equality constraints) */
myQP->z /* Dual Solution of the QP (inequality constraints) */
myQP->s /* Slack Variables of the QP */
The statistics of the solution can be accessed via myQP->stats pointer and has the following fields
/* Time Statistics */
tsetup /* Setup time ; includes initialisation as well */
tsolve /* QP solve time */
kkt_time /* kkt matrix inversion time */
ldl_numeric /* kkt matrix factorization time */
/* Time Statistics */
/* Algorithmic Statistics */
IterationCount /* iteration Count */
n_rx /* norm of residual vector rx */
n_ry /* norm of residual vector ry */
n_rz /* norm of residual vector rz */
n_mu /* complementary Slackness (s'z/m) */
alpha_p /* primal step Size */
alpha_d /* dual step Size */
/* Algorithmic Statistics */
fval /* function Value */
Flag /* solver FLAG */
AMD_RESULT /* AMD Compilation Result */
/* >=0 means successful */
/* <0 means unsuccessful */
/* -3 means unused */
The last function to call is QP_CLEANUP.
QP_CLEANUP(myQP)
This function clears all the memory created by QP_SETUP. Please note that this function needs to be called after copying the QP solution and relevant statistics.
Demo file for C++ interface can be found at runqpcpp.cpp. The dense interface is also similar to the sparse interface. To interface with the dense interface, add the header file
#include "qpSWIFT.h"
The algorithmic skeleton for qpSWIFT dense interface is as follows
QP *myQP;
myQP = QP_SETUP_dense(n, m, p, P, A, G, c, h, b, Permut, COLUMN_MAJOR_ORDERING);
/* settings can be changed now */
qp_int ExitCode = QP_SOLVE(myQP);
/* solution and solution statistics can be accessed now */
QP_CLEANUP_dense(myQP);
First the QP struct pointer is created as
QP* myQP;
The solver can be interfaced via the same three functions, the same way as the sparse interface or can be done via a dense interface using QP_SETUP_dense function. Initially, a pointer for the QP structure is defined. The data fields of the QP structure and the necessary memory are allocated using the first function QP_SETUP_dense. Any custom settings, for example, the maximum number of iterations, can be set after invoking the QP_SETUP_dense function. The second function QP_SOLVE computes the actual solution. At this stage, the solution is accessible using myQP->x. The third function QP_CLEANUP_dense clears the entire setup. The description of the input arguments for each of the functions is provided below.
qp_int n /* Number of decision Variables */
qp_int m /* Number of inequality constraints */
qp_int p /* Number of equality constraints */
qp_real *P /* data pointer of P Matrix */
qp_real *G /* data pointer of G Matrix */
qp_real *A /* data pointer of A Matrix */
qp_real *c /* cost function vector */
qp_real *h /* inequality constraints vector */
qp_real *b /* equality constraints vector */
qp_int Permut /* Permutation vector of KKT Matrix */
qp_int ordering /* Indicates row major or column major ordering of P,A,G matrices*/
/* ROW_MAJOR_ORDERING - row major indexing of matrices */
/* COLUMN_MAJOR_ORDERING - column major indexing of matrices */
Note that all the matrices P, A, and G must be in contiguous blocks of memory and must be in either row-major or column-major ordering. If there are no equality constraints, set the A matrix and b vector to NULL pointer and the number of equality constraints p to be 0. The argument Permut refers to the permutation matrix of the KKT matrix. This can be set to NULL if you want to use the inbuilt AMD routines to compute the permutation matrix. More info regarding CCS format and Permutation matrices can be found in Appendix. After invoking this function, the solver settings for the QP can now be changed using
myQP->settings->maxit /* Maximum number of Iterations of QP */
myQP->settings->reltol /* Relative Tolerance */
myQP->settings->abstol /* Absolute Tolerance */
myQP->settings->sigma /* sigma desired */
myQP->settings->verbose /* Verbose Levels || 0 :: No Print */
/* || >0 :: Print Everything */
The default for these settings can be found in GlobalOptions.h. The function QP_SOLVE performs the actual solution
Exit_Code = QP_SOLVE(myQP)
The Exit_Code has the exit flag of the qpSWIFT. The following flags are set for ExitCode
QP_OPTIMAL (0) /* optimal solution found */
QP_KKTFAIL (1) /* failure in solving LDL' factorization */
QP_MAXIT (2) /* maximum number of iterations exceeded */
QP_FATAL (3) /* unknown problem in solver */
The solution can be accessed via the pointer
myQP->x /* Primal Solution a.k.a solution of the QP */
myQP->y /* Dual Solution of the QP (equality constraints) */
myQP->z /* Dual Solution of the QP (inequality constraints) */
myQP->s /* Slack Variables of the QP */
The statistics of the solution can be accessed via myQP->stats pointer and has the following fields
/* Time Statistics */
tsetup /* Setup time ; includes initialisation as well */
tsolve /* QP solve time */
kkt_time /* kkt matrix inversion time */
ldl_numeric /* kkt matrix factorization time */
/* Time Statistics */
/* Algorithmic Statistics */
IterationCount /* iteration Count */
n_rx /* norm of residual vector rx */
n_ry /* norm of residual vector ry */
n_rz /* norm of residual vector rz */
n_mu /* complementary Slackness (s'z/m) */
alpha_p /* primal step Size */
alpha_d /* dual step Size */
/* Algorithmic Statistics */
fval /* function Value */
Flag /* solver FLAG */
AMD_RESULT /* AMD Compilation Result */
/* >=0 means successful */
/* <0 means unsuccessful */
/* -3 means unused */
The last function to call is QP_CLEANUP_dense.
QP_CLEANUP_dense(myQP)
This function clears all the memory created by QP_SETUP_dense. Please note that this function needs to be called after copying the QP solution and relevant statistics.
qpSWIFT can be interfaced with Eigen via the dense matrix interface. Assuming that the matrices P, A, G and the vectors c, h, b are Eigen matrices, we can invoke qpSWIFT via
myQP = QP_SETUP_dense(P.rows(),A.rows().G.rows(),P.data(),G.data(),A.data(),...
c.data(),h.data(),b.data(),NULL,COLUMN_MAJOR_ORDERING);
The rest of the steps are similar to the dense interface.
Demo file can be found at demoqp.m. To use qpSWIFT for general quadratic program of the form
+
type the following commands
[sol,basic_info,adv_info] = qpSWIFT(sparse(P),c,sparse(A),b,sparse(G),h)
or
[sol,basic_info,adv_info] = qpSWIFT(sparse(P),c,sparse(A),b,sparse(G),h,opts)
For inequality only quadratic program of the form
the syntax is as follows
[sol,basic_info,adv_info] = qpSWIFT(sparse(P),c,sparse(G),h)
or
[sol,basic_info,adv_info] = qpSWIFT(sparse(P),c,sparse(G),h,opts)
The input arguments and their description is given below
P is a sparse matrix of dimension (n,n)
c is a dense column vector of size n
A is a sparse matrix of size (p,n); p is the number of equality constraints
b is a dense column vector of size p
G is a sparse matrix of size (m,n); m is the number of inequality constraints
h is a dense column vector of size m
opts is a structure with the following fields
-> MAXITER : maximum number of iterations needed
-> ABSTOL : absolute tolerance
-> RELTOL : relative tolerance
-> SIGMA : maximum centering allowed
-> VERBOSE : print levels || 0 -- no print
|| >0 -- print everything
-> Permut : permutation vector obtained as
KKT = [P A' G';
A 0 0;
G 0 -I];
Permut = amd(KKT);
Note that opts is not mandatory and all fields of opts are also not mandatory. All input matrices must be sparse. The output arguments have the following description
sol represents the primal solution of the QP
basic_info has four fields
-> Exit Flag : 0 : optimal solution found
: 1 : failure in factorising KKT matrix
: 2 : maximum number of iterations reached
: 3 : unknown problem in solver
-> Iterations : number of iterations
-> Setup Time : involves setting up QP; solving for the initial guess
-> Solve Time : solution time
adv_info has five fields
-> Fval : objective value of the QP
-> KKT_Time : time needed to solve the KKT system of equations
-> LDL_Time : time needed to perform LDL' factorization
-> y : dual variables corresponding to equality constraints
-> z : dual variables corresponding to inequality constraints
-> s : primal slack variables
Demo file can be found at demoqp.py. To run qpSWIFT in your python script
import qpSWIFT as qp
res = qp.run(c,h,P,G,A,b,opts)
The last three arguments A, b, opts are optional. The input arguments and their description is as follows
P is a numpy matrix of dimension (n,n)
c is a numpy column vector of size n
A is a numpy matrix of size (p,n); p is the number of equality constraints
b is a numpy column vector of size p
G is a numpy matrix of size (m,n); m is the number of inequality constraints
h is a numpy column vector of size m
opts is a dictionary with the following keys
-> MAXITER : maximum number of iterations needed
-> ABSTOL : absolute tolerance
-> RELTOL : relative tolerance
-> SIGMA : maximum centering allowed
-> VERBOSE : PRINT LEVELS || 0 -- No Print
|| >0 -- Print everything
-> OUTPUT : OUTPUT LEVELS || 1 -- sol + basicInfo
|| 2 -- sol + basicInfo + advInfo
|| otherwise -- sol
opts is not mandatory and all fields of opts are also not mandatory. The output arguments and their description is as follows
res represents a dictionary class with the following key-value pairs
* [sol] : Basic Solution represented as numpy vector
* [basic_info] : Dictionary class with four key-value pairs
-> Exit Flag : 0 : Optimal Solution Found
: 1 : Failure in factorizing KKT matrix
: 2 : Maximum Number of Iterations Reached
: 3 : Unknown Problem in Solver
-> Iterations : Number of Iterations
-> Setup Time : Involves setting up QP; solving for the initial guess
-> Solve Time : Solution Time
* [adv_info] : Dictionary class with five key-value pairs
-> Fval : Objective Value of the QP
-> KKT_Time : Time needed to solve the KKT system of equations
-> LDL_Time : Time needed to perform LDL' factorization
-> y : Dual Variables
-> z : Dual Variables
-> s : Primal Slack Variables
The demo simulink models can be found at demoqp_e.slx and demoqp.slx. Input to the s-function can be changed by modifying the vectors in_P, c, in_G and, h in the matlab function InputData of the demoqp.slx model . Similar changes can be made to demoqp_e.slx file. There are five outputs to each of the simulink s-function which are as follows
solution /* Solution of QP; dimension is set in s-function (line 13) */
exitflag /* : 0 : optimal solution found
: 1 : failure in factorizing KKT matrix
: 2 : maximum number of iterations reached
: 3 : unknown problem in solver */
iterations /* number of iterations */
setuptime /* setup time */
solvetime /* solution time */
Please note the following points while using the simulink interface.
- Inputs to the simulink s-functions must be vectors of appropriate dimensions. The matrices must be in column-major ordering.
- The solution vector of the QP is set to 3-dimensions (by default). To get the complete solution of QP, change the pre-processor definition
#define NVto desired value before compiling the s-function - To use the simulink function in SLRT framework, add all the source files found in src/ to the
Configuration Parameters > Simulation Target > Custom Code > Source fileblock in the simulink model file. Similarly, add the header file directory include/ to theConfiguration Parameters > Simulation Target > Custom Code > Header fileblock - The settings of the QP can be changed in the simulink s-function lines (142-152). Necessary details are found in the comments of the respective s-function files.