凸优化数学基础笔记七一般非线性最优问题的迭代解法思路1.迭代方法/* by 01022.hk - online tools website : 01022.hk/zh/json.html */ 在经典最优化极值问题中解析法虽然具有概念简明计算精确等优点但因只能适用于简单或特殊问题的寻优对于复杂的工程实际问题通常无能为力一般采用迭代算法逐渐逼近最优解。 最优化问题的迭代算法是指从某一选定的初始点或初始解出发根据目标函数约束函数在该点的某些信息确定本次迭代的一个搜索方向和适当的步长用式子表示即为\[\mathbf{X}_{k1}\mathbf{X}_{k}t_k\mathbf{P}_k \hspace{2em}(k0,1,2,\cdots) \tag{1} \]其中\(\mathbf{X}_k\)表示前一次已经取得的迭代点在开始计算的时候为迭代的初始点\(\mathbf{X}_0\)\(\mathbf{X}_{k1}\)表示的更新的迭代点\(\mathbf{P}_k\)表示第\(k\)次的迭代计算的搜索方向\(t_k\)表示第\(k\)迭代计算的步长因子。 按照式1进行一系列迭代计算所根据的思想是所谓的“爬山法”或“贪心算法”就是将寻求的函数极小值点无约束或约束极小值点的过程比喻为向“山”的顶峰攀登过程始终保持向“高”的方向前进直至到达“山顶”。当然“山顶”可以理解为目标函数的极大值也可以理解为极小值前者称为上升算法后者称为下降算法。这两种算法都有一个共同的特点就是每前进一步都应该使目标函数有所改善同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法则序列迭代点的目标函数值必须满足下列关系\[f(\mathbf{X}_0)f(\mathbf{X}_1)f(\mathbf{X}_2)\cdotsf(\mathbf{X}_k)f(\mathbf{X}_{k1}) \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\)若存在实数\(\alpha0\)及一个与迭代次数\(k\)无关的常数\(q0\), 使得\[\lim_{k\rightarrow\infty}\frac{||\mathbf{X}_{k1}-\mathbf{X}^*||}{||\mathbf{X}_k-\mathbf{X}^*||^{\alpha}}q \tag{4} \]则迭代优化算法\(\mathbf{A}\)产生的迭代点列\(\{\mathbf{X}_k\}\)叫做具有\(\alpha\)阶收敛速度或算法\(\mathbf{A}\)叫做是\(\alpha\)阶收敛的特别地。当\(\alpha1,q0\)迭代点列\({\mathbf{X}_k}\)具有线性收敛速度或算法\(\mathbf{A}\)称为线性收敛的。当\(1\alpha2,q0\)或\(\alpha1,q0\)时迭代点列\({\mathbf{X}_k}\)叫做具有超线性收敛速度或称算法\(\mathbf{A}\)是超线性收敛。当\(\alpha2,q\geq0\)时迭代点列\({\mathbf{X}_k}\)叫做具有二阶收敛速度或算法\(\mathbf{A}\)是二阶收敛的。一般认为具有超线性收敛速度和二阶收敛的算法是较快的算法。2.2 计算终止准则 用迭代算法寻优时其迭代过程总不能无限制的进行下去那么什么时候截断这种迭代呢这就是迭代什么时候终止的问题。从理论上说当然希望最终迭代最优解到达理论极小值点或者使最终迭代点与理论极小值点之间的“距离”足够小时候才终止迭代。但是这在实际上是办不到因为对于一个待求的最优化问题其理论极小值点在哪里并不知道。所知道的只是通过迭代计算获得的迭代点列\(\{\mathbf{X}_k\}\),因此只能从点列所提供的信息来判断是否应该终止迭代。 对于无约束优化问题通常采用的迭代终止准则有以下几种。点距准则相邻两个迭代点迭代优化解\(\mathbf{X}_k,\mathbf{X}_{k1}\)之间的距离已达到充分小即\[||\mathbf{X}_{k1}-\mathbf{X}_{k}||\leq {\varepsilon} \tag{5} \]其中\(\varepsilon\)表示距离收敛阈值目标函数损失函数下降量准则相邻两个迭代点的目标函数或损失函数值下降量已经充分小。当\(|f(\mathbf{X}_{k1})|1\)时可用目标函数绝对下降量准则\[|f(\mathbf{X}_{k1})-f(\mathbf{X}_k)|\leq \varepsilon \tag{6} \]当\(|f(\mathbf{X}_{k1})|1\),时可采用函数相对下降量准则\[|\frac{f(\mathbf{X}_{k1})-f(\mathbf{X}_k)}{f(\mathbf{X}_{k1})}|\leq{\varepsilon} \tag{7} \]梯度准则目标函数在迭代点的梯度已达到充分小即\[|\nabla{(f}(\mathbf{X}_{k1})|\leq{\varepsilon} \tag{8} \]这一准则对于定义域上的凸函数是完全正确的。若是非凸函数有可能导致误把驻点作为最优点。3.迭代优化算法一般步骤 通过上述的迭代优化算法的架构一般含有三个基本元素1确定最优解的搜索方向\(\mathbf{P}_k\)的计算方法2迭代步长\(t_k\)的确定方法3 迭代计算终止准则其算法的基本格式步骤1选定初始点\(\mathbf{X}_0\),设置迭代计算的终止误差限\(\varepsilon\);步骤 2按照某种规则确定搜索方向\(\mathbf{P}_k\);步骤3按照某种规则确定\(t_k\):\[f(\mathbf{X}_kt_k\mathbf{P}_k)f(\mathbf{X}_k) \tag{9} \]步骤 4跟新迭代最优解\(\mathbf{X}_{k1}\):\[\mathbf{X}_{k1}\mathbf{X}_kt_k\mathbf{P}_k \tag{10} \]步骤5判定\(\mathbf{X}_{k1}\)是否满足终止准则若满足则停止迭代则输出\(\mathbf{X}_{k1}\)和\(f(\mathbf{X}_{k1})\)否则置\(kk1\)转步骤2进行迭代。