TOMLAB OPTIMIZATION ENVIRONMENT: sTrustr

sTrustr

Purpose

For solving optimization problems constrained by a convex feasible region.

Syntax

   Result = sTrustr(Prob, varargin);

Description

Structured Trust Region algorithm

Ref. A. R. Conn, Nick Gould, A. Sartenaer, Ph. L. Toint, "Convergence Properties of Minimization Algorithms For Convex Constraints Using A Structured Trust Region", July 4, 1995

sTrustr implements an algorithm for solving linearly constrained minimization problems

It handles nonlinear constraints, but might fail if the constraints are nonconvex.

Run e.g. conSolve or nlpSolve for nonlinearly constrained problems.

sTrustr runs different methods to obtain the gradient g and the Hessian H, dependent on the parameters Prob.Solver.Alg, Prob.NumDiff, Prob.AutoDiff and if a user supplied routine for the Hessian, stored in Prob.USER.H is available.

Solver.Alg=1 gives quasi-Newton BFGS and Solver.Alg=2 gives DFP

The table gives the different possibilities

 Solver.Alg  NumDiff  AutoDiff isempty(USER.H)  Hessian computation
     0          0         0           0         Analytic Hessian
     0          0         0           1         Numerical differences H
     0         >0         0         any         Numerical differences g,H
     0         <0         0         any         Numerical differences H
     0        any         1         any         Automatic differentiation
     1          0         0         any         BFGS
     2          0         0         any         DFP
     1        ~=0         0         any         BFGS, numerical gradient g
     2        ~=0         0         any         DFP,  numerical gradient g
     1        any         1         any         BFGS, automatic diff gradient
     2        any         1         any         DFP,  automatic diff gradient

Problem

	min      f(x) = sum (i=1:M) f_i (x), i.e. f is partially separable

       s/t       x_L <=   x  <= x_U
                 b_L <= A x  <= b_U
                 c_L <= c(x) <= c_U.

Input Parameters

Use conAssign.m (or probAssign) to initialize the Prob structure in the TOMLAB Quick format.

Fields used in structure Prob:

PartSep field for partially separable function (psf) information:

   PartSep.pSepFunc Number of elements M in the psf
   PartSep.index    Index for the function to compute

   x_0      Starting point
   x_L      Lower bounds for x
   x_U      Upper bounds for x
   b_L:     Lower bounds for linear constraints
   b_U:     Upper bounds for linear constraints
   A:       Linear constraint matrix
   c_L:     Lower bounds for nonlinear constraints
   c_U:     Upper bounds for nonlinear constraints
   ConsDiff Differentiation method for the constraint Jacobian
            0 = analytic, 1-5 different numerical methods
   SolverQP Name of the solver used for QP subproblems. If empty,
            the default solver is used. See GetSolver.m and tomSolve.m

   optParam Optimization parameters
   optParam.QN_InitMatrix  Initial Quasi-Newton matrix, if not empty,

 optParam structure in Prob. Fields used:
    IterPrint     Print short information each iteration
    eps_f         Relative tolerance in f(x)
    eps_g         Gradient convergence tolerance
    eps_x         Convergence tolerance in x
    eps_absf      Lower bound on function value
    size_x        Approximate size of optimal variable values 
    size_f        Approximate size of optimal function value 
    MaxIter       Maximal number of iterations
    wait          Pause after printout if true
    cTol          Constraint violation convergence tolerance
    bTol          Linear constraint violation convergence tolerance
    xTol          Variable violation tolerance
    PriLev        Print level
    IterPrint     Print short information each iteration
    QN_InitMatrix Initial Quasi-Newton matrix, if not empty,
                  Otherwise use identity matrix

The Prob structure could be created in the TOMLAB Quick format with calls to probAssign and mFiles, or in the Init File format, see Users Guide.

Extra Parameters

    VARARGIN: Extra user parameters passed to the computation of f(x) etc

Output Parameters

 Result      Structure with results from optimization
    x_k      Optimal point
    v_k      Lagrange multipliers 
    f_k      Function value at optimum
    g_k      Gradient vector at optimum
    x_0      Starting value vector
    B_k      The Quasi Newton matrix if Result.Solver.Alg > 0
    H_k      The Hessian matrix if Result.Solver.Alg == 0
    xState   Variable: Free==0; On lower == 1; On upper == 2; Fixed == 3;
    Iter     Number of iterations
    ExitFlag Flag giving exit status
    ExitTest Text string giving ExitFlag and Inform information
    Inform   Code telling type of convergence
             1   Iteration points are close.
             2   Projected gradient small.
             3   Iteration points are close and projected gradient small.
             4   Relative function value reduction low for LowIts iterations.
             5   Iteration points are close and relative function value
                 reduction low for LowIts iterations.
             6   Projected gradient small and relative function value
                 reduction low for LowIts iterations.
             7   Iteration points are close, projected gradient small and
                 relative function value reduction low for LowIts iterations.
             8   Too small trust region
           101   Max no of iterations reached.
           102   Function value below given estimate.
           103   Too large trust region, failure

 Printing (PriLev = Prob.PriLevOpt):

 PriLev: < 0: Totally silent,          0: Error messages, 
         1: Final result,              2: Each iteration, short output
         3: Each iteration, more info. 4: Info from QP solver. 5: Hessian

slsSolve

Tfmin