92.DESCENT METHODS
F
00
(x) is positive definite, then we get quadratic convergence (defined in
(2.3)). On the other hand, if x is in a region where F
00
(x) is negative definite
everywhere, and where there is a stationary point, the basic Newton method
(2.9) would converge (quadratically) towards this stationary point, which
is a maximizer. We can avoid this by requiring that all steps taken are in
descent directions.
We can build a hybrid method, based on Newton’s method and the steepest
descent method. According to (2.10) the Newton step is guaranteed to be
downhill if F
00
(x) is positive definite, so a sketch of the central section of
this hybrid algorithm could be
if F
00
(x) is positive definite
h := h
n
else
h := h
sd
x := x + αh
(2.11)
Here, h
sd
is the steepest descent direction and α is found by line search; see
Section 2.3. A good tool for checking a matrix for positive definiteness is
Cholesky’s method (see Appendix A) which, when successful, is also used
for solving the linear system in question. Thus, the check for definiteness is
almost for free.
In Section 2.4 we introduce some methods, where the computation of the
search direction h
d
and step length α is done simultaneously, and give a
version of (2.11) without line search. Such hybrid methods can be very
efficient, but they are hardly ever used. The reason is that they need an im-
plementation of F
00
(x), and for complicated application problems this is not
available. Instead we can use a so-called Quasi-Newton method, based on
series of matrices which gradually approach H
∗
= F
00
(x
∗
). In Section 3.4
we present such a method. Also see Chapter 5 in Frandsen et al (2004).
2.3. Line Search
Given a point x and a descent direction h. The next iteration step is a move
from x in direction h. To find out, how far to move, we study the variation
of the given function along the half line from x in the direction h,
2.3. Line Search 10
ϕ(α)=F(x+αh), xand h fixed,α≥0. (2.12)
An example of the behaviour of ϕ(α) is shown in Figure 2.1.
α
y
y = φ(0)
y = φ(α)
Figure 2.1. Variation of the cost
function along the search line.
Our h being a descent direction ensures that
ϕ
0
(0) = h
>
F
0
(x) < 0 ,
indicating that if α is sufficiently small, we satisfy the descending condition
(2.1), which is equivalent to
ϕ(α) <ϕ(0) .
Often, we are given an initial guess on α,egα=1 with Newton’s method.
Figure 2.1 illustrates that three different situations can arise
1
◦
α is so small that the gain in value of the objective function is very
small. α should be increased.
2
◦
α is too large: ϕ(α) ≥ϕ(0). Decrease α in order to satisfy the descent
condition (2.1).
3
◦
α is close to the minimizer
1)
of ϕ(α). Accept this α-value.
1)
More precisely: the smallest local minimizer of ϕ. If we increase α beyond the interval
shown in Figure 2.1, it may well happen that we get close to another local minimum
for F .
剩余29页未读，继续阅读
likai1610
- 粉丝: 1
- 资源: 1
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
