Optimization Toolbox™

fmincon - Find minimum of constrained nonlinear multivariable function

Equation

Finds the minimum of a problem specified by

x, b, beq, lb, and ub are vectors, A and Aeq are matrices, c(x) and ceq(x) are functions that return vectors, and f(x) is a function that returns a scalar. f(x), c(x), and ceq(x) can be nonlinear functions.

Syntax

x = fmincon(fun,x0,A,b)
x = fmincon(fun,x0,A,b,Aeq,beq)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fmincon(problem)
[x,fval] = fmincon(...)
[x,fval,exitflag] = fmincon(...)
[x,fval,exitflag,output] = fmincon(...)
[x,fval,exitflag,output,lambda] = fmincon(...)
[x,fval,exitflag,output,lambda,grad] = fmincon(...)
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...)

Description

fmincon attempts to find a constrained minimum of a scalar function of several variables starting at an initial estimate. This is generally referred to as constrained nonlinear optimization or nonlinear programming.

Note   Passing Extra Parameters explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.

x = fmincon(fun,x0,A,b) starts at x0 and attempts to find a minimizer x of the function described in fun subject to the linear inequalities A*x ≤ b. x0 can be a scalar, vector, or matrix.

x = fmincon(fun,x0,A,b,Aeq,beq) minimizes fun subject to the linear equalities Aeq*x = beq and A*x ≤ b. If no inequalities exist, set A = [] and b = [].

x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables in x, so that the solution is always in the range lb ≤ x ≤ ub. If no equalities exist, set Aeq = [] and beq = []. If x(i) is unbounded below, set lb(i) = -Inf, and if x(i) is unbounded above, set ub(i) = Inf.

x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the nonlinear inequalities c(x) or equalities ceq(x) defined in nonlcon. fmincon optimizes such that c(x) ≤ 0 and ceq(x) = 0. If no bounds exist, set lb = [] and/or ub = [].

x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the optimization options specified in the structure options. Use optimset to set these options. If there are no nonlinear inequality or equality constraints, set nonlcon = [].

x = fmincon(problem) finds the minimum for problem, where problem is a structure described in Input Arguments.

Create the structure problem by exporting a problem from Optimization Tool, as described in Exporting to the MATLAB Workspace.

[x,fval] = fmincon(...) returns the value of the objective function fun at the solution x.

[x,fval,exitflag] = fmincon(...) returns a value exitflag that describes the exit condition of fmincon.

[x,fval,exitflag,output] = fmincon(...) returns a structure output with information about the optimization.

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

[x,fval,exitflag,output,lambda,grad] = fmincon(...) returns the value of the gradient of fun at the solution x.

[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...) returns the value of the Hessian at the solution x. See Hessian.

Note   If the specified input bounds for a problem are inconsistent, the output x is x0 and the output fval is []. Components of x0 that violate the bounds lb ≤ x ≤ ub are reset to the interior of the box defined by the bounds. Components that respect the bounds are not changed.

Input Arguments

Function Arguments describes the arguments passed to fmincon. Options provides the function-specific details for the options values. This section provides function-specific details for fun, nonlcon, and problem.

x = fmincon(@myfun,x0,A,b)

function f = myfun(x)
f = ...            % Compute function value at x

x = fmincon(@(x)norm(x)^2,x0,A,b);

options = optimset('GradObj','on')

x = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)

function [c,ceq] = mycon(x)
c = ...     % Compute nonlinear inequalities at x.
ceq = ...   % Compute nonlinear equalities at x.

options = optimset('GradConstr','on')

Output Arguments

Function Arguments describes arguments returned by fmincon. This section provides function-specific details for exitflag, lambda, and output:

Hessian

fmincon uses a Hessian, the second derivatives of the Lagrangian (see Equation 2-2), namely,

(9-1)

There are three algorithms used by fmincon, and each one handles Hessians differently:

• The active-set algorithm does not accept a user-supplied Hessian. It computes a quasi-Newton approximation to the Hessian of the Lagrangian.

• The trust-region-reflective can accept a user-supplied Hessian as the final output of the objective function. Since this algorithm has only bounds or linear constraints, the Hessian of the Lagrangian is same as the Hessian of the objective function. See Writing Objective Functions for details on how to pass the Hessian to fmincon. Indicate that you are supplying a Hessian by

  options = optimset('Hessian','user-supplied');

  If you do not pass a Hessian, the algorithm computes a finite-difference approximation.

• The interior-point algorithm can accept a user-supplied Hessian as a separately defined function—it is not computed in the objective function. The syntax is

  hessian = hessianfcn(x, lambda)

  hessian is an n-by-n matrix, sparse or dense, where n is the number of variables. lambda is a structure with the Lagrange multiplier vectors associated with the nonlinear constraints:

  lambda.ineqnonlin
  lambda.eqnonlin

  fmincon computes the structure lambda. hessianfcn must calculate the sums in Equation 9-1. Indicate that you are supplying a Hessian by

  options = optimset('Hessian','user-supplied',...
                     'HessFcn',@hessianfcn);

