2.7 优化设计方法的基本思想与迭代终止准则在线视频

本节课我们来讲解

优化设计方法的基本思想

与迭代终止准则

我们之前的两节或者三节呢

我们都讲什么问题呢

如果说你这个函数和你的实际问题

变成了数学模型以后呢

你能够去写出一个可导的一个f（x）

或者具有约束问题

那么你可以用什么

函数的极值条件来判断我们来进行求解

我们称为这个是解析解

但是呢如果这个函数非常复杂

或者说这个函数

可能就不是连续的不是可导的话

那你怎么去判断

因为我们之前讲的我们对这里面的

我们说优化问题的一个更通用的方法

我们是以数学规划论为基础

借助于电子计算机来进行求解的因此我们说

经常我们求优化问题的求解方法是什么

数值方法求解我们就是说的

数值的一个叫数值的迭代方法去求解

通过计算机计算机的高速计算性能

我们用数值方法去求解

你之前你所学的你求一阶求Hessian矩阵

都是什么解析的方法

你对于这个函数你要记住公式

你要记住这个求导公式代进去求解

我们这更加通用的是用数值方法求解

优化问题的一个基本思想优化问题的基本思想

方法数值迭代法基本思想搜索 迭代 逼近

这是我们的一个基本思想

我们通过三步搜索 迭代 逼近

这样三步的来进行求解我们称为是步步下降

步步紧逼最终逼近x*数值迭代

我们一步一步做每一步都使你的函数值下降

因为我们求什么

求的是极小值点每一步都是函数值下降

步步下降步步逼近函数的极值点

最终呢是达到或者逼近x*达到或者逼近x*

这是我们的x0起始点起始点x0

我们从这个点x0然后呢去搜索然后迭代

一步一步的去寻找逼近这个点

走一步怎么走

实际上找一个合适的方向s0

然后找到一个合适的步长

走到一定找一个新的x1

这是我们合适的步长αs然后呢找到x1

在x1处呢我再选择一个合适的方向

选择一个合适的步长α1s

再选择一个方向s3选择一个合适的步长α3

一步一步的去这样找直到最后逼近我的最优解

直到逼近我的最优解

一步一步的选择一个合适的方向

选择一个合适的步长找到一个新的点

这个新的点你看这个图看出来

这个新的点的函数值一定比上一个点要下降了

所以说步步下降然后呢在寻找一个合适的方向

合适的步长找一个新的点

一步一步一步步步逼近最终找到我们这个x*

那么基本的迭代公式是什么呢

xk加1下一次的xk x点等于xk加上αk sk

k是等于0 1 2 3 4 5等等往后去走

这是我们的基本迭代公式

这个公式我们后面会经常用到这个公式

上一个点合适的方向合适的步长

构成了下一个点

保证我下一点的函数值f（xk+1）

一定是小于f（xk）步步逼近

否则的话你们越做越大了

因为我们要求的极小值越做越大南辕北辙了

使f（xk+1）小于f（xk）

式中xk是第k步的迭代的初始点或者出发点

xk+1是第k步迭代产生的新点或者是终止点

也是k+1步迭代的初始点

上一步的初始点这一步的终止点

或者是下一步的初始点

s第k步的搜索方向它一定是个矢量

合适的一个方向s是合适的方向

αk第k步我说需要沿着这个方向走的步长

我要迈的步长

步长小了我可能这个方向利用的不充分

你看比如我们就这个例子肯定用这个例子

从这一点步长如果小了

我可以往前走沿这个方向往前走一走

会得到更好一个点因为什么

因为这个没有到达这个下一个等值线

如果步长大了是不是反而这个函数值就增大了

如果步长特别大从这点我一步迈到这了

我是不变大了

所以步长大步长小就需要你去选择的

找一个合适的步长然后呢找到这一点

步长选择的好方案选择的好

你的效率就高效率就高

那么迭代公式的几何意义呢

实际上就是什么

从第零点开始找到一个合适的方向到xk

然后呢xk这一点处找到一个合适的方向

xk这是我们的0点xk当前的这一步的初始解

找一个方向找一个步长到xk+1

因此说呢我们这里面优化设计方法的

研究的主要问题是什么呢就两个问题

如何选取搜索方向

两个问题最核心的问题就是选取搜索方向

如何选取搜索方向sk

不同的sk则构成了我们后续章节

所讲的不同的优化方法

实际上你的后面各种各样优化方法

本质上就是不同的选取sk的方法

那么当你选定一个合适的sk以后

下一个问题就是你选取什么样的步长

所以是两个问题

两个问题最重要的问题是

不同的选取方向选取方向sk

sk选取的方法就是不同优化方法

选取的好与坏直接决定了你的最优化搜索方法

或最优化求解方法的效率高于低效率高于低

由于数值迭代计算不可能也没有必要精确到x*

因此说呢我们需要一个终止条件

因为我们说这里是

步步下降步步紧逼最终达到x*或者逼近x*

但是呢我们这里数值迭代方法

可能你最终也达不到x*

因此说你也没有必要去求解最精确的x*

因此说呢我们就需要制定终止条件

循环多少多少步我可以终止了我可以终止了

