《【清华】yh2-优化基础理论（凸分析）【GHOE】》由会员分享，可在线阅读，更多相关《【清华】yh2-优化基础理论（凸分析）【GHOE】（61页珍藏版）》请在金锄头文库上搜索。
1、1 1 4 优化基本理论 2 1 4 1 函数的连续性 处连续 在点则称函数 存在 存在 有 若存在某一点对于函数 0 0 0 0 0 0 lim 3 lim 2 1 xx xx x x xx xx xx 3 4 1 4 2 函数的可微性 上的一个可微函数 为区间称 上的每一个点都可微 若在区间 处是可微的 在点则称函数 存在 处的导数在点若函数 x xx xxx 0 0 5 可微的 在什么区间上是连续或 指出下列函数 函数的连续性分析 例 xx x x ln 2 1 1 11 6 优化问题的目标函数及约束函数的不连续性 会 给优化搜索过程带来一些困难 不可微性对于不用导数的优化方法来说 对优
2、化 搜索过程不会产生影响 而对于要用到导数的优 化方法来说 会导致优化搜索过程不能进行 7 1 4 3 最优解的概念 8 1 4 3 1 局部最优解 极小值 上的局部 或严格局部在为 极小点 上的局部 或严格局部在为 称或 不等式 均满足 且 即的小于 的距离使所有与如果存在 对于 则有元实函数 其中的 上上的某一领域维空间为定义在设 Nxf Nxfx xfxfxfxf xxNxNx xNx xxxxn Nnxf T n n 0 21 9 1 4 3 2 全局最优解 极小值 上的全局 或严格全局为在 极小点 上的全局 或严格全局在为 则称或 都有 而对于所有若点 Nxf Nxfx xfxf x
3、fxfNxNx 10 1 4 4 单峰与多峰函数 为极小值 的单峰区间称为函数 区间上的单峰函数 为在升 则称 严格上严格下降 在在区间 上只有一个极小点在区间设函数 00 00 0 0 00 xxba bax bxxax bax 11 xa 单峰函数 12 xfb 单峰函数 13 xc 多峰函数 14 xfd 多峰函数 15 1 4 5 目标函数的等值线 称为目标函数的等值线 函数值都等于同一常数曲线上任何一点的目标 求例 2 2 2 121 12 min 21 xxxxf 16 17 18 1 4 6 凸集和凹集 凹集 为一凸集 否则 称为则称 的连线的一切点均有 点上的一个点集 任意两维
4、空间是设 D Dxx DxDx nD n 10 1 21 21 19 20 是否为凸集 试确定集合例 42 31 321321 xxxxxxxD T 21 例1 3 证明过程 为凸集 DDxxxx xx xx xx xxx xxxxxx xxxDx xxxDx 42 1 1 1 1 4 1 1 2 1 1 2 1 2 42 1 42 321 2 3 1 3 2 2 1 2 2 1 1 1 21 2 3 1 3 2 2 1 2 2 1 1 1 2 3 2 2 2 1 2 1 3 1 2 1 1 1 22 1 4 7 凸函数与凹函数 凹函数的定义 反号就是凹函数与严格若将上两式中的不等式 上的严格
5、凸函数 为定义在则称 恒有 以及任意两点若对任意实数 上的凸函数 为定义在则称 恒有点 以及任意两的函数 若对任意实数 上中某一个凸集维空间为定义在设 Dxf xfxfxxf Dxx Dxf xfxfxxf DxDx Dnxf n 1 1 10 1 1 10 2121 21 2121 21 23 图 1 12 凸函数与凹函数 凸函数 凹函数 24 上的凸函数 是 试验证一元函数例 1 41 xx 25 例1 4 证明过程 为凸函数 x xx xx xx xxxx xxxx xx 21 21 21 2121 2211 2211 1 1 1 11 10 26 多元函数的Taylor展开式 时的高阶
6、无穷小量 表示当 之间的距离 与点表示点 矩阵 的在点 的梯度 在点 0 where 2 1 kk kk kk kk kkk T k k T kk xxxx xxxx HessianxxfxH xxfxf xxxxxHxx xxxfxfxf 27 梯度 T n kkk k k k T n n x xf x xf x xf xf xxf nnx xxxxxxf 21 21 处的梯度 记作 在点为函数 维向量 称个一阶偏导数所构成的处的一点 在某梯度 函数 28 处的梯度 在点 求函数例 T x xxxxxf 1 1 565 61 0 2 221 2 1 29 偏导数 处的二阶在点为函数 阶对称矩
7、阵 矩阵是指下述的的 处在某一点函数 k ji k n k n k n k n kkk n kkk kk k T n n xxfnjni xx xf x xf xx xf xx xf xx xf x xf xx xf xx xf xx xf x xf xfxH nnHessian xxxxxxxf 1 1 2 2 2 2 2 1 2 2 2 2 2 2 12 2 1 2 21 2 2 1 2 2 21 L MLMM L L Hessian矩阵 30 矩阵 处的在点 求函数例 Hessianx xxxxx xxxxxf T 1 0 22 245 44 71 0 2 2 1 4 121 2 2 2
8、 121 31 判断函数凸性的一阶条件 12112 21 xxxfxfxf Dxx Dxf xfn T n 恒有点充要条件是 对任意两 上的凸函数的为具有连续一阶导数 则 上的函数维空间一阶条件 设定义在 32 一阶条件的几何解释 1211 xxxfxf T x1x2x 0 f x f x1 f x2 111 xxxfxf T 33 凸函数一阶条件证明过程 必要性 12112 12121 12 1121 0 12 1121 121121 1212 12 lim 11 xxxfxfxf xfxfxxxf xfxf xfxxxf xfxf xfxxxf xfxfxfxxxf xfxfxxf DxD
9、x T T 系定理得到由方向导数与梯度的关 由凸函数的定义 34 凸函数一阶条件证明过程 充分性 为凸函数 xf xxf xxxxfxfxfxf xxxfxfxf xxxfxfxf DxxxDxDx T T T 21 2121 22 11 2121 1 11 1 2 1 2 1 1 35 判断函数凸性的二阶条件 是半正定的 矩阵的的任意一点 是 上的凸函数的充要条件为凸集则 具有连续二阶导数 上的函数维空间设定义在 xHHessianDxxf Dxf xfn n 36 凸函数二阶条件证明过程 充分性 为凸函数 由一阶条件 半正定 其中 根据中值定理有 xf xxxfxfxf xxxHxxxH
10、Dxxxx xxxHxxxxxfxfxf DxDx T T TT 0 1 0 1 2 1 37 凸函数二阶条件证明过程 必要性 半正定 舍去高阶无穷小有 代入上述不等式有 根据泰勒展开有 代入一阶条件得上式 其中 由一阶条件为凸函数 取任意 xH xxxHxx xxxxxHxx xxxxxHxxxxxfxfxxxf xxxxxx xxxfxfxxxf Dxxf T T TT T 0 0 2 1 2 1 2 2 2 2 12 38 是凸函数还是凹函数 判定函数例 10223 51 2 2 21 2 1 xxxxxf 39 凸函数的全局极小值 上的全局极小点 局部极小点就是它在的凸函数 则它的任一
11、 上上某一开凸集维空间为定义在设 D Dnxf n 40 凸函数的局部极小为全局极小的证明过程 示意图 x x x 41 凸函数的局部极小为全局极小的证明过程 的全局极小点 为矛盾 为凸函数 则由 且满足 令存在全局极小 有满足对于任意 全局最小 的局部极小点 但不是为反证法 假设 xfx xfxfxfxfxfxf xf xxxxx xfxfDx xfxfxxx xfx 11 10 1 42 1 4 9 无约束优化问题最优解存在的充 分必要条件 n xts xf min 43 1 4 9 2 必要条件 的稳定点 称为函数的解或满足式 或 件是的一个最优解的必要条 为处一阶连续可微 在点若函数
12、xfx x xf x xf x xf xf xfxxxf n 7 16 1 7 1 0 6 1 0 2 1 L 44 的所有稳定点 求函数例 2 2 1 4 121 2 2 2 121 22 245 44 81 xxxxx xxxxxf 45 图 1 13 稳定点图示 46 1 4 9 3 充分条件 定的 为正矩阵的在点条件是函数 的一个最优解的充分为的一个稳定点 则 为 具有连续的二阶偏导数若函数 xHHessianxxf xfx xfxxf 47 是否为最优解 的三个稳定点 所得函数试判定例例 TT T xx x xxxxx xxxxxf 492 1 611 0 028 1 053 1 8
13、54 3 941 1 22 245 44 8 1 91 32 1 2 2 1 4 121 2 2 2 121 48 表1 4 判定结果 稳定点f x Hessian矩阵特征值稳定点类别 1 941 3 854 0 98537 030 97局部极小点 1 053 1 028 0 513410 53 5全局极小点 0 611 1 492 2 837 0 2 56鞍点 49 1 4 10 下降迭代算法及其收敛性 0 0 0 0 8 1 min 2 1 21 n n T n x xf x xf x xf xf xxxxxf M 即 50 1 4 10 1 下降迭代算法 法 这种迭代法称为下降下降 即
14、一步都使目标函数有所始点之后 如果每迭代 在给定初列收敛于那么 该算法产生的序 或 的极小点 即极限恰好是问题 法 如果这个序列的 这种规则通常称为算 生一个序列 然后按一定的规则产点 计的极小点的一个初始估给定目标函数 kk k k k k k xfxf x xx xx xx xf 1 0 0lim lim 81 51 kk k kk k k kk kk k k k k k xfpxfxf pxx pxx p x x x x LL 110 kk k k xfxfxfxf x p 54 kkk k k k k k pxfpxf p k min 1 一维搜索 使 进行上对搜索方向最优步长因子法
15、即在 函数下降 次的目标常数 满足定步长法 即取 的选取步长因子 55 1 4 10 2 下降迭代算法的收敛速度与终止准则 56 1 收敛速度 为二次收敛 为超线性收敛 为线性收敛 无关的常数 为与 的实数 阶收敛 其中则称该算法为 且满足的最优解 收敛于优化问题列设某种算法所产生的点 k k k p k k k k xp xp xp k cpp c xx xx x x 2 21 1 01 lim 1 57 2 终止准则 10 1 9 1 0 1 1 kk kk k xx xx xx为给定的误差 58 图1 15 单一准则的不可靠性 59 k kk k kk x xx x xx 1 1 60 梯度终止准则 0 的条件 只要求凸函数
