凸优化理论与应用-无约束优化

信息与通信工程学院庄伯金[e-mail]1凸优化理论与应用第8章无约束优化信息与通信工程学院庄伯金[e-mail]2无约束优化问题问题描述：minimize()fx无约束问题求解的两种方法：迭代逼近：()*()kfxp求解梯度方程：*()0fx为凸函数，且二次可微。()fx信息与通信工程学院庄伯金[e-mail]3例梯度方程*0Pxq二次优化：1minimize,2TTnxPxqxrPS信息与通信工程学院庄伯金[e-mail]4迭代起始点满足条件2的几种函数：起始点满足：(0)(0)1.dom2.{dom|()()}xfSxffxfx；为闭集。(0)x函数任意下水平集都是闭集；()fx函数的定义域为nR当时，bddomxf()fx信息与通信工程学院庄伯金[e-mail]5强凸性定义：函数在上具有强凸性，若满足2(),0fxmIm()fxS()fx若函数具有强凸性，则有2222()()()()21()()2Tmfyfxfxyxyxfxfxm()fx为最优值，则2*21()()2fxpfxm*p信息与通信工程学院庄伯金[e-mail]6强凸性为最优解，则*222()xxfxm*x信息与通信工程学院庄伯金[e-mail]7强凸性则有22()()()()2TMfyfxfxyxyx为最优值，则2*21()()2pfxfxM*p若函数在上具有强凸性，则可以证明存在，满足2()fxMI()fxS0M信息与通信工程学院庄伯金[e-mail]8强凸性对于，矩阵的特征值从大到小依次为。则有：21()nmIIfxIMIxS2()nfxS1{,...,}n定义：矩阵的条件数为最大特征值与最小特征值之比，即。1/nr2()nfxS/rMm条件数的上界：信息与通信工程学院庄伯金[e-mail]9下降法下降法的基本原理：迭代，满足(1)()kkxxtx为下降方向，为步长因子。(1)()()()kkfxfxxt对于凸函数，当满足时，存在某个，使得。()fxx()0Tfxxt(1)()()()kkfxfx信息与通信工程学院庄伯金[e-mail]10下降法下降法的一般步骤：给出初始点；domxf循环迭代计算下降方向；x搜索步长因子；t迭代：xxtx信息与通信工程学院庄伯金[e-mail]11步长因子搜索精确一维搜索：0argmin()ttfxtx回溯一维搜索：给定参数循环迭代初始化：令；若，则终止退出；(0,0.5),(0,1)否则令tt1t()()()Tfxtxfxtfxx信息与通信工程学院庄伯金[e-mail]12步长因子搜索m信息与通信工程学院庄伯金[e-mail]13梯度下降法算法简单，但收敛速度较慢。下降方向：()xfx终止条件：2()fx收敛性：其中。()*(0)*()(())kkfxpcfxp(0,1)c信息与通信工程学院庄伯金[e-mail]14收敛性分析则有：设函数具有强凸性，则存在和，满足：()fx2()mIfxMI0m0M22222()()()()2Mtfxtxfxtfxfx若采用精确一维搜索，则，收敛速度因子：t1/tM1/cmM若采用回溯一维搜索，收敛速度因子：t1min{2,2/}cmmM条件数越大，收敛速度越小。信息与通信工程学院庄伯金[e-mail]15例当时，算法收敛速度很慢。11or初始解为，采用精确一维搜索；(,1)22121minimize(),02xx迭代：()111kkx()211kkx信息与通信工程学院庄伯金[e-mail]16例步长因子采用回溯一维搜索。1minimizelog(),500,100mTTiiicxbaxmn信息与通信工程学院庄伯金[e-mail]17最速下降法归一化最速下降方向：argmin{()|1}Tnsdvxfxvv非归一化最速下降方向*()sdnsdxfxx欧式范数：()sdxfx二次范数：1/2()TPxxPx1()sdxPfx范数：1l()()sdnsdiifxxxfxex信息与通信工程学院庄伯金[e-mail]18最速下降法信息与通信工程学院庄伯金[e-mail]19收敛性分析范数界：*2,(0,1]xx收敛速度因子：2212min{1,/}cmM信息与通信工程学院庄伯金[e-mail]20牛顿法设函数二阶可微，则在附近，的泰勒展式为：21()()()()2TTfxxfxfxxxfxx()fxx()fx下降方向：21()()ntxfxfx泰勒展开可作为在附近的近似；()fxx为二次范数上的最速下降方向。221/2()(())Tfxxxfxx信息与通信工程学院庄伯金[e-mail]21牛顿法信息与通信工程学院庄伯金[e-mail]22牛顿减量令211/2()(()()())Txfxfxfx为在处的牛顿减量。()fxx()x牛顿减量的性质1：21()inf()()()()2ntyfxfyfxfxxx牛顿减量可作为迭代求解的误差估计。性质2：2()()Tntfxxx性质3：牛顿减量具有仿射不变性。信息与通信工程学院庄伯金[e-mail]23牛顿方法LOOP：初始化：给定初始解以及domxf0计算：221()()()Tfxfxfx21()()ntxfxfx若则终止退出；2/2一维线性搜索：计算步长因子；tntxxtx迭代：信息与通信工程学院庄伯金[e-mail]24收敛性分析定理：假设二阶连续可微，具有强凸性，即存在，满足：2()mIfxMI0Mm()fx且海森矩阵满足Lipschitz条件，即存在，满足：0L2222()()fxfyLxy则存在，20/,0mL2(1)()2222()()22kkLLfxfxmm若，则；若，则，且()2()kfx(1)()()()kkfxfx()2()kfx()1kt信息与通信工程学院庄伯金[e-mail]25收敛性分析定理：假设二阶连续可微，具有强凸性，即存在，满足：2()mIfxMI0Mm()fx且海森矩阵满足Lipschitz条件，即存在，满足：0L2222()()fxfyLxy则存在，对于，有0k1232()*()22121()()22lkllmfxpfxmLlk信息与通信工程学院庄伯金[e-mail]26例