约束最优化方法

约束最优化问题的求解要比无约束问题的求解复杂得多, 也困难得多, 因而求解方法也更多种多样, 内容更为丰富. 这里只讨论可行方向方法中的简约梯度法和增广目标函数方法中的惩罚函数法. 一: 约束优化问题的最优性条件 KKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的. 这组最优化条件在Kuhn和Tucker 发表之后才逐渐受到重视, 因此许多书只记载成「Kuhn-Tucker 最优化条件(Kuhn-Tucker conditions)」. KKT条件处理不等式约束时, 可以把它变换成一组等式约束. KTT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式如式(1), 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点\({{\bf{x}}^ * }\)必须满足下面的条件: 1). 约束条件满足\({g_i}({{\bf{x}}^ * }) \le 0,i = 1,2,…,p\), 以及\(,{h_j}({{\bf{x}}^ * }) = 0,j = … 继续阅读

拟牛顿法

牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息, 而计算Hesse矩阵工作量大, 并且有的目标函数的Hesse矩阵很难计算, 甚至不好求出来, 这就导致仅用目标函数的一阶导数的方法, 拟牛顿法就是利用目标函数值和一阶导数信息, 构造出目标函数的曲率近似, 而不需要明显形成Hesse矩阵, 同时具有收敛速度快的优点. 一: 拟牛顿法条件 目标函数\(f\)在\({x_{k + 1}}\)附近的二次近似为: \[f(x) \approx f({x_{k + 1}}) + g_{k + 1}^T(x - {x_{k + 1}}) + \frac{1}{2}{(x - {x_{k + 1}})^T}{G_{k + 1}}(x - {x_{k + 1}})\] 对上面的式子两边求导, … 继续阅读

共轭梯度法

一: 共轭方向法 共轭方向法是介于最速下降法与牛顿法之间的一个方法, 它仅需利用一阶导数信息, 但克服了最速下降法收敛慢的缺点, 又避免了存储和计算牛顿法所需要的二阶导数信息. 共轭方向法是从研究二次函数的极小化产生的, 但是它可以推广到处理非二次函数的极小化问题. 最典型的共轭方向法是共轭梯度法. 而拟牛顿法也是共轭方向法的一种. 共轭方向的概念是这么定义的: 设\(G\)是\(n \times n\)对称矩阵, \({d_1},{d_2}\)是\(n\)维非零向量, 如果\(d_1^TG{d_2} = 0\), 则称向量\({d_1},{d_2}\)是\(G – \)共轭的. 类似地, 设\({d_1},{d_2},…,{d_m}\)是\({R^n}\)中的任意一组非零向量. 若有\(d_i^TG{d_j} = 0,(i \ne j)\), 则称\({d_1},{d_2},…,{d_m}\)是\(G – \)共轭的. 显然地, 当\(G\)是\(n\)阶单位矩阵时, \(d_i^T{d_j} = 0,(i \ne j)\), 即是正交向量组. 因而共轭概念是正交概念的推广. … 继续阅读

牛顿法

一: 最速下降法 下降法的迭代格式为\({x_{k + 1}} = {x_k} – {\alpha _k}{d_k}\), 其中\({d_k}\)为下降方向, 设\({g_k} = \nabla f({x_k}) \ne 0\), 则下降方向要满足\(d_k^T{g_k} < 0\). 当步长确定时, \(d_k^T{g_k}\)的值越小, 即\({\rm{ - }}d_k^T{g_k}\)的值越大, 函数下降得越快. 由Cauchy-Schwartz不等式\(\left| {d_k^T{g_k}} \right| \le \left\| {{d_k}} \right\|\left\| {{g_k}} \right\|\), 当且仅当\({d_k} = - {g_k}\)时, \(d_k^T{g_k}\)的值最小. … 继续阅读

一维搜索linesearch

一: 精确搜索-区间分割方法 1). 0.618法 对于一个单谷函数想通过迭代不断缩小该区间的长度, 当区间长度充分小时, 可取这个小区间中的一点作为\(\varphi (t)\)的一个近似极小点. 每次迭代时在搜索区间中任取两个点, 然后比较这两个点的函数值定下新的搜索区间. 当我们想在第二迭代开始时每次只搜索一个点, 即要把上一次迭代被抛弃的点利用上, 并且限制住收缩比相同. 则可以推出0.618法. 2). Fibonacci法 问题的提出: 在0.618法中, 经过N-1次迭代后的搜索区间\(\left[ {{a_N},{b_N}} \right]\)的长度为\({b_N}{\rm{ – }}{a_N} = {\tau ^{N – 1}}({b_1} – {a_1})\), 那么, 如果事先给定了搜索算法的迭代次数N, 按那种规则选取试探点可以使给定的搜索区间长度做最快分割呢? 上面的问题可以转化为一个优化问题: \[\begin{array}{*{20}{c}} {\min }&{{\tau _1}{\tau _2} \cdots … 继续阅读

最优化方法结构

一:无约束问题的最优性条件 对于一个无约束问题\(\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{*}}}) … 继续阅读