ktrlink - Find minimum of constrained or unconstrained nonlinear multivariable function using KNITRO third-party libraries

Equation

Finds the minimum of a problem specified by

where 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. All constraints are optional; ktrlink can minimize unconstrained problems.

Syntax

x = ktrlink(fun,x0) x = ktrlink(fun,x0,A,b) x = ktrlink(fun,x0,A,b,Aeq,beq) x = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub) x = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) x = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options, knitroOptions) [x,fval] = ktrlink(...) [x,fval,exitflag] = ktrlink(...) [x,fval,exitflag,output] = ktrlink(...) [x,fval,exitflag,output,lambda] = ktrlink(...)

Description

ktrlink attempts to find a minimum of a scalar function of several variables starting at an initial estimate. This is generally referred to as constrained or unconstrained 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 = ktrlink(fun,x0) starts at x0 and attempts to find a minimizer x of the function described in fun, subject to no constraints. x0 can be a scalar, vector, or matrix.

x = ktrlink(fun,x0,A,b) minimizes fun subject to the linear inequalities A*x ≤ b.

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

x = ktrlink(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 = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the nonlinear inequalities c(x) and the 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 = ktrlink(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 = ktrlink(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options, knitroOptions) minimizes with the KNITRO options specified in the text file knitroOptions. All options given in options are ignored except for HessFcn, HessMult, HessPattern, and JacobPattern.

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

[x,fval,exitflag] = ktrlink(...) returns exitflag, which describes the exit condition of the KNITRO solver.

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

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

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 contains descriptions of arguments passed to ktrlink. Options provides the function-specific details for the options values. This section provides function-specific details for fun and nonlcon.

fun

The function to be minimized. fun is a function that accepts a vector x and returns a scalar f, the objective function evaluated at x. fun can be specified as a function handle for an M-file function

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

where myfun is a MATLAB function such as

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

fun can also be a function handle for an anonymous function.

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

If you can compute the gradient of fun and the GradObj option is 'on', as set by

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

then fun must return the gradient vector g(x) in the second output argument.

If you can compute the Hessian matrix, there are several ways to pass the Hessian to ktrlink. See Hessian for details.

nonlcon

The function that computes the nonlinear inequality constraints c(x)≤ 0 and the nonlinear equality constraints ceq(x) = 0. nonlcon accepts a vector x and returns the two vectors c and ceq. c contains the nonlinear inequalities evaluated at x, and ceq contains the nonlinear equalities evaluated at x. The function nonlcon can be specified as a function handle.

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

where mycon is a MATLAB function such as

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

If you can compute the gradients of the constraints and the GradConstr option is 'on', as set by

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

then nonlcon must also return GC, the gradient of c(x), and GCeq, the gradient of ceq(x), in the third and fourth output arguments respectively. See Nonlinear Constraints for details.

Note Because Optimization Toolbox functions only accept inputs of type double, user-supplied objective and nonlinear constraint functions must return outputs of type double.

Passing Extra Parameters explains how to parameterize the nonlinear constraint function nonlcon, if necessary.

Output Arguments

Function Arguments contains descriptions of arguments returned by ktrlink. This section provides function-specific details for exitflag, lambda, and output:

`exitflag`	Integer identifying the reason the algorithm terminated. For more information, see the KNITRO documentation at `http://www.ziena.com/`
`lambda`	Structure containing the Lagrange multipliers at the solution `x` (separated by constraint type). The fields of the structure are
	`lower`	Lower bounds `lb`
	`upper`	Upper bounds `ub`
	`ineqlin`	Linear inequalities
	`eqlin`	Linear equalities
	`ineqnonlin`	Nonlinear inequalities
	`eqnonlin`	Nonlinear equalities
`output`	Structure containing information about the optimization. The fields of the structure are:
	`iterations`	Number of iterations taken
	`funcCount`	Number of function evaluations
	`constrviolation`	Maximum of constraint violations (interior-point algorithm only)
	`firstorderopt`	Measure of first-order optimality

Hessian

ktrlink can optionally use a user-supplied Hessian, the matrix of second derivatives of the Lagrangian, namely,

(11-2)

If you don't supply a Hessian, KNITRO software estimates it.

To provide a Hessian, 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

KNITRO software computes lambda. hessianfcn must calculate the sums in Equation 11-2. Indicate that you are supplying a Hessian by

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

There are several more options for Hessians:

options = optimset('Hessian','bfgs');
The KNITRO solver calculates the Hessian by a dense quasi-Newton approximation.
options = optimset('Hessian',... {'lbfgs',positive integer});
The KNITRO solver 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','fin-diff-grads',... 'SubproblemAlgorithm','cg','GradObj','on',... 'GradConstr','on');
The KNITRO solver 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 any nonlinear constraint functions.
options = optimset('Hessian','user-supplied',... 'SubproblemAlgorithm','cg','HessMult',@HessMultFcn);
The KNITRO solver 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 syntax for the 'HessMult' option 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 KNITRO software), and v is a vector.

Options

Optimization options used by ktrlink. Use optimset to set or change the values of fields in the options structure options. See Optimization Options for detailed information. For example:

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

Option	Description
`Algorithm`	Choose a KNITRO optimization algorithm: `'interior-point'` or `'active-set'`.
`AlwaysHonorConstraints`	The default `'bounds'` ensures that bound constraints are satisfied at every iteration. Disable by setting to `'none'`.
`Display`	Level of display: `'off'` displays no output. `'iter'` displays output at each iteration. `'final'` (default) displays just the final output.
`FinDiffType`	Finite differences, used to estimate gradients, are either `'forward'` (the default), or `'central'` (centered). `'central'` takes twice as many function evaluations but should be more accurate. `'central'` differences might violate bounds during their evaluation.
`GradObj`	Gradient for the objective function defined by the user. See the preceding description of `fun` to see how to define the gradient in `fun`. Set to `'on'` to have KNITRO use a user-defined gradient of the objective function. The default `'off'` causes KNITRO to estimate gradients using finite differences.
`HessFcn`	Function handle to a user-supplied Hessian (see Hessian).
`Hessian`	Chooses how `ktrlink` calculates the Hessian (see Hessian).
`HessMult`	Handle to a user-supplied function that gives a Hessian-times-vector product (see Hessian).
`InitBarrierParam`	Initial barrier value. A value above the default 0.1 might help, especially if the objective or constraint functions are large.
`InitTrustRegionRadius`	Initial radius of the trust region. On badly-scaled problems choose a value smaller than the default, , where n is the number of variables.
`MaxIter`	Maximum number of iterations allowed.
`MaxProjCGIter`	A tolerance (stopping criterion) for the number of projected conjugate gradient iterations; this is an inner iteration, not the number of iterations of the algorithm.
`ObjectiveLimit`	A tolerance (stopping criterion). If the objective function value goes below `ObjectiveLimit` and the iterate is feasible, the iterations halt, since the problem is presumably unbounded.
`ScaleProblem`	The default `'obj-and-constr'` causes the algorithm to normalize all constraints and the objective function. Disable by setting to `'none'`.
`SubproblemAlgorithm`	Determines how the iteration step is calculated. The default `'ldl-factorization'` is usually faster than `'cg'` (conjugate gradient), though `'cg'` may be faster for large problems with dense Hessians.
`TolFun`	Termination tolerance on the function value.
`TolCon`	Termination tolerance on the constraint violation.
`TolX`	Termination tolerance on `x`.

KNITRO Options

You can set options for the KNITRO libraries and pass them in a text file. The text file should consist of lines of text with the name of an option followed by blank space and then the desired value of the option. For example, to select the maximum run time to be less than 100 seconds, and to use an adaptive algorithm for changing the multiplier μ, create a text file containing the following lines: