QPSolve (Matrix Form) - Maple Help

Optimization[QPSolve](Matrix Form)

solve a quadratic program in Matrix Form

 Calling Sequence QPSolve(obj, lc, bd, opts)

Parameters

 obj - Matrix or list; quadratic objective function lc - (optional) list; linear constraints bd - (optional) list; bounds opts - (optional) equation(s) of the form option = value where option is one of assume, feasibilitytolerance, infinitebound, initialpoint, iterationlimit, maximize, or output; specify options for the QPSolve command

Description

 • The QPSolve command solves a quadratic program (QP), which involves computing the minimum (or maximum) of a quadratic objective function possibly subject to linear constraints. A QP has the following form.
 minimize (or maximize) $c\text{'}x+\frac{1}{2}x\text{'}Hx$
 subject to
 $A·x\le b$ (linear inequality constraints)
 $\mathrm{Aeq}·x=\mathrm{beq}$ (linear equality constraints)
 $\mathrm{b1}\le x\le \mathrm{bu}$ (bounds)
 where $x$ is the vector of problem variables; $c$, $b$, $\mathrm{beq}$, $\mathrm{bl}$, and $\mathrm{bu}$ are vectors; $A$ and $\mathrm{Aeq}$ are matrices; and $H$ is the symmetric Hessian matrix.  The relations involving matrices and vectors are element-wise.  In the function defined, $c\text{'}$ and $x\text{'}$ refer to the vector transpose.
 • This help page describes how to specify the problem in Matrix form. For details about the exact format of the objective function and the constraints, see the Optimization/MatrixForm help page. The algebraic form for specifying a QP is described in the Optimization[QPSolve] help page. The Matrix form is more complex, but leads to more efficient computation.
 • The first parameter obj is either a Matrix $H$, when the objective function has no linear part, or a list $\left[c,H\right]$, when the linear part $c$ exists.  The parameter obj is required and the number of problem variables $n$ is taken to be the dimension of the symmetric Matrix $H$.  The Vector $c$ must have dimension $n$.
 The second parameter lc is an optional list of linear constraints. The most general form is $\left[A,b,\mathrm{Aeq},\mathrm{beq}\right]$ where A and Aeq are Matrices, and b and beq are Vectors. This parameter can take other forms if either inequality or equality constraints do not exist.  For a full description of how to specify general linear constraints, refer to the Optimization/MatrixForm help page.
 The third parameter $\mathrm{bd}$ is an optional list $\left[\mathrm{bl},\mathrm{bu}\right]$ of lower and upper bounds.  In general, bl and bu must be n-dimensional Vectors. The Optimization/MatrixForm help page describes alternate forms that can be used when either bound does not exist and provides more convenient ways of specifying the Vectors. Non-negativity of the problem variables is not assumed by default, but can be specified using the assume = nonnegative option.
 • Maple returns the solution as a list containing the final minimum (or maximum) value and a point (the extremum).  If the output = solutionmodule option is provided, then a module is returned.  See the Optimization/Solution help page for more information.
 If the quadratic program is convex, a global minimum is returned. Otherwise, the solution may be a local minimum.

Options

 The opts argument can contain one or more of the following options. These options are described in more detail in the Optimization/Options help page.
 • assume = nonnegative -- Assume that all variables are non-negative.
 • feasibilitytolerance = realcons(positive) -- Set the maximum absolute allowable constraint violation.
 • infinitebound = realcons(positive) -- Set any value of a variable greater than the infinitebound value to be equivalent to infinity during the computation.
 • initialpoint = Vector --  Use the provided initial point, which is an n-dimensional Vector of numeric values.
 • iterationlimit = posint -- Set the maximum number of iterations performed by the active-set algorithm.
 • maximize or maximize = truefalse -- Maximize the objective function when equal to true and minimize when equal to false.  The option 'maximize' is equivalent to maximize = true. The default is maximize = false.
 • output = solutionmodule -- Return a module as described in the Optimization/Solution help page.

Notes

 • The QPSolve command uses an active-set method implemented in a built-in library provided by the Numerical Algorithms Group (NAG).  An initial point can be provided using the initialpoint option. Otherwise, a default point is used.
 • The computation is performed in floating-point. Therefore, all data provided must have type realcons and all returned solutions are floating-point, even if the problem is specified with exact values.  For best performance, Vectors and Matrices should be constructed with the datatype = float option, and the symmetric Hessian H should be constructed with the shape = symmetric and storage = rectangular options. For more information about numeric computation in the Optimization package and suggestions on how to obtain the best performance using the Matrix form of input, see the Optimization/Computation help page.
 • QPSolve returns an error if the problem is infeasible.  If the problem appears to be unbounded, QPSolve issues a warning and returns the last computed result. This result may be meaningless.
 • Although the assume = nonnegative option is accepted, general assumptions are not supported by commands in the Optimization package.

Examples

 > $\mathrm{with}\left(\mathrm{Optimization}\right):$

Use QPSolve to solve a quadratic program in two variables subject to one linear constraint.

 > $c≔\mathrm{Vector}\left(\left[2,5\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $H≔\mathrm{Matrix}\left(\left[\left[6,3\right],\left[3,4\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[-1,1\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $b≔\mathrm{Vector}\left(\left[-2\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $\mathrm{QPSolve}\left(\left[c,H\right],\left[A,b\right]\right)$
 $\left[{-3.53333333333333}{,}\left[\begin{array}{c}{0.466666666666667}\\ {-1.60000000000000}\end{array}\right]\right]$ (1)

Use the assume = nonnegative option to specify that the variables are non-negative.

 > $\mathrm{QPSolve}\left(\left[c,H\right],\left[A,b\right],\mathrm{assume}=\mathrm{nonnegative}\right)$
 $\left[{16.}{,}\left[\begin{array}{c}{2.}\\ {0.}\end{array}\right]\right]$ (2)

Replace the non-negative assumption with explicit bounds on each variable.

 > $\mathrm{bl}≔⟨1.5,-\mathrm{\infty }⟩:$
 > $\mathrm{bu}≔⟨\mathrm{\infty },\mathrm{\infty }⟩:$
 > $\mathrm{QPSolve}\left(\left[c,H\right],\left[A,b\right],\left[\mathrm{bl},\mathrm{bu}\right]\right)$
 $\left[{-1.53125000000000}{,}\left[\begin{array}{c}{1.50000000000000}\\ {-2.37500000000000}\end{array}\right]\right]$ (3)

Solve a quadratic problem with equality and inequality constraints.

 > $H≔\mathrm{Matrix}\left(\left[\left[8,-1\right],\left[-1,-2\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[7,3\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $b≔\mathrm{Vector}\left(\left[16\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $\mathrm{Aeq}≔\mathrm{Matrix}\left(\left[\left[2,1\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $\mathrm{beq}≔\mathrm{Vector}\left(\left[10\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $\mathrm{QPSolve}\left(H,\left[A,b,\mathrm{Aeq},\mathrm{beq}\right]\right)$
 $\left[{-128.000000000000}{,}\left[\begin{array}{c}{-14.0000000000000}\\ {38.0000000000000}\end{array}\right]\right]$ (4)

To maximize a quadratic problem use the option maximize.

 > $H≔\mathrm{Matrix}\left(\left[\left[-2,0,0\right],\left[0,-2,0\right],\left[0,0,-2\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[-1,-1,-1\right]\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $b≔\mathrm{Vector}\left(\left[-15\right],\mathrm{datatype}=\mathrm{float}\right):$
 > $\mathrm{QPSolve}\left(H,\left[A,b\right],\mathrm{maximize}\right)$
 $\left[{-75.}{,}\left[\begin{array}{c}{5.}\\ {5.}\\ {5.00000000000000}\end{array}\right]\right]$ (5)