最优化方法结构

一:无约束问题的最优性条件

对于一个无约束问题\(\min f(x),x \in {R^n}\). 它的极小点类型有局部极小和总体极小两种. 而且一般来说, 总体求总体极小点是一个相当困难的任务, 很多实际问题中求局部极小点已满足了问题的要求. 当研究的问题是具有某种凸性时, 局部极小点就是全局极小点.

设\(f\)的一阶导数和二阶导数存在, 且分别表示为\(g(x) = \nabla f(x),G(x) = {\nabla ^2}f(x),\) 则
1. 收敛点的一阶必要条件: \(g({x^{\rm{*}}}) = 0\);
2. 收敛点的二阶必要条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}}) \ge 0\);
3. 收敛点的二阶充分条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}})\)是正定矩阵;
4. 如果目标函数为凸函数, 那么全局极小值点的充分必要条件就是\(g({x^{\rm{*}}}) = 0\).

二:最优化方法结构

最优化方法的基本步骤为:
给定初始点\({x_0}\),
a). 确定搜索方向\({d_k}\), 即依照一定规则, 构造\(f\)在\({x_k}\)点处的下降方向作为搜索方向;
b). 确定步长因子\({\alpha _k}\), 使目标函数值有某种意义的下降;
c). 令\({x_{k + 1}} = {x_k} + {\alpha _k}{d_k}\), 若\({x_{k + 1}}\)满足某种终止条件, 则停止迭代, 得到近似最优解\({x_{k + 1}}\). 否则, 重复以上步骤.

如果我们假设了算法产生的迭代点列\(\{ {x_k}\} \)是在某种范数下收敛的, 即\(\mathop {\lim }\limits_{k \to \infty } \left\| {{x_k} – {x^ * }} \right\| = 0\), 那么考察收敛速度的话, Q-收敛速度较为常用是这么定义的: 若存在实数\(\alpha > 0\)及一个与迭代次数\(k\)无关的常数\(q > 0\), 使得\(\mathop {\lim }\limits_{k \to \infty } \frac{{\left\| {{x_{k{\rm{ + }}1}} – {x^ * }} \right\|}}{{{{\left\| {{x_k} – {x^ * }} \right\|}^\alpha }}} = q\),
1). 线性收敛速度: \(\alpha = 1,q > 0\);
2). 超线性收敛速度: \(1 < \alpha < 2,q > 0\)或者\(\alpha = 1,q = 0\);
3). 二阶收敛速度: \(\alpha = 2\).
注: 还有其他的一些收敛速度的定义, 但并不常用.

终止迭代的收敛准则有多种多样, 这里记几种比较常用的.
1). \(\left\| {{x_{k + 1}} – {x_k}} \right\| \le {\varepsilon _1},\left| {f({x_k}) – f({x_{k + 1}})} \right| \le {\varepsilon _1}\), 注: 对于一些明确的问题可以单独只拿其中一项作为终止条件;
2). 如果\({x_k},f({x_k})\)都比较大, 可考虑采用\(\frac{{\left\| {{x_{k + 1}} – {x_k}} \right\|}}{{\left\| {{x_k}} \right\|}} \le {\varepsilon _2},\frac{{\left| {f({x_k}) – f({x_{k + 1}})} \right|}}{{\left| {f({x_k})} \right|}} \le {\varepsilon _2}\)作为终止条件;
3). 对于有一阶导数信息, 且收敛不太快的算法, 如共轭梯度算法, 可采用如下终止准则: \(\left\| {{g_k}} \right\| \le {\varepsilon _3}\).

[参考] 1. <最优化理论与方法>袁亚湘院士著.

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>