The interior-point algorithm has several more options for Hessians:

• options = optimset('Hessian','bfgs');

  fmincon calculates the Hessian by a dense quasi-Newton approximation.

• options = optimset('Hessian',{'lbfgs',positive integer});

  fmincon calculates the Hessian by a limited-memory, large-scale quasi-Newton approximation. The positive integer specifies how many past iterations should be remembered.

• options = optimset('Hessian','lbfgs');

  fmincon calculates the Hessian by a limited-memory, large-scale quasi-Newton approximation. The default memory, 10 iterations, is used.

• options = optimset('Hessian','fin-diff-grads',... 'SubproblemAlgorithm','cg','GradObj','on',... 'GradConstr','on');

  fmincon calculates a Hessian-times-vector product by finite differences of the gradient(s). You must supply the gradient of the objective function, and also gradients of nonlinear constraints if they exist.

• options = optimset('Hessian','on',... 'SubproblemAlgorithm','cg', 'HessMult',@HessMultFcn]);

  fmincon uses a Hessian-times-vector product. You must supply the function HessMultFcn, which returns an n-by-1 vector. The HessMult option enables you to pass the result of multiplying the Hessian by a vector without calculating the Hessian.

The 'HessMult' option for the interior-point algorithm has a different syntax than that of the trust-region-reflective algorithm. The syntax for the interior-point algorithm is

W = HessMultFcn(x,lambda,v);

The result W should be the product H*v, where H is the Hessian at x, lambda is the Lagrange multiplier (computed by fmincon), and v is a vector. In contrast, the syntax for the trust-region-reflective algorithm does not involve lambda:

W = HessMultFcn(H,v);

Again, the result W = H*v. H is the function returned in the third output of the objective function (see Writing Objective Functions), and v is a vector. H does not have to be the Hessian; rather, it can be any function that enables you to calculate W = H*v.

Options

Optimization options used by fmincon. Some options apply to all algorithms, and others are relevant for particular algorithms. You can use optimset to set or change the values of these fields in the structure options. See Optimization Options for detailed information.

fmincon uses one of three algorithms: active-set, interior-point, or trust-region-reflective. You choose the algorithm at the command line with optimset. For example:

options=optimset('Algorithm','active-set');

The default trust-region-reflective (formerly called large-scale) requires:

• A gradient to be supplied in the objective function

• 'GradObj' to be set to 'on'

• Either bound constraints or linear equality constraints, but not both

If these conditions are not all satisfied, the 'active-set' algorithm (formerly called medium-scale) is the default.

The 'active-set' algorithm is not a large-scale algorithm.

All Algorithms

These options are used by all three algorithms:

Trust-Region-Reflective Algorithm

These options are used by the trust-region-reflective algorithm:

W = hmfun(Hinfo,Y)

[f,g,Hinfo] = fun(x)

Active-Set Algorithm

These options are used only by the active-set algorithm:

Interior-Point Algorithm

These options are used by the interior-point algorithm:

Examples

Find values of x that minimize f(x) = –x₁x₂x₃, starting at the point x = [10;10;10], subject to the constraints:

0 ≤ x₁ + 2x₂ + 2x₃ ≤ 72.

1. Write an M-file that returns a scalar value f of the objective function evaluated at x:

   function f = myfun(x)
   f = -x(1) * x(2) * x(3);
   

2. Rewrite the constraints as both less than or equal to a constant,

   –x₁–2x₂–2x₃ ≤ 0
   x₁ + 2x₂ + 2x₃≤ 72

3. Since both constraints are linear, formulate them as the matrix inequality A·x ≤ b, where

   

4. Supply a starting point and invoke an optimization routine:

   x0 = [10; 10; 10];    % Starting guess at the solution
   [x,fval] = fmincon(@myfun,x0,A,b)
   

5. After 66 function evaluations, the solution is

   x =
       24.0000
       12.0000
       12.0000
   

   where the function value is

   fval =
       -3.4560e+03
   

   and linear inequality constraints evaluate to be less than or equal to 0:

   A*x-b= 
       -72
         0
   

Notes

Trust-Region-Reflective Optimization

To use the trust-region-reflective algorithm, you must

• Supply the gradient of the objective function in fun.

• Set GradObj to 'on' in options.

• Specify the feasible region using one, but not both, of the following types of constraints:

  • Upper and lower bounds constraints

  • Linear equality constraints, in which the equality constraint matrix Aeq cannot have more rows than columns

You cannot use inequality constraints with the trust-region-reflective algorithm. If the preceding conditions are not met, fmincon reverts to the active-set algorithm.

fmincon returns a warning if you do not provide a gradient and the Algorithm option is trust-region-reflective. fmincon permits an approximate gradient to be supplied, but this option is not recommended; the numerical behavior of most optimization methods is considerably more robust when the true gradient is used.

The trust-region-reflective method in fmincon is in general most effective when the matrix of second derivatives, i.e., the Hessian matrix H(x), is also computed. However, evaluation of the true Hessian matrix is not required. For example, if you can supply the Hessian sparsity structure (using the HessPattern option in options), fmincon computes a sparse finite-difference approximation to H(x).

