| Optimization Toolbox™ | |
| On this page… |
|---|
Iterations and Function Counts First-Order Optimality Measure Tolerances and Stopping Criteria |
In general, Optimization Toolbox™ solvers iterate to find an optimum. This means a solver begins at an initial value x0, performs some intermediate calculations that eventually lead to a new point x1, and then repeats the process to find successive approximations x2, x3, ... of the local minimum. Processing stops after some number of iterations k.
At any step, intermediate calculations may involve evaluating the objective function and constraints, if any, at points near the current iterate xi. For example, the solver may estimate a gradient by finite differences. At each of these nearby points, the function count (F-count) is increased by one.
If there are no constraints, the F-count reports the total number of objective function evaluations.
If there are constraints, the F-count reports only the number of points where function evaluations took place, not the total number of evaluations of constraint functions.
If there are many constraints, the F-count can be significantly less than the total number of function evaluations.
F-count is a header in the iterative display for many solvers. For an example, see Interpreting the Result.
The F-count appears in the output structure as output.funcCount. This enables you to access the evaluation count programmatically. For more information on output structures, see Output Structures.
Note Intermediate calculations do not count towards the reported number of iterations k. The number of iterations is the total number of steps xi, 1 ≤ i ≤ k. |
First-order optimality is a measure of how close a point x is to optimal. It is used in all smooth solvers, constrained and unconstrained, though it has different meanings depending on the problem and solver. For more information about first-order optimality, see [1].
The tolerance TolFun relates to the first-order optimality measure. If the optimality measure is less than TolFun, the solver iterations will end.
For a smooth unconstrained problem,
the optimality measure is the infinity-norm (i.e., maximum absolute value) of ∇f(x):
This measure of optimality is based on the familiar condition for a smooth function to achieve a minimum: its gradient must be zero. For unconstrained problems, when the first-order optimality measure is nearly zero, the objective function has gradient nearly zero, so the objective function could be nearly minimized. If the first-order optimality measure is not small, the objective function is not minimized.
The theory behind the definition of first-order optimality measure for constrained problems. The definition as used in Optimization Toolbox functions is in Constrained Optimality in Solver Form.
For a smooth constrained problem let g and h be vector functions representing all inequality and equality constraints respectively (i.e., bound, linear, and nonlinear constraints):
The meaning of first-order optimality in this case is more involved than for unconstrained problems. The definition is based on the Karush-Kuhn-Tucker (KKT) conditions. The KKT conditions are analogous to the condition that the gradient must be zero at a minimum, modified to take constraints into account. The difference is that The KKT conditions hold for constrained problems.
The KKT conditions are given via an auxiliary Lagrangian function
 | (2-2) |
The vector λ is called the Lagrange multiplier vector. Its length is the total number of constraints.
 | (2-3) |
 | (2-4) |
 | (2-5) |
The three expressions in Equation 2-5 are not used in the calculation of optimality measure.
The optimality measure associated with Equation 2-3 is
 | (2-6) |
The optimality measure associated with Equation 2-4 is
 | (2-7) |
where the infinity norm (maximum) is used for the vector
.
The combined optimality measure is the maximum of the values calculated in Equation 2-6 and Equation 2-7. Any constraint violations g(x) > 0 or |h(x)| > 0 are measured and reported as tolerance violations; see Tolerances and Stopping Criteria.
The first-order optimality measure used by toolbox solvers is expressed as follows for constraints given separately by bounds, linear functions, and nonlinear functions. The measure is the maximum of the following two norms, which correspond to Equation 2-6 and Equation 2-7:
 | (2-8) |
 | (2-9) |
