Syntax

Description

Finds a minimum for a problem specified by

$$\underset{x}{\min }\frac{1}{2}{x}^{T}Hx+f^{T}x\text{ such that }\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ lb\le x\le ub.\end{array}$$

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

W = hmfun(Hinfo,Y)

Output Arguments

Examples

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

$$f(x)=\frac{1}{2}{x}_1^2+x_2^2-x_1{x}_2-2x_1-6x_2,$$

subject to

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

In matrix notation this is

$$f(x)=\frac{1}{2}{x}^{T}Hx+f^{T}x,$$

where

$$H=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right],f=\left[\begin{array}{c}-2\\ -6\end{array}\right],x=\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right].$$

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 'interior-point-convex' algorithm with no display:

   options = optimoptions('quadprog',...
       'Algorithm','interior-point-convex','Display','off');

3. Call quadprog:

   [x,fval,exitflag,output,lambda] = ...
      quadprog(H,f,A,b,[],[],lb,[],[],options);

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.

References

See Also

linprog | lsqlin | optimoptions