电子科技大学：《机器学习 Machine Learning》课程教学资源（课件讲稿）第2章 数值最优化介绍

最优T化回顾 电子科技大学 师君

电子科技大学 师 君

最优化问题 解的特点 问题转化 迭代法

最优化问题 解的特点 问题转化 迭代法

最优化问题 ,最优化一一寻找最大（小）值和对应位置： 。数值最优化一一连续（可导）问题的最值； ·最速下降、牛顿法、内点法… 。组合最优化一一离散问题的最值； ·最短路径、最优遍历… 。演化最优化一一通过随机搜索，寻找最值； ·模拟退火（SA)、遗传算法(GA)、微分进化(DE)、蚁群 算法(AA)、粒子群算法(PA)…

 最优化——寻找最大（小）值和对应位置: ◦ 数值最优化——连续（可导）问题的最值；  最速下降、牛顿法、内点法…… ◦ 组合最优化——离散问题的最值；  最短路径、最优遍历…… ◦ 演化最优化——通过随机搜索，寻找最值；  模拟退火（SA）、遗传算法（GA）、微分进化（DE）、蚁群 算法（AA）、粒子群算法（PA）……

最优化问题概念 ,无约束最优化问题 minf(x),f(x):R”→R ,约束最优化问题： min f(x), f(x):R”→R Ceq,(x)=0 s.t.< Cie,(x)≥0

 无约束最优化问题  约束最优化问题: min ( ), ( ) : n f f x x  min ( ), ( ) : ( ) 0 . . ( ) 0 n i i f f Ceq s t Cie       x x x x

最优化问题的几何解释 R f(x) 可行解集 等式约束 R 最小值 最大值 不等式约束

( ) f x 不等式约束 等式约束 3 可行解集 最小值 最大值

最优解的存在性 ，最优化解存在的充分条件 。Weierstrass定理： (x)为连续函数 ①为紧密集 理解：1、实数域的紧密子集存在最大值和最小值 2、连续函数将紧密集映射为紧密集（利用柯西序列判 定)

 最优化解存在的充分条件 ◦ Weierstrass定理： 理解：1、实数域的紧密子集存在最大值和最小值 2、连续函数将紧密集映射为紧密集（利用柯西序列判 定） f ( ) x 为连续函数 D为紧密集

最优解的存在性 实数域的紧密子集存在最大值和最小值 1.紧密集为有界集，存在上下确界。 2.上、下确界属于紧密集 D=[-1,1] ①=R ①=(-1,1) ①=[-1,1]U[3,4] ①=[-1,0) D=[-1,1]∩Q 紧密集 无界不紧密集 有界不紧密集

实数域的紧密子集存在最大值和最小值 1.紧密集为有界集，存在上下确界。 2.上、下确界属于紧密集 D  [ 1,1] D  [ 1,1] D  ( 1,1) D  [ 1,1] [3, 4] D    [ 1, ) D  紧密集 无界不紧密集 有界不紧密集

最优解的存在性 ,思考：下列最优解是否存在？ f(x)=x2,x∈[0.01,1] f(x)=x2;x∈[-1,1]∩Q tno f(x)=x2,x∈(0.01,1] f(x)=-;x∈[-1,1] X

 思考：下列最优解是否存在?   2 f x x x ( ) , 0.01,1   2 f x x x ( ) ; [ 1,1]    2 f x x x ( ) , (0.01,1]   2 ( ) ; [ 1,1] 4 f x x x            1 f x x ( ) ; [ 1,1] x   

最优化问题 解的特点 问题转化 迭代法

最优化问题 解的特点 问题转化 迭代法

最优解的特点 Local Max ,最值vs极值 Local Max Local Max Local Min Local Min 极值点： 。在可行解集中，存在一个邻域N,使得任意x∈W都有： f(x*)≤f(x),X∈N(x*) 。则x*为该函数的极值点

 最值 vs 极值  极值点： ◦ 在可行解集中，存在一个邻域N，使得任意 都有： ◦ 则x*为该函数的极值点。 xN f f ( *) ( ), ( *) x x x x  N