If x0 is not strictly feasible, fmincon chooses a new strictly feasible (centered) starting point.

If components of x have no upper (or lower) bounds, fmincon prefers that the corresponding components of ub (or lb) be set to Inf (or -Inf for lb) as opposed to an arbitrary but very large positive (or negative in the case of lower bounds) number.

Take note of these characteristics of linearly constrained minimization:

• A dense (or fairly dense) column of matrix Aeq can result in considerable fill and computational cost.

• fmincon removes (numerically) linearly dependent rows in Aeq; however, this process involves repeated matrix factorizations and therefore can be costly if there are many dependencies.

• Each iteration involves a sparse least-squares solution with matrix

  

  where R^T is the Cholesky factor of the preconditioner. Therefore, there is a potential conflict between choosing an effective preconditioner and minimizing fill in .

Active-Set Optimization

If equality constraints are present and dependent equalities are detected and removed in the quadratic subproblem, 'dependent' appears under the Procedures heading (when you ask for output by setting the Display option to'iter'). The dependent equalities are only removed when the equalities are consistent. If the system of equalities is not consistent, the subproblem is infeasible and 'infeasible' appears under the Procedures heading.

Algorithm

Trust-Region-Reflective Optimization

The trust-region-reflective algorithm is a subspace trust-region method and is based on the interior-reflective Newton method described in [3] and [4]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). See the trust-region and preconditioned conjugate gradient method descriptions in fmincon Trust Region Reflective Algorithm.

Active-Set Optimization

fmincon uses a sequential quadratic programming (SQP) method. In this method, the function solves a quadratic programming (QP) subproblem at each iteration. fmincon updates an estimate of the Hessian of the Lagrangian at each iteration using the BFGS formula (see fminunc and references [7] and [8]).

fmincon performs a line search using a merit function similar to that proposed by [6], [7], and [8]. The QP subproblem is solved using an active set strategy similar to that described in [5]. fmincon Active Set Algorithm describes this algorithm in detail.

See also SQP Implementation for more details on the algorithm used.

Interior-Point Optimization

This algorithm is described in [1], [41], and [9].

Limitations

fmincon is a gradient-based method that is designed to work on problems where the objective and constraint functions are both continuous and have continuous first derivatives.

When the problem is infeasible, fmincon attempts to minimize the maximum constraint value.

The trust-region-reflective algorithm does not allow equal upper and lower bounds. For example, if lb(2)==ub(2), fmincon gives this error:

Equal upper and lower bounds not permitted in this
large-scale method.
Use equality constraints and the medium-scale
method instead.

There are two different syntaxes for passing a Hessian, and there are two different syntaxes for passing a HessMult function; one for trust-region-reflective, and another for interior-point.

For trust-region-reflective, the Hessian of the Lagrangian is the same as the Hessian of the objective function. You pass that Hessian as the third output of the objective function.

For interior-point, the Hessian of the Lagrangian involves the Lagrange multipliers and the Hessians of the nonlinear constraint functions. You pass the Hessian as a separate function that takes into account both the position x and the Lagrange multiplier structure lambda.

Trust-Region-Reflective Coverage and Requirements

References

[1] Byrd, R.H., J. C. Gilbert, and J. Nocedal, "A Trust Region Method Based on Interior Point Techniques for Nonlinear Programming," Mathematical Programming, Vol 89, No. 1, pp. 149–185, 2000.

[2] Byrd, R.H., Mary E. Hribar, and Jorge Nocedal, "An Interior Point Algorithm for Large-Scale Nonlinear Programming, SIAM Journal on Optimization," SIAM Journal on Optimization, Vol 9, No. 4, pp. 877–900, 1999.

[3] Coleman, T.F. and Y. Li, "An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds," SIAM Journal on Optimization, Vol. 6, pp. 418–445, 1996.

[4] Coleman, T.F. and Y. Li, "On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds," Mathematical Programming, Vol. 67, Number 2, pp. 189–224, 1994.

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

[6] Han, S.P., "A Globally Convergent Method for Nonlinear Programming," Vol. 22, Journal of Optimization Theory and Applications, p. 297, 1977.

[7] Powell, M.J.D., "A Fast Algorithm for Nonlinearly Constrained Optimization Calculations," Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.

[8] Powell, M.J.D., "The Convergence of Variable Metric Methods For Nonlinearly Constrained Optimization Calculations," Nonlinear Programming 3 (O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, eds.), Academic Press, 1978.

[9] Waltz, R. A., J. L. Morales, J. Nocedal, and D. Orban, "An interior algorithm for nonlinear optimization that combines line search and trust region steps," Mathematical Programming, Vol 107, No. 3, pp. 391–408, 2006.

See Also

@ (function_handle), fminbnd, fminsearch, fminunc, optimset, optimtool

For more details about the fmincon algorithms, see Constrained Nonlinear Optimization. For more examples of nonlinear programming with constraints, see Constrained Nonlinear Optimization Examples.

fminbnd

fminimax