机器学习系统与优化 课件 第一章 最优化理论

第一章最优化理论目录content01基本概述02基本知识03

线搜索方法04无约束优化问题05约束优化的罚函数法习题101PARTONE基本概述1.1.1最优化问题概括1.1.2实例：稀疏优化1.1.3实例：深度学习1.1.1最优化问题概述最优化问题的一般形式最优化问题一般可以描述为(1.1)min

f

(x),s.t.

x∈

X,x

=

(x1,

x2,

·

·

·

,

xn)T

∈

Rn是决策变量f

:

Rn

→

R是目标函数X

⊆

Rn是约束集合或可行域，可行域包含的点称为可行解或可行点。当X

=

Rn时，问题(1.1)称为无约束优化问题．集合X

通常可以由约束函数ci(x):

Rn

→

R,

i

=

1,

2,

·

·

·

,

m

+

l

表达为如下形式：X={x

∈

R|ci(x)≤

0,

ci(x)=

0,i

=

1,

2,

·

·

·

,

m,i

=

m

+

1,

m

+

2

·

·

·

,

m

+

l}.1.1.1最优化问题概述在所有满足约束条件的决策变量中，使目标函数取最小值的变量x∗

称为优化问题(1.1)的最优解，即对任意x

∈

X

都有f

(x)

≥

f

(x∗).如果求解在约束集合X

上目标函数f

(x)的最大值，则问题(1.1)的“min”应相应地替换为“max”．注意到在集合X

上，函数f

的最小（最大）值不一定存在，但是其下（上）确界“inf

f

(sup

f

)”

