fminimax (Optimization Toolbox)

Solve the minimax problem

where x, b, beq, lb, and ub are vectors, A and Aeq are matrices, c(x), ceq(x), and F(x) are functions that return vectors. F(x), c(x), and ceq(x) can be nonlinear functions.

Syntax

x = fminimax(fun,x0)
x = fminimax(fun,x0,A,b)
x = fminimax(fun,x0,A,b,Aeq,beq)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,...)
[x,fval] = fminimax(...)
[x,fval,maxfval] = fminimax(...)
[x,fval,maxfval,exitflag] = fminimax(...)
[x,fval,maxfval,exitflag,output] = fminimax(...)
[x,fval,maxfval,exitflag,output,lambda] = fminimax(...)

Description

fminimax minimizes the worst-case value of a set of multivariable functions, starting at an initial estimate. The values may be subject to constraints. This is generally referred to as the minimax problem.

x = fminimax(fun,x0)

starts at x0 and finds a minimax solution x to the functions described in fun.

x = fminimax(fun,x0,A,b)

solves the minimax problem subject to the linear inequalities A*x <= b.

x = fminimax(fun,x,A,b,Aeq,beq)

solves the minimax problem subject to the linear equalities Aeq*x = beq as well. Set A=[] and b=[] if no inequalities exist.

x = fminimax(fun,x,A,b,Aeq,beq,lb,ub)

defines a set of lower and upper bounds on the design variables, x, so that the solution is always in the range lb <= x <= ub.

x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)

subjects the minimax problem to the nonlinear inequalities c(x) or equality constraints ceq(x) defined in nonlcon. fminimax optimizes such that c(x) <= 0 and ceq(x) = 0. Set lb=[] and/or ub=[] if no bounds exist.

x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

minimizes with the optimization parameters specified in the structure options.

x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,...)

passes the problem-dependent parameters P1, P2, etc., directly to the functions fun and nonlcon. Pass empty matrices as placeholders for A, b, Aeq, beq, lb, ub, nonlcon, and options if these arguments are not needed.

[x,fval] = fminimax(...)

returns the value of the objective function fun at the solution x.

[x,fval,maxfval] = fminimax(...)

returns the maximum function value at the solution x.

[x,fval,maxfval,exitflag] = fminimax(...)

returns a value exitflag that describes the exit condition of fminimax.

[x,fval,maxfval,exitflag,output] = fminimax(...)

returns a structure output with information about the optimization.

[x,fval,maxfval,exitflag,output,lambda] = fminimax(...)

returns a structure lambda whose fields contain the Lagrange multipliers at the solution x.

Arguments

The arguments passed into the function are described in Table 1-1. The arguments returned by the function are described in Table 1-2. Details relevant to fminimax are included below for fun, nonlcon, options, exitflag, lambda, maxfval, and output.


`fun`	The function to be minimized. `fun` takes a vector `x` and returns a vector `F` of the objective functions evaluated at `x`. You can specify `fun` to be an inline object. For example, fun = inline('sin(x.*x)'); Alternatively, `fun` can be a string containing the name of a function (an M-file, a built-in function, or a MEX-file). If `fun='myfun'` then the M-file function `myfun.m` would have the form function F = myfun(x) F = ... % Compute function values at x
	To minimize the worst case absolute values of any of the elements of the vector F(x) (i.e., min`{`max abs{F(x)} } ), partition those objectives into the first elements of `F` and set `options.MinAbsMax` to be the number of such objectives. If the gradient of the objective function can also be computed and `options.GradObj` is `'on'`, as set by options = optimset('GradObj','on') then the function `fun` must return, in the second output argument, the gradient value `G`, a matrix, at `x`. Note that by checking the value of `nargout` the function can avoid computing `G` when '`myfun'` is called with only one output argument (in the case where the optimization algorithm only needs the value of `F` but not `G`):
	function [F,G] = myfun(x) F = ... % compute the function values at x if nargout > 1 % two output arguments G = ... % gradients evaluated at x end
	The gradient is the partial derivatives dF/dx of each `F` at the point `x`. If `F` is a vector of length `m` and `x` has length `n`, then the gradient `G` of `F(x)` is an n-by-m matrix where `G(i,j)` is the partial derivative of `F(j)` with respect to `x(i)` (i.e., the `j`th column of `G` is the gradient of the `j`th objective function `F(j)`).
`nonlcon`	The function that computes the nonlinear inequality constraints `c(x) <=0` and nonlinear equality constraints `ceq(x)=0`. `nonlcon` is a string containing the name of a function (an M-file, a built-in, or a MEX-file). `nonlcon` takes a vector `x` and returns two arguments, a vector `c` of the nonlinear inequalities evaluated at `x` and a vector `ceq` of the nonlinear equalities evaluated at `x`. For example, if `nonlcon='mycon'` then the M-file `mycon.m` would have the form function [c,ceq] = mycon(x) c = ... % Compute nonlinear inequalities at x ceq = ... % Compute the nonlinear equalities at x If the gradients of the constraints can also be computed and `options.GradConstr` is `'on'`, as set by options = optimset('GradConstr','on')
	then the function `nonlcon` must also return, in the third and fourth output arguments, `GC`, the gradient of `c(x)`, and `GCeq`, the gradient of `ceq(x)`. Note that by checking the value of `nargout` the function can avoid computing `GC` and `GCeq` when `nonlcon` is called with only two output arguments (in the case where the optimization algorithm only needs the values of `c` and `ceq` but not `GC` and `GCeq`):
	function [c,ceq,GC,GCeq] = mycon(x) c = ... % nonlinear inequalities at x ceq = ... % nonlinear equalities at x if nargout > 2 % nonlcon called with 4 outputs GC = ... % gradients of the inequalities GCeq = ... % gradients of the equalities end
	If `nonlcon` returns a vector `c` of `m` components and `x` has length `n`, then the gradient `GC` of `c(x)` is an n-by-m matrix, where `GC(i,j)` is the partial derivative of `c(j)` with respect to `x(i)` (i.e., the `j`th column of `GC` is the gradient of the `j`th inequality constraint `c(j)`). Likewise, if `ceq` has `p` components, the gradient `GCeq` of `ceq(x)` is an n-by-p matrix, where `GCeq(i,j)` is the partial derivative of `ceq(j)` with respect to `x(i)` (i.e., the `j`th column of `GCeq` is the gradient of the `j`th equality constraint `ceq(j)`).
`options`	Optimization parameter options. You can set or change the values of these parameters using the `optimset` function. `DerivativeCheck` - Compare user-supplied derivatives (gradients of the objective or constraints) to finite-differencing derivatives. `Diagnostics` - Print diagnostic information about the function to be minimized or solved. `DiffMaxChange` - Maximum change in variables for finite-difference gradients. `DiffMinChange` - Minimum change in variables for finite-difference gradients. `Display` - Level of display. `'off'` displays no output; `'iter'` displays output at each iteration; `'final'` displays just the final output.
	`GradConstr` - Gradient for the constraints defined by user. See the description of `nonlcon` under the Arguments section above to see how to define the gradient in `nonlcon`. `GradObj` - Gradient for the objective function defined by user. See the description of `fun` under the Arguments section above to see how to define the gradient in `fun`. The gradient must be provided to use the large-scale method. It is optional for the medium-scale method. `MaxFunEvals` - Maximum number of function evaluations allowed. `MaxIter` - Maximum number of iterations allowed.
	`MeritFunction` - Use goal attainment/minimax merit function if set to `'multiobj`'. Use `fmincon` merit function if set to `'singleobj'`. `MinAbsMax` - Number of F(x) to minimize the worst case absolute values. `TolCon` - Termination tolerance on the constraint violation. `TolFun` - Termination tolerance on the function value. `TolX` - Termination tolerance on `x`.
