solve a quadratic program in Matrix Form - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Optimization : Optimization Package : Optimization/QPSolveMatrixForm

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'x+12x'Hx

  

subject to

  

A.xb (linear inequality constraints)

  

Aeq.x=beq (linear equality constraints)

  

b1xbu (bounds)

  

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.

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

withOptimization:

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

c:=Vector2,5,datatype=float:

H:=Matrix6,3,3,4,datatype=float:

A:=Matrix1,1,datatype=float:

b:=Vector2,datatype=float:

QPSolvec,H,A,b

3.53333333333333,0.4666666666666671.60000000000000

(1)

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

QPSolvec,H,A,b,assume=nonnegative

16.,2.0.

(2)

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

bl:=1.5,∞:

bu:=∞,∞:

QPSolvec,H,A,b,bl,bu

1.53125000000000,1.500000000000002.37500000000000

(3)

Solve a quadratic problem with equality and inequality constraints.

H:=Matrix8,1,1,2,datatype=float:

A:=Matrix7,3,datatype=float:

b:=Vector16,datatype=float:

Aeq:=Matrix2,1,datatype=float:

beq:=Vector10,datatype=float:

QPSolveH,A,b,Aeq,beq

128.000000000000,14.000000000000038.0000000000000

(4)

To maximize a quadratic problem use the option maximize.

H:=Matrix2,0,0,0,2,0,0,0,2,datatype=float:

A:=Matrix1,1,1,datatype=float:

b:=Vector15,datatype=float:

QPSolveH,A,b,maximize

75.,5.5.5.00000000000000

(5)

See Also

Optimization, Optimization/AlgebraicForm, Optimization/Computation, Optimization/MatrixForm, Optimization/Options, Optimization/Solution, Optimization[QPSolve], realcons


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam