Documentation Trust Region Subroutine Algorithm

Documentation for
Trust Region Subroutine Algorithm

Charles Fortin and Henry Wolkowicz
Dept. Comb. & Opt., Univ. of Waterloo

This file contains the documentation for the trust region subproblem algorithm.

This file is available with URL:
Variable Definitions, Tolerances, Initialization,

Call: [xopt,fopt,lopt,lambdamin,muup,mulow,iter,flag] = newtrust(a,s,dgaptol)

solves: min q(x) = x'Ax - 2a'x such that s^2-x'x >=0 (Lagr. mult. lopt <=0) which is the trust region subproblem. This can be used within a trust region algorithm for min f(x). It is specifically designed for large sparse problems. The algorithm is based on the one developed in the paper A Semidefinite Framework for Trust Region Subproblems with Applications to Large Scale Minimization (Franz Rendl and Henry Wolkowicz, Math. Progr. 1997., Math. Review
files needed: Afun.m,Dfun.m,conj_grad.m, and this file newtrust.m BEFORE USING NEWTRUST, THE FOLLOWING INSTRUCTION MUST BE ENTERED >> global A D counter


Back to top of Documentation file
TOLERANCES Back to top of documentation file Tolerances - these can and should be changed by the user. The tolerance for the duality gap is for significant figures, i.e. it is a relative duality gap. The significant figures of agreement are computed for the duality gap as follows: signif = max( -log_10 |primal-dual|/(|primal|+1) , 0 ) The tolerances for ***LANCZOS** should be significantly higher than those used here, e.g. 4 here and 7 for Lanczos Stopping criteria: (i) feasibility, ||x|| > (1+normtol)s (ii) feasibility dbestgap= (bestfxf-mulow)/(|bestfxf|+1) > 2*dgaptol bestfxf is the current best opt. value corresponding to the current best feasible point bestxf, while muup is the current best upper bound of the optimal value. (iii) duality gap, |gap(2)-gap(1)|/(|gap(2)|+1) > dgaptol (iv) iteration count, iter <= iterbnd (v) interval of uncertainty for t is > zerotol Loop while: ( ((i) and (ii)) or (iii)) and ((iv) and (v)) i.e. while ( (t1&t2) | t3) & (t4 & t5), So stop: ( (~t1|~t2) & ~t3) | (~t4 | ~t5) Inverse Interpolation Starts if side>0, last iterate was on the GOOD SIDE