Documentation Center

  • Trial Software
  • Product Updates

quadprog

Quadratic programming

Syntax

x = quadprog(H,f)
x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(problem)
[x,fval] = quadprog(H,f,...)
[x,fval,exitflag] = quadprog(H,f,...)
[x,fval,exitflag,output] = quadprog(H,f,...)
[x,fval,exitflag,output,lambda] = quadprog(H,f,...)

Description

Finds a minimum for a problem specified by

H, A, and Aeq are matrices, and f, b, beq, lb, ub, and x are vectors.

f, lb, and ub can be passed as vectors or matrices; see Matrix Arguments.

x = quadprog(H,f) returns a vector x that minimizes 1/2*x'*H*x + f'*x. H must be positive definite for the problem to have a finite minimum.

x = quadprog(H,f,A,b) minimizes 1/2*x'*H*x + f'*x subject to the restrictions A*x  b. A is a matrix of doubles, and b is a vector of doubles.

x = quadprog(H,f,A,b,Aeq,beq) solves the preceding problem subject to the additional restrictions Aeq*x = beq. Aeq is a matrix of doubles, and beq is a vector of doubles. If no inequalities exist, set A = [] and b = [].

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) solves the preceding problem subject to the additional restrictions lb  x  ub. lb and ub are vectors of doubles, and the restrictions hold for each x component. If no equalities exist, set Aeq = [] and beq = [].

    Note:   If the specified input bounds for a problem are inconsistent, the output x is x0 and the output fval is [].

    quadprog resets components of x0 that violate the bounds lb  x  ub to the interior of the box defined by the bounds. quadprog does not change components that respect the bounds.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) solves the preceding problem starting from the vector x0. If no bounds exist, set lb = [] and ub = []. Some quadprog algorithms ignore x0, see Input Arguments.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) solves the preceding problem using the optimization options specified in options. Use optimoptions to create options. If you do not want to give an initial point, set x0 = [].

x = quadprog(problem) returns the minimum for problem, where problem is a structure described in Input Arguments. Create problem by exporting a problem using the Optimization app; see Exporting Your Work.

[x,fval] = quadprog(H,f,...) returns the value of the objective function at x:

fval = 0.5*x'*H*x + f'*x

[x,fval,exitflag] = quadprog(H,f,...) exitflag, a scalar that describes the exit condition of quadprog.

[x,fval,exitflag,output] = quadprog(H,f,...) output, a structure that contains information about the optimization.

[x,fval,exitflag,output,lambda] = quadprog(H,f,...) lambda, a structure whose fields contain the Lagrange multipliers at the solution x.

Input Arguments

H

Symmetric matrix of doubles. Represents the quadratic in the expression 1/2*x'*H*x + f'*x.

f

Vector of doubles. Represents the linear term in the expression 1/2*x'*H*x + f'*x.

A

Matrix of doubles. Represents the linear coefficients in the constraints A*x  b.

b

Vector of doubles. Represents the constant vector in the constraints A*x  b.

Aeq

Matrix of doubles. Represents the linear coefficients in the constraints Aeq*x = beq.

beq

Vector of doubles. Represents the constant vector in the constraints Aeq*x = beq.

lb

Vector of doubles. Represents the lower bounds elementwise in lb  x  ub.

ub

Vector of doubles. Represents the upper bounds elementwise in lb  x  ub.

x0

Vector of doubles. Optional. The initial point for some quadprog algorithms:

  • active-set

  • trust-region-reflective when there are only bound constraints

If you do not give x0, quadprog sets all components of x0 to a point in the interior of the box defined by the bounds. quadprog ignores x0 for the interior-point-convex algorithm, and for the trust-region-reflective algorithm with equality constraints.

options

Options created using optimoptions or the Optimization app.

All Algorithms

Algorithm

Choose the algorithm:

  • 'interior-point-convex' (default)

  • 'trust-region-reflective'

  • 'active-set'

The 'trust-region-reflective' algorithm handles problems with only bounds, or only linear equality constraints, but not both. The 'interior-point-convex' algorithm handles only convex problems. For details, see Choosing the Algorithm.

Diagnostics

Display diagnostic information about the function to be minimized or solved. The choices are 'on' or 'off' (default).

Display

Level of display returned to the command line.

  • 'off' or 'none' displays no output.

  • 'final' displays just the final output (default).

The 'interior-point-convex' algorithm allows additional values:

  • 'iter' gives iterative display.

  • 'iter-detailed' gives iterative display with a detailed exit message.

  • 'final-detailed' displays just the final output, with a detailed exit message.

MaxIter

Maximum number of iterations allowed, a positive integer.

  • For a 'trust-region-reflective' equality-constrained problem, the default value is 2*(numberOfVariables - numberOfEqualities).

  • For all other algorithms and problems, the default value is 200.

All Algorithms Except active-set

TolFun

Termination tolerance on the function value, a positive scalar.

  • For a 'trust-region-reflective' equality-constrained problem, the default value is 1e-6.

  • For a 'trust-region-reflective' bound-constrained problem, the default value is 100*eps, about 2.2204e-14.

  • For 'interior-point-convex', the default value is 1e-8.

TolX

Termination tolerance on x, a positive scalar.

  • For 'trust-region-reflective', the default value is 100*eps, about 2.2204e-14.

  • For 'interior-point-convex', the default value is 1e-8.

trust-region-reflective Algorithm Only

HessMult

Function handle for a Hessian multiply function. For large-scale structured problems, this function computes the Hessian matrix product H*Y without actually forming H. The function has the form

W = hmfun(Hinfo,Y)

where Hinfo and possibly some additional parameters contain the matrices used to compute H*Y.

See Quadratic Minimization with Dense, Structured Hessian for an example that uses this option.

MaxPCGIter

Maximum number of PCG (preconditioned conjugate gradient) iterations, a positive scalar. The default is max(1,floor(numberOfVariables/2)). For more information, see Preconditioned Conjugate Gradient Method.

PrecondBandWidth

Upper bandwidth of the preconditioner for PCG, a nonnegative integer. By default, quadprog uses diagonal preconditioning (upper bandwidth 0). For some problems, increasing the bandwidth reduces the number of PCG iterations. Setting PrecondBandWidth to Inf uses a direct factorization (Cholesky) rather than the conjugate gradients (CG). The direct factorization is computationally more expensive than CG, but produces a better quality step toward the solution.

TolPCG

Termination tolerance on the PCG iteration, a positive scalar. The default is 0.1.

TypicalX

Typical x values. The number of elements in TypicalX equals the number of elements in x0, the starting point. The default value is ones(numberofvariables,1). quadprog uses TypicalX internally for scaling. TypicalX has an effect only when x has unbounded components, and when a TypicalX value for an unbounded component exceeds 1.

interior-point-convex Algorithm Only

TolCon

Tolerance on the constraint violation, a positive scalar. The default is 1e-8.

problem

Structure encapsulating the quadprog inputs and options:

H

Symmetric matrix in 1/2*x'*H*x

f

Vector in linear term f'*x

Aineq

Matrix in linear inequality constraints Aineq*x  bineq

bineq

Vector in linear inequality constraints Aineq*x  bineq

Aeq

Matrix in linear equality constraints Aeq*x = beq

beq

Vector in linear equality constraints Aeq*x = beq
lbVector of lower bounds
ubVector of upper bounds

x0

Initial point for x

solver

'quadprog'

options

Options created using optimoptions or the Optimization app

Output Arguments

x

Vector that minimizes 1/2*x'*H*x + f'*x subject to all bounds and linear constraints. x can be a local minimum for nonconvex problems. For convex problems, x is a global minimum. For more information, see Local vs. Global Optima.

fval

Value of 1/2*x'*H*x + f'*x at the solution x, a double.

exitflag

Integer identifying the reason the algorithm terminated. The following lists the values of exitflag and the corresponding reasons the algorithm terminated:

All Algorithms

1

Function converged to the solution x.

0

Number of iterations exceeded options.MaxIter.

-2

Problem is infeasible.

-3

Problem is unbounded.

interior-point-convex Algorithm

-6

Nonconvex problem detected.

trust-region-reflective Algorithm

3

Change in the objective function value was smaller than options.TolFun.

-4

Current search direction was not a direction of descent. No further progress could be made.

active-set Algorithm

4

Local minimizer was found.

-7

Magnitude of search direction became too small. No further progress could be made. The problem is ill-posed or badly conditioned.

output

Structure containing information about the optimization. The fields are:

iterations

Number of iterations taken

algorithm

Optimization algorithm used

cgiterations

Total number of PCG iterations (trust-region-reflective algorithm only)

constrviolation

Maximum of constraint functions

