quadprog

Description

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 Tool; 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

W = hmfun(Hinfo,Y)

Output Arguments

Examples

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

subject to

x₁ + x₂ ≤ 2
–x₁ + 2x₂ ≤ 2
2x₁ + x₂ ≤ 3
0 ≤ x₁, 0 ≤ x₂.

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 Tool for quadratic programming. Enter optimtool at the MATLAB^® command line, and choose the quadprog - Quadratic programming solver. For more information, see Graphical Optimization Tool.

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.