2.7非线性优化直接方法在线视频

同学们好

本单元

主要讲授非线性优化直接方法

让我们回顾一下

无约束非线性优化问题求解思路

无约束非线性优化问题求解思路是

构造下降的迭代算法

应满足

逐步迭代增优

收敛.

即构造点列{xk}使

f(X0)>f(X1)>…>f(Xk)>…

XK收敛到X*

且f(XK)的极限=f(X*)=f(XK)的极小值

算法的核心是

当有了Xk

搜索Xk+1时

要确定搜索方向即在Xk附近为下降的方向dk

和搜索步长αk,即Xk+1=Xk+αkdk

使f(Xk)>f(Xk+1)

这里

dk 是向量α

k 是标量α

k可以取最优

即使得

f(XK+1)=f(xk+αkdk)=minf(XK++α.dk)

无约束非线性优化问题求解方法

可以分为解析法和直接方法

解析法就是求解过程中利用了

目标函数的导数（梯度）信息

解析法有梯度法

牛顿法

共轭方向法等

直接方法就是

在求解过程中仅用目标函数值信息

不利用或无法利用目标函数的

导数信息

直接方法主要有坐标轮换法

Powell法

单纯形算法

复合形法

群体复合形法等方法

其中群体复合形法是

全局优化方法

目前快速发展的

群体智能算法也可以

看作是直接方法

不少实际问题的

目标函数表达式非常复杂

或没有明显的解析表达式

其导数不可求或者非常难以计算

例如

水库发电优化调度问题

目标函数中

每个时段的平均入库流量

平均发电流量

时段初末库蓄水量之间

必须满足水量平衡方程

这样

若选择发电流量为决策变量

则每个时段的库蓄水量及

发电水头都与该时段的

平均发电流量

该时段之前所有时段的

平均发电流量有关

年发电量目标函数对

某个时段的平均发电流量的

导数非常复杂

水库发电优化调度问题

常采用动态规划方法

求解过程中不需要利用导数信息

可以看成是直接优化方法

水库发电优化调度问题

也可以采用群体智能算法求解

群体智能算法也是直接算法

下面讨论坐标轮换法

坐标轮换法又称为交替方向法

其基本思路是

沿n个坐标轴方向

轮流搜索最优点

搜索方向依次取n个坐标方法

交替方向法程序简单

而且在收敛时必收敛到稳定点

但交替方向法可能不收敛

交替方向法的思想在

水库群优化调度方向有一定的应用 例如

传统的求解中长期发电优化调度的

方法是动态规划法

水库群发电优化调度要比

单库优化调度复杂的多

当参与优化的水库数目增加时

动态规划求解的状态变量

将成几何级数增加

出现所谓的“维数灾”现象

因此

人们时常采用轮库法求解

对参与优化调度的水库

依次轮库循环求解

当采用单库动态规划方法

优化求解某水库的发电流量决策时

其余水库的发电流量采用

前次循环所求得的发电流量解

连续作若干个循环

每次循环都是对前次解的

改进即增优

若轮库循环达到可以接受的

最高次数或当前解达到给定的精度

则输出当前解作为最优解

下面讨论Powell法

Powell法又称为共轭方向法

其基本思路是

沿n个坐标轴方向

轮流搜索最优点

搜索完一轮后

利用搜索到的点构造1个

向量加入到搜索方向组中

同时删去排在第1的坐标方向

保持n个搜索方向个数不变.

Powell方法的一个弱点是

随着迭代次数的增加

方向 很容易线性相关

为此

Powell后来提出了一个修正方案

具体参见有关文献.

下面讨论单纯形法.

求解无约束优化问题的

单纯形法的思路是

给定n维实空间Rn中的

一个凸多面体

又称为单纯形

求出其n+1个顶点上的函数值

并确定其最坏值

次坏值

最好值

然后通过反射

扩张

收缩

缩边等运算求得一个较好的点取代最坏点

构成新的单纯形

通过迭代

逐步逼近最优点. 单纯形法又称为可变多面体搜索法.

算法的第1步

初始化. 给定有关参数

生成初始单纯形

（2.7-2）给出了生成

正规单纯形（多面体的每条边相等）

的方法是

给定一个初始点

再给定正规单纯形边长为t

正规单纯形n+1个点的

坐标为（2.7-2）.

算法的第2步

求出单纯型的最好点

最坏点

次坏点

形心和半径

算法的第3步

收敛性判断

若当前单纯形半径小于

事先给定的精度

则迭代收敛

否则

继续迭代.

算法的第3步

反射操作

根据不同的反射计算结果情况

确定一个较好点取代最坏点

分3种情形

情况1

若反射成功

即反射点比当前最好点好

应进行扩张

根据扩张是否成功确定

以扩张点或以反射点取代最坏的点得到新的单纯形转第2步继续迭代

情况2

若反射失败

且反射点比次坏点差

应进行收缩.若收缩成功

则以收缩点取代最坏点

否则进行缩边

向当前最小点靠近

得到新的单纯形转

第2步继续迭代.

情况3

若反射失败

但反射点比次坏点好

则以反射点代替最坏点

得到新的单纯形转第2步继续迭代

单纯形法在开始阶段搜索效率较高

但在迭代的后期接近

最优时收敛速度较慢

单纯形法具有简单实用的优点

大量的计算表明单纯形法是

一个十分可靠的方法

特别是它能处理函数值

变化剧烈的问题

单纯形法经改进后

也可以用于求解

约束非线性规划

特别是决策变量区间约束情形

在单纯形法中

对于n维极值问题

单纯形的顶点个数为p=n+1

实际上也可取p≥n+1

例如p=2n

在n为欧氏空间中

顶点个数p>n+1时的

多面体称之为复合形

相应地有复合形算法

下面给出求解

约束非线性规划问题的复合形算法

本次课到此结束

谢谢大家

再见