| Home / lib / M_Mathematics / MOc_Optimization and control / | ||
Coleman T. Large Sparse Numerical Optimization(LNCS165, Springer, 1984)(T)(111s)_MOc_.djvu |
|
Size 0.8Mb Date Dec 2, 2005 |
matrix B+ by imposing a sparse Broyden update on U to obtain U+...
An inexact approach is also pos-
possible (see Section 4.2.1.1) using one of the indirect linear solvers, discussed in Sec-
Section 1.3, on the normal equations...
It is important to note
that only this last step need be repeated if X is changed ( MINPACK-1 saves a
copy of the matrix R)...
Instead, the relationship p(X) -+ pu as
X -> 0 is used to determine a solution p, which is 'close' to pu...
However, «я is not always a suitable correc-
correction since it is possible that f(x+sN) > f(x)...
An algorithm for minimization using exact second deriva-
derivatives, Atomic Energy Research Establishment, Report T.P...
Direct Determination (Powell & Toint [1979], Coleman & More [1982])
The problem of estimating a sparse Hessian matrix can be phrased as follows:
Given the sparsity structure of a symmetric matrix A, obtain vectors dhd2,...,dp
such that AdhAd2, ...
A coloring ф of GS(A) does not necessarily induce a symmetrically consistent
partition of the columns of a symmetric matrix A; it is necessary to restrict the
class of colorings...
, Cp is a consistent partition of the columns of L
then A can be determined indirectly with p evaluations of Ad...
To further explore the properties of triangular substitution methods, we
characterize a coloring of Gu(Lr) as a restricted coloring of GS(A) in the following
sense...
That is, B+ solves
,B symmetric, Es = у, Б « S(y2/)} E.2.12)
But this optimization problem has exactly the same form as E.2.11) and there-
therefore a solution can be achieved by the procedure described in the previous section
(due to Toint[l977])...
But
note that if и and t are indices such that @,...,a,,0,...,«,,0,...,0) and
@,...,z,,0,...,z,,0,...,0) are linearly independent then a* 5^0 and
E.2.15)
A-J > 0
It only remains to show that for any vector z which is not a multiple of я
there exists an index pair (u,t) e T with и < t such that (я„,я() and (zu,zt) are
linearly independent...
Similarity, let z,-,s,- and y; represent the
reduced versions, with respect to /,-, of x,s,&ady...
(Of course, if Д-z = 0 for z
in ЛГ,- then Д+г =0.)
The BFGS procedure does not suffer from potential singularity problems, as
is the case with the DFP update, since low rank approximations to Ht in the ini-
initial stages are not required...
If ak is deter-
determined exactly, then it is easy to see that pk is a descent direction:
9kTPk = 9kTl-9k + Л-iPt-J = ЧЫ12 < 0
Unfortunately, it is usually not feasible to determine the exact minimizer of
f(xk+ apk)...
Global Convergence and Direct Equation Solvers
Most of the sparse Hessian approximation techniques discussed in this section
allow for an indefinite approximation B...
Convergence Results For Trust Region Methods
Trust region methods are appealing for large sparse problems because they
handle indefinite matrices in a geometrically meaningful way...
S and further assuming
that v/ is uniformly continuous, then
While the above results are very positive and suggest probable convergence of
{xk} in practise, they do not ensure it...
A trust region algorithm will exhibit superlinear convergence if {xk} converges
to a point satisfying second-order sufficiency conditions and there exists Д > 0
such that if \\sk\\ < 03Ak then
where ek converges to zero...
Storage is needed for the sparse
factor L, the small dense factor Г, and the sparse matrix A...
| © 2007 eKnigu | ||