总是存在的。因此，当目标函数的最小(最大）值不存在时，便关心其下（上）确界，即将问题(1.1)中的“min(max)”改为“inf(sup)”．为了叙述简便，问题(1.1)中x为Rn空间中的向量。实际上，根据具体应用和需求，x还可以是矩阵、多维数组或张量等。1.1.1最优化问题概述最优化问题的类型与应用最优化问题可以按照目标函数、约束函数以及解的性质将其分类。当目标函数和约束函数均为线性函数时，问题称为线性规划；当目标函数和约束函数中至少有一个为非线性函数时，相应的问题称为非线性规划；如果目标函数是二次函数而约束函数是线性函数则称为二次规划；包含非光滑函数的问题称为非光滑优化；不能直接求导数的问题称为无导数优化；变量只能取整数的问题称为整数规划；在线性约束下极小化关于半正定矩阵的线性函数的问题称为半定规划，其广义形式为锥规划。1.1.1最优化问题概述最优解只有少量非零元素的问题称为稀疏优化；最优解是低秩矩阵的问题称为低秩矩阵优化。此外还有几何优化、二次锥规划、张量优化、鲁棒优化、全局优化、组合优化、网络规划、随机优化、动态规划、带微分方程约束优化、微分流形约束优化、分布式优化等。就具体应用而言，问题（1.1）可涵盖统计学习、压缩感知、最优运输、信号处理、图像处理、机器学习、强化学习、模式识别、金融工程、电力系统等领域的优化模型。1.1.2实例：稀疏化给定b

∈

Rm，矩阵A

∈

Rm×n，且向量b

的维数远小于向量x的维数，即m

«

n。

考虑线性方程组求解问题：Ax=

b.(1.2)注意到由于m

«

n，方程组（1.2）是欠定的，因此存在无穷多个解，重构出原始信号看似很难。这些解当中大部分是不重要的，真正有用的解是所谓的“稀疏解”，即原始信号中有较多的零元素。如果加上稀疏性这一先验信息，且矩阵A以及原问题的解u满足某些条件，那么可以通过求解稀疏优化问题把u与方程组（1.2）的其他解区别开。这类技术广泛应用于压缩感知（compressive

sensing），即通过部分信息恢复全部信息的解决方案。1.1.2实例：稀疏化

（1.3）1.1.2实例：稀疏化在MATLAB环境里构造A,

u

和b：m=128;n=

256;A=randn(m,n)

;u

=

sprandn

(

n

,

1

,

0

.

1

)

;b=A∗u

;构造一个128

×

256矩阵A，它的每个元素都服从高斯（Gauss）随机分布。精确解u只有10%的元素非零，每一个非零元素也服从高斯分布图11.1.2实例：稀疏化

1.1.2实例：稀疏化

图21.1.2实例：稀疏化问题（1.3）的理论和算法研究在2006年左右带来了革命性的影响．理论上研究的课题包括什么条件下问题（1.3）的解具有稀疏性，如何改进这些条件，如何推广这些条件到其他应用。常见的数据矩阵A一般由离散余弦变换，小波变换，傅里叶（Fourier）变换等生成。虽然这些矩阵本身并没有稀疏性，但通常具有很好的分析性质，保证稀疏解的存在性。注意到绝对值函数在零点处不可微，问题（1.3）是非光滑优化问题．虽然它可以等价于线性规划问题，但是数据矩阵A通常是稠密矩阵，甚至A的元素未知或者不能直接存储，只能提供Ax或ATy等运算结果．在这些特殊情况下，线性规划经典的单纯形法和内点法通常不太适用于求解大规模的问题（1.3）。需要强调的是，问题（1.3）主要特点是其最优解是稀疏向量，它是稀疏优化的一种典型形式。1.1.2实例：稀疏化Lasso问题

1.1.3实例：深度学习深度学习（deeplearning）是机器学习的一个子领域，它采用了一个特定的模型：一族通过某种方式连接起来的简单函数。由于这类模型的结构是受到人类大脑结构的启发而创造出来的，因此通常把它们称为神经网络（neuralnetworks）。神经网络中的函数链条能够将复杂的概念分解为多个层次的更简单的概念，这就是深度学习的核心思想。深度学习的起源可以追溯至20世纪40年代，其维形出现在控制论中。近十年来深度学习又重新走入了人们的视野，深度学习问题和算法的研究也经历了一次新的浪潮。虽然卷积网络的设计受到了生物学和神经科学的启发，但深度学习目前的发展早已超越了机器学习模型中的神经科学观点。它用相对简单的函数来表达复杂的表示，从低层特征概括到更加抽象的高层特征，让计算机从经验中挖掘隐含的信息和价值。1.1.3实例：深度学习机器学习中典型问题形式

1.1.3实例：深度学习多层感知机

1.1.3实例：深度学习多层感知机模型介绍

1.1.3实例：深度学习常见的激活函数类型

1.1.3实例：深度学习多层感知机上述过程可用下图表示：图3：带p个输入单元和q个输出单位的(L+2)层感知机的网络图，第l个隐藏层包含m(l)

个神经元．1.1.3实例：深度学习卷积神经网络CNN

图41.1.3实例：深度学习卷积神经网络CNNLeCun等人开创性的建立了数字分类的神经网络。几家银行使用它来识别支票上的手写数字。图502PARTtwo基本知识1.2.1向量和矩阵范数1.2.2多元函数分析1.2.3凸集与凸函数1.2.4最优化问题的迭代解法1.2.5收敛速度与计算终止准则1.2.1向量的矩阵和范数

1.2.1向量的矩阵和范数

1.2.1向量的矩阵和范数

1.2.1向量的矩阵和范数向量序列和矩阵序列的收敛性

1.2.1向量的矩阵和范数向量序列和矩阵序列的收敛性

1.2.2多元函数分析

1.2.2多元函数分析

1.2.2多元函数分析

1.2.2多元函数分析

1.2.2多元函数分析

1.2.2多元函数分析

1.2.2多元函数分析

1.2.3凸集和凸函数

1.2.3凸集和凸函数

1.2.3凸集和凸函数

1.2.3凸集和凸函数

1.2.3凸集和凸函数

1.2.3凸集和凸函数

1.2.3凸集与凸函数凸函数性质

利用凸函数的定义来判断一个函数是否具有凸性并非一件容易的事情。如果函数是一阶或二阶连续可微的，则可利用函数的梯度或Hesse阵来判别或验证函数的凸性要相对容易一些。1.2.3凸集与凸函数判别定理

1.2.3凸集与凸函数定义1.7

有了定义1.7，可以把一元函数关于用二阶导数表述凸性的结果推广到多元函数上。1.2.3凸集与凸函数判别定理

1.2.4最优化问题的迭代解法

1.2.4最优化问题的迭代解法由上面的迭代过程可知，在迭代过程中有两个规则需要确定：一个是搜索方向的选取；一个是步长因子的选取．一旦选取方法和的选取方法确定，则一种迭代算法A就确定，即不同的规则就对应不同的最优化方法．1.2.4最优化问题的迭代解法下降迭代算法

1.2.4最优化问题的迭代解法

1.2.5收敛速度与计算终止准则

（1）收敛速度1.2.5收敛速度与计算终止准则

1.2.5收敛速度与计算终止准则

1.2.5收敛速度与计算终止准则

1.2.5收敛速度与计算终止准则

用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题。从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代．但是这在实际上是办不到的。因为对于一个待求的优化问题，其理论极小点在哪里并不知道．所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代。对于无约束优化问题通常采用的迭代终止准则有以下几种：（2）计算终止准则1.2.5收敛速度与计算终止准则

（2）计算终止准则1.2.5收敛速度与计算终止准则

（2）计算终止准则1.2.5收敛速度与计算终止准则（2）计算终止准则03PARTTHREE线搜索方法1.3.1精确线搜索方法1.3.2非精确线搜索方法1.3.3线搜索法的收敛性1.3.1精确线搜索方法精确线搜索的基本思想是：首先确定包含问题最优解的搜索区间，然后采用某种插值或分割技术缩小这个区间，进行搜索求解。本小节，主要介绍一维搜索法和Newton切线法

1.3.1精确线搜索方法（1）一维搜索法

1.3.1精确线搜索方法（1）一维搜索法1.3.1精确线搜索方法迭代点的梯度正交性与搜索方向的几何意义

1.3.1精确线搜索方法迭代点的梯度正交性与搜索方向的几何意义

1.3.1精确线搜索方法（2）Newton切线法——基本原理

1.3.1精确线搜索方法（2）Newton切线法——迭代步骤

1.3.1精确线搜索方法（2）Newton切线法——迭代步骤

流程图：1.3.1精确线搜索方法（2）Newton切线法——优点与局限1.高收敛速度的优点Newton切线法在选择合适的初始点时，具有非常高的收敛速度。在理想情况下，通常只需几次迭代即可达到所需的精度。1.3.1精确线搜索方法（2）Newton切线法——优点与局限

1.3.2非精确线搜索方法精确线搜索的局限精确线搜索虽然理论上有效，但在实际应用中面临以下问题：需要频繁计算目标函数值与梯度，计算开销大。当迭代点距离最优点较远时，精确搜索反而低效，甚至误导优化方向。

放宽对最优步长的要求，只需满足适度下降。在计算资源有限、目标函数复杂或高维场景下，更加高效可靠。能保持算法收敛性，同时减少函数/梯度评估次数。非精确线搜索的优势本节着重介绍非精确线搜索中的Wolfe准则和Armijo准则1.3.2非精确线搜索方法（1）Wolfe准则——准则定义

Wolfe准则兼顾目标函数值下降与方向有效性，适用于大多数优化算法中的非精确线搜索步骤。1.3.2非精确线搜索方法（1）Wolfe准则——强Wolfe准则

1.3.2非精确线搜索方法（1）Wolfe准则——步长存在性定理

1.3.2非精确线搜索方法（2）Armijo准则

1.3.2非精确线搜索方法（2）Armijo准则—程序算法1.3.2非精确线搜索方法（2）Armijo准则—程序算法程序1.1（Armijo搜索程序）Armijo搜索准则是许多非线性优化算法都必须执行的步骤，把它编制成可重复利用的程序模块是很有意义的。1.3.2非精确线搜索方法（2）Armijo准则

1.3.2非精确线搜索方法（2）Armijo准则1.3.3线搜索法的收敛性线搜索算法框架所谓“线搜索法”是指用线搜索策略求步长因子的无约束优化问题下降类算法的简称，其一般的算法框架如下。

1.3.3线搜索法的收敛性线搜索算法框架

1.3.3线搜索法的收敛性定理

04PARTFOUR无约束问题1.4.1无约束问题的最优性条件1.4.2梯度法及其MATLAB实现1.4.3牛顿法及其MATLAB实现1.4无约束优化问题

1.4.1无约束问题的最优性条件

无约束优化问题与极小点定义1.4.1无约束问题的最优性条件

一阶必要条件1.4.1无约束问题的最优性条件

二阶必要条件1.4.1无约束问题的最优性条件

二阶充分条件1.4.1无约束问题的最优性条件

二阶充分条件1.4.2梯度法及其MATLAB实现梯度法步骤1.4.2梯度法及其MATLAB实现

搜索方向对算法的影响

函数沿方向的变化率分析1.4.2梯度法及其MATLAB实现

最速下降法1.4.2梯度法及其MATLAB实现

全局收敛保证1.4.2梯度法及其MATLAB实现

全局收敛性1.4.2梯度法及其MATLAB实现

收敛速度估计1.4.2梯度法及其MATLAB实现

收敛速度与条件数关系1.4.2梯度法及其MATLAB实现基于Armijo非精确线搜索的梯度法MATLAB程序1.4.2梯度法及其MATLAB实现

例题1.4.2梯度法及其MATLAB实现解首先，编写好目标函数及其梯度的两个m文件fun.m和gfun.m：例题

1.4.3牛顿法及其MATLAB实现

牛顿法1.4.3牛顿法及其MATLAB实现基本牛顿法步骤牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性。1.4.3牛顿法及其MATLAB实现

局部二阶收敛性1.4.3牛顿法及其MATLAB实现基于Armijo搜索的阻尼牛顿法1.4.3牛顿法及其MATLAB实现

全局收敛性定理1.4.3牛顿法及其MATLAB实现

超线性收敛性与收敛速度分析1.4.3牛顿法及其MATLAB实现阻尼牛顿法程序1.4.3牛顿法及其MATLAB实现

例题1.4.3牛顿法及其MATLAB实现解除了例1.11中建立的两个计算目标函数和梯度的m文件之外，还需建立求Hesse阵的m文件：例题

05PARTFIVE约束优化的罚函数法1.5.1外罚函数法1.5.2内点法1.5.3乘子法1.5.4乘子法及其MATLAB实现1.5约束优化的罚函数法本节介绍求解约束优化问题的另一经典算法——罚函数法。其基本思想是：根据约束条件的特点，将其转化为某种惩罚函数加到目标函数中去，从而将约束优化问题转化为一系列的无约束优化问题来求解。通过求解一系列无约束最优化问题来得到约束优化问题的最优解，这类方法称为序列无约束极小化方法。本章主要介绍外罚函数法、内点法和乘子法。前言1.5.1外罚函数法最早的罚函数法是由Courant在1943年提出来的。下面通过两个简单的例子阐明罚函数法的基本思想。

例1.13

例1.141.5.1外罚函数法

例1.13

1.5.1外罚函数法

例1.13

1.5.1外罚函数法

例1.14

1.5.1外罚函数法

例1.14

1.5.1外罚函数法

例1.14

1.5.1外罚函数法

例1.14

1.5.1外罚函数法

外罚函数法

1.5.1外罚函数法

外罚函数法算法步骤1.5.1外罚函数法

收敛性分析1.5.2内点法

不等式约束问题的内点法1.5.2内点法

不等式约束问题的内点法1.5.2内点法

不等式约束问题的内点法1.5.2内点法

不等式约束问题的内点法

1.5.2内点法

不等式约束问题的内点法

1.5.2内点法

不等式约束问题的内点法续

：其几何意义如图：

1.5.2内点法

不等式约束问题的内点法内点法算法步骤1.5.2内点法

收敛性分析

不等式约束问题的内点法1.5.2内点法

一般约束问题的内点法1.5.2内点法一般约束问题的内点法

1.5.3乘子法起源与发展乘子法是Powell和Hestenes于1969年针对等式约束优化问题时独立提出的一种优化算法；后于1973年由Rockfellar推广到求解不等式约束优化问题。其基本思想是从原问题的拉格朗日函数出发，再加上适当的罚函数，从而将原问题转化为求解一系列的无约束优化问题。

与外罚函数比较1.5.3乘子法等式约束问题的乘子法

1.5.3乘子法等式约束问题的乘子法

1.5.3乘子法等式约束问题的乘子法

1.5.3乘子法等式约束问题的乘子法1.5.3乘子法等式约束问题的乘子法

1.5.3乘子法等式约束问题的乘子法

1.5.3乘子法一般约束问题的乘子法

1.5.3乘子法一般约束问题的乘子法

1.5.3乘子法