终止条件第一点距准则

我帮你去做三个终止条件

大家如果平时来去建模或解模

做设计可以用这样三个条件

第一点距条件

如果说我下一次迭代那个求的新点

和我上一次这个点之间的

点的距离非常小了小于ε或者说呢我这里面呢

因为是sk吗这是我们的矢量所以说我们取模

我可以把它写出来变成标量的话

xk+1减去xk括号的平方再开方如果小于ε的话

我认为可以终止什么意思啊

我做了一步以后的我的新的点

和我上一点前进的距离不够大

我觉得非常小了基本上小的非常小了

那我认为可以收敛了可以终止可以收敛了

第二个值差准则值差准则什么意思啊

我的下一个点所得到的sk+1的f（x）函数值

我的下一个点所得到的新的函数值

和我上一点的函数值之间的差距

非常小非常小了

或者说什么啊

它俩相减再比上一个上一点的时候

也非常小了小于ε了那我就认为是可以终止

我认为是可以终止了

我迭代了一步以后我迭代这一步的函数值

下降的这个程度太小了非常小了小到什么

小到我的计算精度了或者终止的条件了

那我认为就可以停止了

就是我这个进步不算太大了

进步特别小了我认为可以终止了

第三梯度准则如果说▽f（xk）小于ε

如果说这个梯度的模比ε小了

我也可以认为是终止了这是三种的终止条件

那么这个ε怎么选取呢

ε就是靠你的实际的问题来决定ε

那么举个例子很简答比如说同样是做距离

那可能你要修公路或者修这个修公路或者桥梁

或者修大坝这样的一个大型工程的话

你的ε可能达到厘米级毫米级可能就可以了

对吧需要这样的就可以了

那如果说你就是做精密仪器

或者做这个测量这个纳米级

本身你的问题就很精确的

那你比如这样的问题的话

焊接或者什么样问题的话

那你可能到什么到微米级那才行

所以说看你的这个ε看你实际的问题了

不一样的问题所选取的ε是不一样的

一般情况下我们这里面只用选择

三种里面的一种准则就可以进行

判断你的优化问题的迭代过程的终止

可以迭代过程终止了

一般情况下一种方法就可以了

但是某一些时候可能你的函数性状极其特殊

函数性状极其特殊这时候呢你可能需要

点距准则和值差准则相互判断

才能够得到你的正确的判定是否收敛

举个例子比如说我这个函数性状

我这是我们说一维函数吧我能画出来f（x）

这是我的x

比如说我这函数是非常一个非常陡的一个函数

我最后性质是这样一个性状

那你可能你上一次的点xk是这个xk

我迭代了一步我迭代了一步我用点距准则

我迭代一步下一个点xk+1对吧这样两个点

然后你只用点距准则来判断的话

你认为xk+1减去xk移动了非常小的一步

你是不是就停止了

但实际上你的极值点在哪在这呢

早着呢还在这早的呢这是因为什么

因为你函数是不太陡了

如果这个时候你再结合值差准则的话

你发现我再算算f（x）

f（xk）和f（xk+1）的话

这是我的f（xk）和f（xk+1）

我算这个两个的话是不是差距还非常大

我还可以继续往下走

同样如果你这个函数值非常平缓的话呢

会存在也是这样的问题所以说呢某些特殊情况

你可以用这两个来结合着使用

一般情况下用一个就可以了

这是我们的终止条件

一般情况下三个准则单独使用

只要满足一个便可以终止

在某些情况下

点距准则和值差准则可以联合起来使用

那好了我们来看一下本章学习的要点

本章内容是学习后面各章内容的一个基础理论

希望大家能够充分的重视起来

因为我们这里学的一些概念

和一些定理后面会经常用到

第一我们说的方向是非常重要的

不同的方向决定了不同的优化问题

那么梯度方向是函数的最速上升方向

是以函数的一阶偏导数为分量的一个矢量

它的模是函数的最大变化率是函数的局部性态

梯度的方向是一个函数一个最重要的一个方向

它是函数一个最速上升的方向但是呢要注意

梯度是函数一个局部性态

不是全局的是局部性态

第二掌握函数的二次泰勒展开形式

海塞矩阵的求法以及正定负定的判定方法

第三掌握无约束优化极值的

必要条件和充分条件

对于简单的无约束优化问题

应会使用或应用该条件求解极值

第四了解函数的凸性

凸集凸函数的判定方法以及凸规划的特点

我们之前也讲了凸函数凸性凸集等等

对我们这里的极值问题

对我们的最值问题的用处

第五掌握判定约束条件优化问题的

局部极小值点的必要条件K T条件

应用时应注意第一数学模型中

不等式约束为小于0的这样的一个形式

我们说它是标准形式之前我们强调过

你的优化问题首先是个标准形式

第二λu是大于0的u是取1到q

q为起作用的约束个数

并不是所有的不等式约束并不是1到m是1到q

第六优化设计计算方法是采用数值迭代方法

基本思想是搜索 迭代 逼近

了解迭代计算的三个终止条件

点距准则 值差准则和梯度准则

那么这是我们第二章所讲的数学的基本概念