Next: Starting and safeguarding Newton's
Up: The TrustRegion subproblem
Previous: Explanation of the Hard
Contents
We will apply the 1Doptimization algorithm called ``1D Newton's
search'' (see Annexes, Section 13.5) to the
secular equation:

(4.14) 
We use the secular equation instead of
inside the ``1D Newton's
search'' because this last function is better behaved than
. In particular
is strictly
increasing when
, and concave. It's first
derivative is:

(4.15) 
where

(4.16) 
The
proof of these properties will be skipped.
In order to apply the ``1D Newton's search'':

(4.17) 
we need to evaluate the function
and
. The value of
can be obtained by
solving the Equation 4.9 to obtain
. The
value of
is available from 4.17 once
has been found using 4.18.
Thus both values may be found by solving linear systems involving
. Fortunately, in the range of interest,
is definite positive, and thus, we may use its Cholesky factors
(see Annexes, Section
13.7 for notes about Cholesky decomposition ). Notice that
we do not actually need tho find
, but
merely the numerator
of 4.17. The simple relationship

(4.18) 
explains
why we compute in step 3 of the following algorithm. Step
4 of the algorithm follows directly from 4.17 and
4.19. Newton's method to solve
:
 find a value of such that
and
.
 factorize
 solve
 Solve

Replace by 
(4.19) 
 If stopping criteria are not met, go to step 2.
Once the algorithm has reached point 2. It will always generate
values of
. Therefore, the Cholesky
decomposition will never fails and the algorithm will finally find
. We skip the proof of this property.
Next: Starting and safeguarding Newton's
Up: The TrustRegion subproblem
Previous: Explanation of the Hard
Contents
Frank Vanden Berghen
20040419