凸优化数学基础笔记（七）：一般非线性最优问题的迭代解法思路

凸优化数学基础笔记（七）：一般非线性最优问题的迭代解法思路

1.迭代方法

1. 在经典最优化极值问题中，解析法虽然具有概念简明，计算精确等优点，但因只能适用于简单或特殊问题的寻优，对于复杂的工程实际问题通常无能为力，一般采用迭代算法，逐渐逼近最优解。

复制代码

​        最优化问题的迭代算法是指：从某一选定的初始点（或初始解）出发，根据目标函数，约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，用式子表示即为：

\[\mathbf{X}_{k+1}=\mathbf{X}_{k}+t_k\mathbf{P}_k \hspace{2em}(k=0,1,2,\cdots) \tag{1}\]
其中：\(\mathbf{X}_k\) 表示前一次已经取得的迭代点，在开始计算的时候为迭代的初始点\(\mathbf{X}_0\) ；\(\mathbf{X}_{k+1}\) 表示的更新的迭代点；\(\mathbf{P}_k\) 表示第\(k\)次的迭代计算的搜索方向；\(t_k\) 表示第\(k\) 迭代计算的步长因子。
​        按照式（1）进行一系列迭代计算所根据的思想是所谓的“爬山法”（或“贪心算法”），就是将寻求的函数极小值点（无约束或约束极小值点）的过程比喻为向“山”的顶峰攀登过程，始终保持向“高”的方向前进，直至到达“山顶”。当然“山顶”可以理解为目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法，则序列迭代点的目标函数值必须满足下列关系：

\[f(\mathbf{X}_0)>f(\mathbf{X}_1)>f(\mathbf{X}_2)>\cdots>f(\mathbf{X}_k)>f(\mathbf{X}_{k+1}) \tag{2}\]
如果是求一个约束的极小值点，则每一次迭代的新点\(\mathbf{X}_1,\mathbf{X}_2,\cdots\)都应该在约束可行域内，即

\[\{\mathbf{X}_k\}\in{\mathbf{D}} \tag{3}\]
由上面的迭代过程可知，在迭代过程中有两个规则需要确定：（1）一个是搜索方向\(\mathbf{P}_k\) 的选取；（2）另一个是步长因子\(t_k\) 的选取。一旦\(\mathbf{P}_k\) 的选取方法和\(t_k\)的选取方法确定，则一个迭代算法就确定，由此得出：不同的规则就对应不同的最优化方法。
2.收敛速度与计算终止准则

2.1 收敛速度

​        作为一个迭代算法，能够收敛域于问题的最优解当然是必要的，但光能收敛还不够，还必须以较快的速度收敛，这才是好的算法。下面给出收敛速度的定义如下：
Defintion 7.1 设由迭代算法\(A\)产生的迭代点列\(\{\mathbf{X}_k\}\) 在某种范数\(||\cdot||\) 的定义下收敛于点\(\mathbf{X}^*\) ，即\(\lim_{k\rightarrow{0}}||\mathbf{X}_k-\mathbf{X}^*||=0\)，若存在实数\(\alpha>0\)，及一个与迭代次数\(k\)无关的常数 \(q>0\),  使得：

\[\lim_{k\rightarrow\infty}\frac{||\mathbf{X}_{k+1}-\mathbf{X}^*||}{||\mathbf{X}_k-\mathbf{X}^*||^{\alpha}}=q \tag{4}\]
则迭代优化算法\(\mathbf{A}\) 产生的迭代点列\(\{\mathbf{X}_k\}\) 叫做具有\(\alpha\)阶收敛速度或算法\(\mathbf{A}\) 叫做是\(\alpha\) 阶收敛的，特别地。
<ol>当\(\alpha=1,q>0\)，迭代点列\({\mathbf{X}_k}\) 具有线性收敛速度或算法\(\mathbf{A}\) 称为线性收敛的。
当\(1