where the infinity norm (maximum) is used for the vector in Equation 2-8 and in Equation 2-9. The summations in Equation 2-8 range over all constraints. If a bound is ±Inf, that term is not considered constrained, so is not part of the summation.
For some large-scale problems with only linear equalities, the first-order optimality measure is the infinity norm of the projected gradient (i.e., the gradient projected onto the nullspace of Aeq).
The number of iterations in an optimization depends on a solver's stopping criteria. These criteria include:
First-order optimality measure
Tolerance TolX
Tolerance TolFun
Tolerance TolCon
Bound on number of iterations taken MaxIter
Bound on number of function evaluations MaxFunEvals
First-order optimality measure is defined in First-Order Optimality Measure. Iterations and function evaluations are discussed in Iterations and Function Counts. The remainder of this section describes how Optimization Toolbox solvers use stopping criteria to terminate optimizations.
TolX is a lower bound on the size of a step, meaning the norm of (xi – xi+1). If the solver attempts to take a step that is smaller than TolX, the iterations end. TolX is sometimes used as a relative bound, meaning iterations end when |(xi – xi+1)| < TolX*(1 + |xi|), or a similar relative measure.
TolFun is a lower bound on the change in the value of the objective function during a step. If |f(xi) – f(xi+1)| < TolFun, the iterations end. TolFun is sometimes used as a relative bound, meaning iterations end when |f(xi) – f(xi+1)| < TolFun(1 + |f(xi)|), or a similar relative measure.
TolFun is also a bound on the first-order optimality measure. If the optimality measure is less than TolFun, the iterations end. TolFun can also be a relative bound.
TolCon is an upper bound on the magnitude of any constraint functions. If a solver returns a point x with c(x) > TolCon or |ceq(x)| > TolCon, the solver reports that the constraints are violated at x. TolCon can also be a relative bound.
Note TolCon operates differently from other tolerances. If TolCon is not satisfied (i.e., if the magnitude of the constraint function exceeds TolCon), the solver attempts to continue, unless it is halted for another reason. A solver does not halt simply because TolCon is satisfied. |
There are two other tolerances that apply to particular solvers: TolPCG and MaxPCGIter. These relate to preconditioned conjugate gradient steps. For more information, see Preconditioned Conjugate Gradients.
There are several tolerances that apply only to the interior-point algorithm in the solver fmincon. See Optimization Options for more information.
Constrained optimization involves a set of Lagrange multipliers, as described in First-Order Optimality Measure. Solvers return estimated Lagrange multipliers in a structure. The structure is called lambda, since the conventional symbol for Lagrange multipliers is the Greek letter lambda (λ). The structure separates the multipliers into the following types, called fields:
lower, associated with lower bounds
upper, associated with upper bounds
eqlin, associated with linear equalities
ineqlin, associated with linear inequalities
eqnonlin, associated with nonlinear equalities
ineqnonlin, associated with nonlinear inequalities
To access, for example, the nonlinear inequality field of a Lagrange multiplier structure, enter lambda.inqnonlin. To access the third element of the Lagrange multiplier associated with lower bounds, enter lambda.lower(3).
The content of the Lagrange multiplier structure depends on the solver. For example, linear programming has no nonlinearities, so it does not have eqnonlin or ineqnonlin fields. Each applicable solver's function reference pages contains a description of its Lagrange multiplier structure under the heading "Outputs."
An output structure contains information on a solver's result. All solvers can return an output structure. To obtain an output structure, invoke the solver with the output structure in the calling syntax. For example, to get an output structure from lsqnonlin, use the syntax
[x,resnorm,residual,exitflag,output] = lsqnonlin(...)
You can also obtain an output structure by running a problem using the Optimization Tool. All results exported from Optimization Tool contain an output structure.
The contents of the output structure are listed in each solver's reference pages. For example, the output structure returned by lsqnonlin contains firstorderopt, iterations, funcCount, cgiterations, stepsize, algorithm, and message. To access, for example, the message, enter output.message.
Optimization Tool exports results in a structure. The results structure contains the output structure. To access, for example, the number of iterations, use the syntax optimresults.output.iterations.
You can also see the contents of an output structure by double-clicking the output structure in the MATLAB® Workspace pane.
For some problems, you might want output from an optimization algorithm at each iteration. For example, you might want to find the sequence of points that the algorithm computes and plot those points. To do this, create an output function that the optimization function calls at each iteration. See Output Function for details and syntax.
Generally, the solvers that can employ an output function are the ones that can take nonlinear functions as inputs. You can determine which solvers can have an output function by looking in the Options section of function reference pages, or by checking whether the Output function option is available in the Optimization Tool GUI for a solver.
What the Example Contains. The following example continues the one in Nonlinear Inequality Constrained Example, which calls the function fmincon at the command line to solve a nonlinear, constrained optimization problem. The example in this section uses an M-file to call fmincon. The M-file also contains all the functions needed for the example, including:
The objective function
The constraint function
An output function that records the history of points computed by the algorithm for fmincon. At each iteration of the algorithm for fmincon, the output function:
Plots the current point computed by the algorithm.
Stores the point and its corresponding objective function value in a variable called history, and stores the current search direction in a variable called searchdir. The search direction is a vector that points in the direction from the current point to the next one.
The code for the M-file is here: Writing the Example M-File.
Writing the Output Function. You specify the output function in the options structure
options = optimset('OutputFcn',@outfun)where outfun is the name of the output function. When you call an optimization function with options as an input, the optimization function calls outfun at each iteration of its algorithm.
In general, outfun can be any MATLAB function, but in this example, it is a nested subfunction of the M-file described in Writing the Example M-File. The following code defines the output function:
function stop = outfun(x,optimValues,state)
stop = false;
switch state
case 'init'
hold on
case 'iter'
% Concatenate current point and objective function
% value with history. x must be a row vector.
history.fval = [history.fval; optimValues.fval];
history.x = [history.x; x];
% Concatenate current search direction with
% searchdir.
searchdir = [searchdir;...
optimValues.searchdirection'];
plot(x(1),x(2),'o');
% Label points with iteration number.
text(x(1)+.15,x(2),num2str(optimValues.iteration));
case 'done'
hold off
otherwise
end
endSee Using Function Handles with Nested Functions in the MATLAB Programming Fundamentals documentation for more information about nested functions.
The arguments that the optimization function passes to outfun are:
x — The point computed by the algorithm at the current iteration
optimValues — Structure containing data from the current iteration
The example uses the following fields of optimValues:
optimValues.iteration — Number of the current iteration
optimValues.fval — Current objective function value
optimValues.searchdirection — Current search direction
state — The current state of the algorithm ('init', 'interrupt', 'iter', or 'done')
For more information about these arguments, see Output Function.
Writing the Example M-File. To create the M-file for this example:
Copy and paste the following code into the M-file:
function [history,searchdir] = runfmincon
% Set up shared variables with OUTFUN
history.x = [];
history.fval = [];
searchdir = [];
% call optimization
x0 = [-1 1];
options = optimset('outputfcn',@outfun,'display','iter',...
'largescale','off');
xsol = fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options);
function stop = outfun(x,optimValues,state)
stop = false;
switch state
case 'init'
hold on
case 'iter'
% Concatenate current point and objective function
% value with history. x must be a row vector.
history.fval = [history.fval; optimValues.fval];
history.x = [history.x; x];
% Concatenate current search direction with
% searchdir.
searchdir = [searchdir;...
optimValues.searchdirection'];
plot(x(1),x(2),'o');
% Label points with iteration number and add title.
text(x(1)+.15,x(2),...
num2str(optimValues.iteration));
title('Sequence of Points Computed by fmincon');
case 'done'
hold off
otherwise
end
end
function f = objfun(x)
f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) +...
2*x(2) + 1);
end
function [c, ceq] = confun(x)
% Nonlinear inequality constraints
c = [1.5 + x(1)*x(2) - x(1) - x(2);
-x(1)*x(2) - 10];
% Nonlinear equality constraints
ceq = [];
end
endSave the file as runfmincon.m in a directory on the MATLAB path.
Running the Example. To run the example, enter:
[history searchdir] = runfmincon;
This displays the following iterative output in the Command Window.
Max Line search Directional First-order
Iter F-count f(x) constraint steplength derivative optimality Procedure
0 3 1.8394 0.5 Infeasible start point
1 6 1.85127 -0.09197 1 -0.027 0.778
2 9 0.300167 9.33 1 -0.825 0.313 Hessian modified
3 12 0.529835 0.9209 1 0.302 0.232 twice
4 16 0.186965 -1.517 0.5 -0.437 0.13
5 19 0.0729085 0.3313 1 -0.0715 0.054
6 22 0.0353323 -0.03303 1 -0.026 0.0271
7 25 0.0235566 0.003184 1 -0.00963 0.00587
8 28 0.0235504 9.032e-008 1 -6.22e-006 8.51e-007
Optimization terminated: first-order optimality measure less
than options.TolFun and maximum constraint violation is less
than options.TolCon.
Active inequalities (to within options.TolCon = 1e-006):
lower upper ineqlin ineqnonlin
1
2
The output history is a structure that contains two fields:
history =
x: [9x2 double]
fval: [9x1 double]The fval field contains the objective function values corresponding to the sequence of points computed by fmincon:
history.fval
ans =
1.8394
1.8513
0.3002
0.5298
0.1870
0.0729
0.0353
0.0236
0.0236These are the same values displayed in the iterative output in the column with header f(x).
The x field of history contains the sequence of points computed by the algorithm:
history.x ans = -1.0000 1.0000 -1.3679 1.2500 -5.5708 3.4699 -4.8000 2.2752 -6.7054 1.2618 -8.0679 1.0186 -9.0230 1.0532 -9.5471 1.0471 -9.5474 1.0474
This example displays a plot of this sequence of points, in which each point is labeled by its iteration number.
The optimal point occurs at the eighth iteration. Note that the last two points in the sequence are so close that they overlap.
The second output argument, searchdir, contains the search directions for fmincon at each iteration. The search direction is a vector pointing from the point computed at the current iteration to the point computed at the next iteration:
searchdir =
-0.3679 0.2500
-4.2029 2.2199
0.7708 -1.1947
-3.8108 -2.0268
-1.3625 -0.2432
-0.9552 0.0346
-0.5241 -0.0061
-0.0003 0.0003
| Choosing a Solver | Local vs. Global Optima | |
| © 1984-2008- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |