数据科学与工程数学基础 课件 第4-6章 凸优化基础-图论基础

第4章

凸优化基础4.2凸集与凸函数4.3凸优化问题4.4最优性条件§4.2凸集与凸函数定义1设集合若对于任意两点及实数都有：则称集合为凸集．

凸集定义例：证明超球为凸集．证明：设为超球中的任意两点，则有：即点属于超球,所以超球为凸集．

凸集定义的几何解释凸集性质

注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．例：表示轴上的点．表示轴上的点．则表示两个轴的所有点，它不是凸集；而凸集．凸包

凸函数设是非空凸集，若对任意的及任意的都有：则称函数为上的凸函数．注：将上述定义中的不等式反向，可以得到凹函数的定义．严格凸函数设是非空凸集，若对任意的及任意的都有：则称函数为上的严格凸函数．注：将上述定义中的不等式反向，可以得到严格凹函数的定义．

对一元函数在几何上表示连接的线段．所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方．表示在点处的函数值．

几何性质

任意两点的函数值的连线上的点都在曲线的上方

判断函数是凸函数的一阶条件

注：该定理提供了一个判别可微函数是否为凸函数的依据。一个可微函数

是凸函数当且

仅当函数图形

上任一点处的

切平面位于曲

面的下方.定理-----几何解释凸函数的判别定理---二阶条件

总结凸集与凸函数概念与性质凸函数判别方法

第5章

优化算法5.2梯度类下降算法5.3牛顿法与拟牛顿法5.4坐标下降法5.5交替方向乘子法5.6对偶优化算法5.7最小二乘法§5.2梯度类下降算法

最速下降法是以负梯度方向作为下降方向的极小化算法,又称梯度法,是1874年法国科学家Cauchy(柯西)提出的.

最速下降法是无约束最优化中最简单的方法

函数值增加最快的方向如何选择下降最快的方向？函数值下降的方向函数值下降最快的方向gk-gk

事实上,最速下降方向也可以这样来考虑.

因为目标函数f沿方向d的变化率是g

(xk)Td,故最速下降的单位方向d是问题

(5.2.4)(5.2.5)

的解

这时

(5.2.6)

其中,

是gk与d之间的夹角

当

时取极值这时

(4.1.7)最速下降法的迭代格式为

(4.1.8)

其中步长因子

由线性搜索策略确定.算法

(最速下降法)步1.给出步2.计算dk=-gk;如果

,停止.步3.由线性搜索求步长因子

.步4.计算步5.k:=k+1,转步2.最速下降法优缺点

优点：程序设计简单，计算工作量小，存储量小，对初始点无要求

缺点：最速下降方向仅是局部性质，对整体而言，下降速度慢，锯齿现象锯齿现象

数值试验表明,当目标函数的等值线接近于一个圆(球)时,最速下降法下降较快;

而当目标函数的等值线是一个扁长的椭球时,最速下降法开始几步下降较快,后来就出现锯齿现象,下降十分缓慢

事实上,由于精确线性搜索满足

则

这表明最速下降法中相邻两次的搜索方向是相互直交的,这就产生了锯齿形状.越接近极小点,步长越小,前进越慢.最速下降法的锯齿现象

§5.3牛顿法与拟牛顿法

牛顿法的基本思想是利用目标函数f(x)在迭代点xk处的二次Taylor展开作为模型函数,并用这个二次模型函数的极小点序列去逼近目标函数的极小点.

设f(x)二次连续可微，Hesse矩阵

正定

我们在xk附近用二次Taylor展开近似

f,

其中,

为f(x)的二次近似牛顿法

将上式右边极小化,即令

得:(5.3.1)

这就是牛顿法迭代公式.相应的算法称为牛顿法

令

,则(5.3.1)也可写成

对于正定二次函数,牛顿法一步即可达到最优解

迭代几何意义如下图所示：算法步骤步骤1.给定初始点

，精度步骤2.

计算

和当

可逆时，

。步骤3.

由方程组

解出步骤4.若

，停止，

；

否则，令

，转步骤2。

Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：

1.尽管每次迭代不会使目标函数f

(x)上升，但仍不能保证f

