Convex Quadratic Programming (ConvexQP) problems#
Problem statement#
Given
an integer \(n\) , the dimension of the ambient space,
a SDP matrix \(M \in \mathrm{I\!R}^{n \times n}\)
a vector \(q \in \mathrm{I\!R}^n\)
a matrix \(A \in \mathrm{I\!R}^{m times n}\) of constraints
a vector \(b \in \mathrm{I\!R}^m\)
a convex set \({C} \in {{\mathrm{I\!R}}}^m\)
the convex QP problem is to find a vector \(z\in{{\mathrm{I\!R}}}^n\) ,
and is most simple example is when \(b= 0 A =I\) and we obtain
Most of the solver returns
the solution vector \(z \in \mathrm{I\!R}^n\)
the vector \(u \in \mathrm{I\!R}^m\)
the multiplier \(\xi \in \mathrm{I\!R}^m\) such that \(-\xi \in \partial \Psi_C(u)\)
the vector \(w \in \mathrm{I\!R}^n\) such that \(w =A^T \xi\)
In the most simple case, we return
the solution vector \(z = u \in \mathrm{I\!R}^n\)
the vector \(w =\xi \in \mathrm{I\!R}^m\)
Implementation in numerics#
Structure to define the problem: ConvexQP
.
No generic driver.
solvers list CONVEXQP_SOLVER
Available solvers#
convex QP, projected gradient (SICONOS_CONVEXQP_PG
)#
driver convexQP_ProjectedGradient()
parameters:
iparam[SICONOS_IPARAM_MAX_ITER] = 20000
iparam[SICONOS_CONVEXQP_PGOC_LINESEARCH_MAX_ITER] =20
dparam[SICONOS_CONVEXQP_PGOC_RHO] = -1.e-3 /* rho is variable by default */
dparam[SICONOS_CONVEXQP_PGOC_RHOMIN] = 1e-9
dparam[SICONOS_CONVEXQP_PGOC_LINESEARCH_MU] =0.9
dparam[SICONOS_CONVEXQP_PGOC_LINESEARCH_TAU] = 2.0/3.0
dparam[SICONOS_DPARAM_TOL] = 1e-6
convex QP, VI solvers`(SICONOS_CONVEXQP_VI_FPP
and SICONOS_CONVEXQP_VI_EG
)#
Rewrite QP as Variational Inequality problem.
ids: SICONOS_CONVEXQP_VI_FPP (fixed-point projection) and SICONOS_CONVEXQP_VI_EG (extra-gradient)
driver convexQP_VI_solver()
parameters:
same as SICONOS_VI_FPP and SICONOS_VI_EG (see VI Available solvers).
convex QP, ADMM (SICONOS_CONVEXQP_ADMM
)#
ADMM, alternating direction method of multipliers
driver convexQP_ADMM()
parameters:
iparam[SICONOS_IPARAM_MAX_ITER] = 20000
iparam[SICONOS_CONVEXQP_ADMM_IPARAM_ACCELERATION] = SICONOS_CONVEXQP_ADMM_ACCELERATION_AND_RESTART
dparam[SICONOS_DPARAM_TOL] = 1e-6
dparam[SICONOS_CONVEXQP_ADMM_RHO] = 1.0
dparam[SICONOS_CONVEXQP_ADMM_RESTART_ETA] = 0.999