firstorderopt

Measure of first-order optimality

message

Exit message

lambda

Structure containing the Lagrange multipliers at the solution x (separated by constraint type). The fields are:

lower

Lower bounds lb

upper

Upper bounds ub

ineqlin

Linear inequalities

eqlin

Linear equalities

For details, see Lagrange Multiplier Structures.

Examples

Solve a simple quadratic programming problem: find values of x that minimize

subject to

x1 + x2 ≤ 2
x1 + 2x2 ≤ 2
2x1 + x2 ≤ 3
0 ≤ x1, 0 ≤ x2.

In matrix notation this is

where

  1. Enter the coefficient matrices:

    H = [1 -1; -1 2]; 
    f = [-2; -6];
    A = [1 1; -1 2; 2 1];
    b = [2; 2; 3];
    lb = zeros(2,1);
  2. Set the options to use the 'active-set' algorithm with no display:

    opts = optimoptions('quadprog','Algorithm','active-set','Display','off');
  3. Call quadprog:

    [x,fval,exitflag,output,lambda] = ...
       quadprog(H,f,A,b,[],[],lb,[],[],opts);
  4. Examine the final point, function value, and exit flag:

     x,fval,exitflag
    
    x =
        0.6667
        1.3333
    
    fval =
       -8.2222
    
    exitflag =
         1
  5. An exit flag of 1 means the result is a local minimum. Because H is a positive definite matrix, this problem is convex, so the minimum is a global minimum. You can see H is positive definite by noting all its eigenvalues are positive:

    eig(H)
    ans =
        0.3820
        2.6180
 

Use the 'interior-point-convex' algorithm to solve a sparse quadratic program.

  1. Generate a sparse symmetric matrix for the quadratic form:

    v = sparse([1,-.25,0,0,0,0,0,-.25]);
    H = gallery('circul',v);
  2. Include the linear term for the problem:

    f = -4:3;
  3. Include the constraint that the sum of the terms in the solution x must be less than -2:

    A = ones(1,8);b = -2;
  4. Set options to use the 'interior-point-convex' algorithm and iterative display:

    opts = optimoptions('quadprog',...
        'Algorithm','interior-point-convex','Display','iter');
  5. Run the quadprog solver and observe the iterations:

    [x fval eflag output lambda] = quadprog(H,f,A,b,[],[],[],[],[],opts);
    
                                        First-order	 Total relative
     Iter         f(x)     Feasibility   optimality	     error
        0  -2.000000e+000   1.000e+001   4.500e+000   1.200e+001   
        1  -2.630486e+001   0.000e+000   9.465e-002   9.465e-002   
        2  -2.639877e+001   0.000e+000   3.914e-005   3.914e-005   
        3  -2.639881e+001   0.000e+000   3.069e-015   6.883e-015   
    
    Minimum found that satisfies the constraints.
    
    Optimization completed because the objective function is
    non-decreasing in feasible directions, to within the default value 
    of the function tolerance, and constraints are satisfied to within 
    the default value of the constraint tolerance.
  6. Examine the solution:

    fval,eflag
    
    fval =
      -26.3988
    
    eflag =
         1

    For the 'interior-point-convex' algorithm, an exit flag of 1 means the result is a global minimum.

Alternatives

You can use the Optimization app for quadratic programming. Enter optimtool at the MATLAB® command line, and choose the quadprog - Quadratic programming solver. For more information, see Optimization App.

More About

expand all

Algorithms

trust-region-reflective

The 'trust-region-reflective' algorithm is a subspace trust-region method based on the interior-reflective Newton method described in [1]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). For more information, see trust-region-reflective quadprog Algorithm.

active-set

quadprog uses an active set method, which is also a projection method, similar to that described in [2]. It finds an initial feasible solution by first solving a linear programming problem. For more information, see active-set quadprog Algorithm.

interior-point-convex

The 'interior-point-convex' algorithm attempts to follow a path that is strictly inside the constraints. It uses a presolve module to remove redundancies, and to simplify the problem by solving for components that are straightforward. For more information, see interior-point-convex quadprog Algorithm.

References

[1] Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040–1058, 1996.

[2] Gill, P. E., W. Murray, and M. H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

[3] Gould, N. and P. L. Toint. "Preprocessing for quadratic programming." Math. Programming, Series B, Vol. 100, pp. 95–132, 2004.

See Also

| |

Was this topic helpful?