(x)下降．当Hesse矩阵非正定时，Newton法的搜索将会失败．

2.对初始点要求严格．一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的．

Newton法有关说明

3.在进行某次迭代时可能求不出搜索方向．

4.牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大．

对于一般非二次函数,牛顿法并不能保证经过有限次迭代求得最优解,但如果初始点x0充分靠近极小点,牛顿法的收敛速度一般是快的.

下面的定理证明了牛顿法的局部收敛性和二阶收敛速度.牛顿法收敛定理

定理

设f(x)二阶连续可微,x*是f(x)的局部极小点,

正定.

假定f(x)的Hesse矩阵

满足Lipschitz条件,即存在

,使得对于所有

有

其中Gij(x)是Hesse矩阵Gk的(i,j)元素.

则当初始点x0充分靠近x*时,对于一切k,迭代序列{xk}

收敛到x*,并且具有二阶收敛速度.拟牛顿法

牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息,但计算Hesse矩阵工作量大,并且有的目标函数的Hesse矩阵很难计算,甚至不好求出.能否仅利用目标函数值和一阶导数的信息,构造出目标函数的曲率近似,使方法具有类似牛顿法的收敛速度快的优点.拟牛顿法就是这样的一类算法.由于它不需要二阶导数,拟牛顿法往往比牛顿法更有效.

拟牛顿条件

从而新的迭代点为

(5.3.2)

其中,

是线性搜索步长因子.

(5.3.2)称为拟牛顿迭代.

与牛顿迭代的主要区别

设

在开集

上二次连续可微,

f

(x)在xk+1附近的二次近似为

对上式两边求导,有

令x=xk,得

令(5.3.3)

如果令,则拟牛顿条件为

(5.3.6)

拟牛顿迭代为

或

拟牛顿条件的插值性质

拟牛顿算法步骤

算法

步1.给出初始点

步2.如果

,停止.

步3.解

得搜索方向dk;(或计算

).

步4.由线性搜索求步长因子αk,并令xk+1=xk+αkdk.

步5.校正Bk产生Bk+1(或校正Hk产生Hk+1),使得拟牛顿条件(5.3.5)(或(5.3.6))成立

步6.k:=k+1,转步2.初始Hesse的选取

拟牛顿法中,初始Hesse近似B0通常取为单位矩阵,即B0=I

这样,拟牛顿法的第一次迭代等价于一个最速下降迭代拟牛顿法的优点

(1)仅需一阶导数.

(牛顿法需二阶导数).(2)Bk(或Hk)保持正定,使得方法具有下降性质.(在牛顿法中,

Gk可能不正定).(3)每次迭代需

次乘法运算.(牛顿法需

次乘法运算).(4)具有超线性收敛性.总结最速下降法牛顿法与拟牛顿法01图的基本概念第六章

图论基础

CONTENTS02图论问题03图论应用6.2

图的基本概念

例

下图是一张无向图G，请写出对应的点集V，边集合E，并求各顶点的度？

属性图

在实际使用中，往往会给图上的点和边赋予一些额外信息，这些信息称为属性或者权。这些属性可以是名称，数值，类别，排序等等。对于这类图，可以统称为属性图。

图的分类1.简单图

在无向图中，两个端点相同的边称为环。两条边有相同的端点，称为重边。定义

没有环与重边的无向图称为简单图。只有一个顶点的无向图称为平凡图。任意不同的两个顶点间都有边的简单图称为完全图。边数为零的图称为零图。例

下图中的这张图是简单图吗？是平凡图吗？是完全图吗？是零图吗？这张图是简单图，不是平凡图，是完全图，不是零图。

6.3

图论问题

七桥问题描述：普雷格尔河从哥尼斯堡穿过，河中有两座小岛，小岛上有7座桥，如下图所示。能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次，最后回到原地？

欧拉（Euler）对这个问题进行了数学建模并给出了否定的回答。将河岸和小岛看成点，桥看成边，七桥问题可以抽象成一张无向图，如下图所示。

在七桥问题的讨论中，给出了对欧拉图遍历边的方法，下面介绍两种对于所有图通用的遍历方法，深度优