QpSolve

Purpose

Solve general quadratic programming problems.

qpSolve solves problems of the form

${\begin{array}{cccccl}\min \limits _{x}&f(x)&=&{\frac {1}{2}}(x)^{T}Fx+c^{T}x&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\&b_{L}&\leq &Ax&\leq &b_{U}\\\end{array}}$

where $x,x_{L},x_{U}\in \mathbb {R} ^{n}$, $F\in \mathbb {R} ^{n\times n}$, $c\in \mathbb {R} ^{n}$, $A\in \mathbb {R} ^{m\times n}$ and $b_{L},b_{U}\in \mathbb {R} ^{m}$.

Calling Syntax

Result = qpSolve(Prob) or
Result = tomRun('qpSolve', Prob, 1);

Inputs

Prob	Problem description structure. The following fields are used:
	QP.F	Constant matrix, the Hessian.
	QP.c	Constant vector.
	A	Constraint matrix for linear constraints.
	b_L	Lower bounds on the linear constraints.
	b_U	Upper bounds on the linear constraints.
	x_L	Lower bounds on the variables.
	x_U	Upper bounds on the variables.
	x_0	Starting point.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: eps_f, eps_Rank, MaxIter, wait, bTol and PriLev.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Optimal point.
	f_k	Function value at optimum.
	g_k	Gradient value at optimum.
	H_k	Hessian value at optimum.
	v_k	Lagrange multipliers.
	x_0	Starting point.
	f_0	Function value at start.
	xState	State of each variable, described in TOMLAB Appendix B.
	Iter	Number of iterations.
	ExitFlag	0: OK, see Inform for type of convergence. 2: Can not find feasible starting point x_0. 3: Rank problems. Can not find any solution point. 4: Unbounded solution. 10: Errors in input parameters.
	Inform	If ExitF lag > 0, Inform = ExitFlag, otherwise I nf orm show type of convergence: 0: Unconstrained solution. 1: λ = 0. 2: λ = 0. No second order Lagrange mult. estimate available. 3: λ and 2nd order Lagr. mult. positive, problem is not negative definite. 4: Negative definite problem. 2nd order Lagr. mult. positive, but releasing variables leads to the same working set.
	Solver	Solver used.
	SolverAlgorithm	Solver algorithm used.
	Prob	Problem structure used.

Description

Implements an active set strategy for Quadratic Programming. For negative definite problems it computes eigenvalues and is using directions of negative curvature to proceed. To find an initial feasible point the Phase 1 LP problem is solved calling lpSimplex. The routine is the standard QP solver used by nlpSolve, sTrustr and conSolve.

M-files Used

ResultDef.m, lpSimplex.m, tomSolve.m, iniSolve.m, endSolve.m

See Also

• qpBiggs
• qpe
• qplm
• nlpSolve]
• sTrustr
• conSolve