`exitflag`	Describes the exit condition: `> 0` indicates that the function converged to a solution `x`. `0` indicates that the maximum number of function evaluations or iterations was reached. `< 0` indicates that the function did not converge to a solution.
`lambda`	A structure containing the Lagrange multipliers at the solution `x` (separated by constraint type): `lambda.lower` for the lower bounds `lb` `lambda.upper` for the upper bounds `ub` `lambda.ineqlin` for the linear inequalities `lambda.eqlin` for the linear equalities `lambda.ineqnonlin` for the nonlinear inequalities `lambda.eqnonlin` for the nonlinear equalities
`maxfval`	Maximum of the function values evaluated at the solution `x`, that is, `maxfval = max{fun(x)}`.
`output`	A structure whose fields contain information about the optimization: `output.iterations` - The number of iterations taken. `output.funcCount` - The number of function evaluations. `output.algorithm` - The algorithm used.

Examples

Find values of x that minimize the maximum value of

where

First, write an M-file that computes the five functions at x:

function f = myfun(x)
f(1)= 2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;     %Objectives
f(2)= -x(1)^2 - 3*x(2)^2;
f(3)= x(1) + 3*x(2) -18;
f(4)= -x(1)- x(2);
f(5)= x(1) + x(2) - 8;

Next, invoke an optimization routine:

x0 = [0.1; 0.1];       % Make a starting guess at solution
[x,fval] = fminimax('myfun',x0)

After seven iterations, the solution is

x = 
     4.0000
     4.0000
fval =
     0.0000  -64.0000  -2.0000  -8.0000  -0.0000

Notes

The number of objectives for which the worst case absolute values of F are minimized is set in options.MinAbsMax. Such objectives should be partitioned into the first elements of F.

For example, consider the above problem, which requires finding values of x that minimize the maximum absolute value of

This is solved by invoking fminimax with the commands

x0 = [0.1; 0.1];   % Make a starting guess at the solution
options = optimset('MinAbsMax',5);   % Minimize absolute values
[x,fval] = fminimax(fun,x0,[],[],[],[],[],[],[],options);

After seven iterations, the solution is

x = 
     4.9256
     2.0796
fval = 
    37.2356 -37.2356 -6.8357 -7.0052 -0.9948

If equality constraints are present and dependent equalities are detected and removed in the quadratic subproblem, 'dependent' is printed under the Procedures heading (when the output option is options.Display='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' is printed under the Procedures heading.

Algorithm

fminimax uses a Sequential Quadratic Programming (SQP) method [3]. Modifications are made to the line search and Hessian. In the line search an exact merit function (see [4] and [5]) is used together with the merit function proposed by [1] and [2]. The line search is terminated when either merit function shows improvement. A modified Hessian that takes advantage of special structure of this problem is also used. Setting options.MeritFunction = 'singleobj' uses the merit function and Hessian used in fmincon.

See also the SQP implementation section in the Introduction to Algorithms chapter for more details on the algorithm used and the types of procedures printed under the Procedures heading for options.Display='iter' setting.

Limitations

The function to be minimized must be continuous. fminimax may only give local solutions.