solve a quadratic program in Matrix Form
QPSolve(obj, lc, bd, opts)
Matrix or list; quadratic objective function
(optional) list; linear constraints
(optional) list; bounds
(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
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'⁢x+12⁢x'⁢H⁢x
A·x≤b (linear inequality constraints)
Aeq·x=beq (linear equality constraints)
where x is the vector of problem variables; c, b, beq, bl, and bu are vectors; A and Aeq are matrices; and H is the symmetric Hessian matrix. The relations involving matrices and vectors are element-wise. In the function defined, c' and x' 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 c,H, 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 A,b,Aeq,beq 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 bd is an optional list bl,bu 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.
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.
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.
Use QPSolve to solve a quadratic program in two variables subject to one linear constraint.
c ≔ Vector⁡2,5,datatype=float:
H ≔ Matrix⁡6,3,3,4,datatype=float:
A ≔ Matrix⁡−1,1,datatype=float:
b ≔ Vector⁡−2,datatype=float:
Use the assume = nonnegative option to specify that the variables are non-negative.
Replace the non-negative assumption with explicit bounds on each variable.
bl ≔ 1.5,−∞:
bu ≔ ∞,∞:
Solve a quadratic problem with equality and inequality constraints.
H ≔ Matrix⁡8,−1,−1,−2,datatype=float:
A ≔ Matrix⁡7,3,datatype=float:
b ≔ Vector⁡16,datatype=float:
Aeq ≔ Matrix⁡2,1,datatype=float:
beq ≔ Vector⁡10,datatype=float:
To maximize a quadratic problem use the option maximize.
H ≔ Matrix⁡−2,0,0,0,−2,0,0,0,−2,datatype=float:
A ≔ Matrix⁡−1,−1,−1,datatype=float:
b ≔ Vector⁡−15,datatype=float:
Download Help Document
What kind of issue would you like to report? (Optional)