凸优化理论与应用.ppt

凸凸优化理化理论与与应用用庄 伯 金B1 1-优化理论概述n什么是什么是优化化问题？Objective functionConstraint functions2 2-几类经典的优化问题n线性性规划划问题n最小二乘最小二乘问题n凸凸优化化问题凸凸优化化问题理理论上有上有有效的方法有效的方法进行求解！行求解！3 3-本课程的主要内容n理理论部分部分n凸集和凸函数凸集和凸函数n凸凸优化化问题n对偶偶问题n应用部分用部分n逼近与逼近与拟合合n统计估估计n几何几何问题n算法部分算法部分n非非约束束优化方法化方法n等式等式约束束优化方法化方法n内点法内点法4 4-n熟悉了解凸熟悉了解凸优化理化理论的基本原理和基本方法；的基本原理和基本方法；n掌握掌握实际问题转化化为凸凸优化化问题的基本方法；的基本方法；n掌握最掌握最优化化问题的的经典算法。典算法。课程要求5 5-参考书目nStephen Boyd and Lieven Vandenberghe,“Convex Optimization”,Cambridge University Press.n袁袁亚湘、湘、孙文瑜，文瑜，“最最优化理化理论与方法与方法”，科学出版，科学出版社，社，1999。6 6-凸凸优化理化理论与与应用用第一章第一章凸集凸集7 7-仿射集(Affine sets)n直直线的表示：的表示：n线段的表示：段的表示：8 8-仿射集(Affine sets)n仿射集的定仿射集的定义：过集合集合C内任意两点的直内任意两点的直线均在集合均在集合C内，内，则称集合称集合C为仿射集。仿射集。n仿射集的例：直仿射集的例：直线、平面、超平面、平面、超平面9 9-仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。n仿射仿射维数：仿射包的数：仿射包的维数。数。1010-仿射集n内点（内点（interior）：）：n相相对内点（内点（relative interior）：）：1111-凸集(Convex Sets)n凸集的定凸集的定义：集合：集合C内任意两点内任意两点间的的线段均在集合段均在集合C内，内，则称集合称集合C为凸集。凸集。1212-凸集n凸包的定凸包的定义：包含集合：包含集合C的最小的凸集。的最小的凸集。1313-锥(Cones)n锥的定的定义：n凸凸锥的定的定义：集合：集合C既是凸集又是既是凸集又是锥。n锥包的定包的定义：集合：集合C内点的所有内点的所有锥组合。合。1414-超平面和半空间n超平面超平面(hyperplane)：n半空半空间(Halfspace)：1515-欧氏球和椭球n欧氏球欧氏球(euclidean ball):n椭球球(ellipsoid):1616-范数球和范数锥n范数范数(norm)：n范数球范数球(norm ball)：n范数范数锥(norm cone)：1717-多面体(Polyhedra)n多面体：多面体：n单纯形形(simplex)：1818-半正定锥(Positive semidefinite cone)nn阶对称矩称矩阵集：集：nn阶半正定矩半正定矩阵集：集：nn阶正定矩正定矩阵集：集：n阶半正定矩半正定矩阵集集为凸凸锥！1919-保持凸性的运算n集合交运算集合交运算n仿射仿射变换n透透视/投射函数投射函数(perspective function)2020-保持凸性的运算n线性分式函数性分式函数(linear-fractional function)2121-真锥(proper cone)n真真锥的定的定义：锥 满足如下条件足如下条件K具有内点具有内点K内不含直内不含直线2222-广义不等式n真真锥 下的下的偏序关系偏序关系：n例：例：n逐逐项不等式不等式n矩矩阵不等式不等式广广义不等式不等式严格广格广义不等式不等式2323-广义不等式的性质2424-严格广义不等式的性质2525-最值和极值n最小元的定最小元的定义：设 ，对 ，都，都有有 成立，成立，则称称 为 的最小元。的最小元。n极小元的定极小元的定义：设 ，对于于 ，若若 ，则 成立，成立，则称称 为 的的极小元。极小元。2626-分割超平面(separating hyperplane)n定理：定理：设 和和 为两不相交凸集，两不相交凸集，则存在超平面存在超平面将将 和和 分离。即：分离。即：2727-支撑超平面(supporting hyperplane)n定定义：设集合集合 ，为 边界上的点。若存在界上的点。若存在 ，满足足对任意任意 ，都有，都有 成成立，立，则称超平面称超平面 为集合集合 在点在点 处的支撑超平面。的支撑超平面。n定理：凸集定理：凸集边界上任意一点均存在支撑超平面。界上任意一点均存在支撑超平面。n定理：若一个定理：若一个闭的非中空集合，在的非中空集合，在边界上的任意一点界上的任意一点存在支撑超平面，存在支撑超平面，则该集合集合为凸集。凸集。2828-对偶锥(dual cone)n对偶偶锥的定的定义：设 为锥，则集合集合 称称为对偶偶锥。n对偶偶锥的性的性质：真真锥的的对偶偶锥仍仍然是真然是真锥！2929-对偶广义不等式n广广义不等式与不等式与对偶等价性偶等价性质n最小元的最小元的对偶特性：偶特性：3030-对偶广义不等式n极小元的极小元的对偶特性偶特性反反过来不一定成来不一定成立！立！3131-作业nP60 2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.333232-凸凸优化理化理论与与应用用第二章第二章 凸函数凸函数3333-凸函数的定义1.定定义域域 为凸集；凸集；2.，有，有n凸函数的定凸函数的定义：函数：函数 ，满足足n凸函数的凸函数的扩展定展定义：若：若 为凸函数，凸函数，则可定可定义其其扩展函数展函数 为凸函数的凸函数的扩展函数展函数也是凸函也是凸函数！数！3434-凸函数的一阶微分条件n若函数若函数 的定的定义域域 为开集，且函数开集，且函数 一一阶可微，可微，则函数函数 为凸函数当且凸函数当且仅当当 为凸集，且凸集，且对3535-凸函数的二阶微分条件n若函数若函数 的定的定义域域 为开集，且函数开集，且函数 二二阶可微，可微，则函数函数 为凸函数当且凸函数当且仅当当 为凸集，且凸集，且对 ，其，其Hessian矩矩阵3636-凸函数的例n幂函数函数n负对数函数数函数n负熵函数函数n范数函数范数函数n指数函数指数函数3737-凸函数的例3838-下水平集(sublevel set)n定理：凸函数的任一下水平集均定理：凸函数的任一下水平集均为凸集。凸集。n任一下水平集均任一下水平集均为凸集的函数凸集的函数不一定不一定为凸函数。凸函数。称称为 的的 下水平集。下水平集。n定定义：集合：集合3939-函数上半图(epigraph)n定理：函数定理：函数 为凸函数凸函数当且当且仅当当 的上半的上半图为凸凸集。集。称称为函数函数 的上半的上半图。n定定义：集合：集合4040-Jensen不等式n 为凸函数，凸函数，则有：有：nJensen不等式的另外形式：不等式的另外形式：4141-保持函数凸性的算子n凸函数的逐点最大凸函数的逐点最大值n凸函数与仿射凸函数与仿射变换的复合的复合n凸函数的非凸函数的非负加加权和和4242-保持函数凸性的算子n复合运算复合运算n最小最小值算子算子n凸函数的透凸函数的透视算子算子4343-共轭函数(conjugate function)n定定义：设函数函数 ，其共，其共轭函数函数 ，定，定义为n共共轭函数的例函数的例共共轭函数函数具有凸性！具有凸性！4444-共轭函数的性质nFenchels inequalityn性性质：若：若 为凸函数，且凸函数，且 的上半的上半图是是闭集，集，则有有n性性质：设 为凸函数，且可微，凸函数，且可微，对于于 ，若，若则4545-准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定定义：设函数函数 ，若函数的定，若函数的定义域域和任意下水平集和任意下水平集则称函数称函数 为准凸函数。准凸函数。4646-准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且准凸函数，当且仅当当 为凸集，且凸集，且对 ，有，有n定理：若函数定理：若函数 一一阶可微，可微，则 为准凸函数，准凸函数，当且当且仅当当 为凸集，且凸集，且对 ，有，有 ，有，有n定理：若函数定理：若函数 二二阶可微，且可微，且满足足对则函数函数 准凸函数。准凸函数。4747-n最小最小值函数函数n非非负权值函数的最大函数的最大值函数函数保持准凸性的算子n复合函数复合函数4848-准凸函数的凸函数族表示n若若 为准凸函数，根据准凸函数，根据 的任意的任意 下水平下水平集，我集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得n性性质：若：若 为准凸函数准凸函数 的凸函数族表示，的凸函数族表示，对每一个每一个 ，若，若 ，则有有4949-对数凸函数 为凸集凸集为凸函数。凸函数。n定定义：函数：函数 称称为对数凸函数，若函数数凸函数，若函数 满足：足：n定理：函数定理：函数 的定的定义域域为凸集，且凸集，且 ，则 为对数凸函数，当且数凸函数，当且仅当当对 有有n对数凸函数的例数凸函数的例5050-对数凸函数和凹函数的性质n性性质：对数凸性与凹性数凸性与凹性对函数乘函数乘积和正数数乘运算均保持封和正数数乘运算均保持封闭。n定理：函数定理：函数 二二阶可微，可微，则 为对数凸函数数凸函数当且当且仅当当n性性质：对数凸性数凸性对函数加运算保持封函数加运算保持封闭。但。但对数凹性数凹性对函数函数加运算不封加运算不封闭。n推推论：函数：函数 对每一个每一个 在在 上上对数凸，数凸，则函数函数 也是也是对数凸函数。数凸函数。5151-对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，数凹函数，则函数函数 是是对数凹函数。数凹函数。5252-广义不等式下的凸性n广广义单调性的定性的定义：设 为真真锥，函数，函数 称称为 单调增，若函数增，若函数 满足：足：n广广义凸函数的定凸函数的定义：设 为真真锥，函数，函数 称称为 凸，若函数凸，若函数 满足足对 均有均有n定理定理(对偶等价偶等价)：函数函数 为 凸函数，当且凸函数，当且仅当当对所有所有 ，为凸函数。凸函数。5353-作业(1)nP116 3.16nP116 3.215454-作业(2)nP121 3.41nP122 3.49 (1)(2)5555-凸凸优化理化理论与与应用用第三章第三章 凸凸优化化5656-优化问题的基本形式n优化化问题的基本描述：的基本描述：优化化变量量不等式不等式约束束等式等式约束束无无约束束优化化5757-优化问题的基本形式最最优化化值最最优化解化解 优化化问题的域的域 可行点可行点(解解)(feasible)满足足约束条件束条件 可行域可行域(可解集可解集)所有可行点的集合所有可行点的集合5858-局部最优问题n局部最局部最优问题5959-优化问题的等价形式(1)n定理：若定理：若 则原原优化化问题与以下与以下优化化问题等价等价6060-优化问题的等价形式(2)n定理：定理：设 为一一一一对应，且，且 则原原优化化问题与以下与以下优化化问题等价等价6161-优化问题的等价形式(3)n定理：定理：设 为严格格单调增函数；增函数；满足足 当且当且仅当当 ；满足足 当且当且仅当当 。则原原优化化问题与以下与以下优化化问题等价等价6262-优化问题的等价形式(4)n定理：原定理：原优化化问题与以下与以下优化化问题等价等价n 称称为松弛松弛变量量6363-优化问题的等价形式(5)n定理：定理：设 满足等式足等式 成立，当且成立，当且仅当当 。则原原优化化问题与以与以下下优化化问题等价等价6464-可分离变量优化问题n性性质：其中其中可以分离可以分离变量量n定理：定理：优化化问题6565-优化问题的上半图形式6666-凸优化问题的基本形式n凸凸优化化问题的基本描述：的基本描述：为仿射函数仿射函数 为凸函数凸函数 若若 为准凸函数，准凸函数，则优化化问题称称为准凸准凸优化化问题。性性质：凸：凸优化化问题的可行域是凸集。的可行域是凸集。6767-凸优化问题的例n例：例：等价于凸等价于凸优化化问题6868-凸优化问题的局部最优解n定理：凸定理：凸优化化问题的局部最的局部最优解均是全局最解均是全局最优解。解。6969-凸优化问题最优解的微分条件n定理：定理：设 为凸凸优化化问题的可行域，的可行域，可微。可微。则 为最最优解当且解当且仅当当 成立。成立。n定理：非定理：非约束凸束凸优化化问题中，若中，若 可微。可微。则 为最最优解当且解当且仅当当 成立。成立。7070-凸优化问题的等价形式则 为最最优解当且解当且仅当当 ，且存在向量，且存在向量 满足足 n定理：定理：设凸凸优化化问题仅有等式有等式约束束7171凸优化问题的等价形式则 为最最优解当且解当且仅当当 ，且，且 n定理：定理：设凸凸优化化问题7272-凸优化问题的等价形式等价于等价于 n定理：定理：设凸凸优化化问题其中其中 7373-凸优化问题的等价形式等价于等价于 n定理：定理：设凸凸优化化问题7474-准凸优化问题 为准凸函数，准凸函数，为凸函数。凸函数。n准凸准凸优化化问题的基本描述的基本描述n注：准凸注：准凸优化化问题的局部最的局部最优解不一定是全局最解不一定是全局最优解。解。7575-准凸优化问题的上半图形式n设 为准凸函数准凸函数 的凸函数族表示，即的凸函数族表示，即 则准凸准凸优化化问题的可行解的可行解问题为n设 为准凸准凸优化化问题的最的最优解，若上述解，若上述问题可解，可解，则 。否。否则 。7676-准凸优化问题二分法求解n给定一个足定一个足够小的小的 和足和足够大的大的 ，使得区，使得区间 能包含最能包含最优解解 。给定定nLOOP：n令令n求解可行解求解可行解问题；n若可解，若可解，则令令 ，否，否则令令n若若 ，则结束，否束，否则goto LOOP。7777-线性规划(linear program,LP)nLP问题的一般描述的一般描述7878-LP问题的几种类型n标准准LP问题n不等式形式不等式形式LP问题7979-标准LP问题的转换8080-LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming8181-Chebyshev center of a polyhedronn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）n问题描述nLP形式8282-Piecewise-linear minimizationn问题描述n上半图形式nLP形式8383-Linear-fractional programmingn问题描述nLP形式8484-二次规划(quadratic program,QP)nQP问题的基本描述的基本描述8585-二次约束二次规划nquadratically constrained quadratic program(QCQP)8686-QP问题的例nLeast-squares and regressionnDistance between polyhedra8787-Least-squares and regressionn问题描述8888-Distance between polyhedran问题描述nQP形式8989-Second-order cone program,SOCPnSOCP问题的基本描述n二次锥约束条件9090-SOCP问题的例Robust linear programmingn问题描述其中 不是完全确定的常数。n例：为确定的常数，为变量，其范围满足SOCP形式9191-几何规划(Geometric programming)n单项式与多项式n几何规划的基本描述9292-几何规划的凸形式转换n令n几何规划的凸形式9393-广义不等式约束n广义不等式约束的优化问题nSOCP的描述9494-凸凸优化理化理论与与应用用第四章第四章 对偶偶问题9595-优化问题的拉格朗日函数n设优化化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的固定的 ，拉格朗日函数，拉格朗日函数 为关于关于 和和 的的仿射函数仿射函数。9696-拉格朗日对偶函数n拉格朗日拉格朗日对偶函数偶函数(lagrange dual function)：若拉格朗日函数没有下界，若拉格朗日函数没有下界，则令令n拉格朗日拉格朗日对偶函数偶函数为凹函数凹函数。n对 和和 ，若原最，若原最优化化问题有最有最优值 ，则9797-对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem9898-Least-squares solution of linear equationsn原原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日拉格朗日对偶函数：偶函数：9999Standard form LPn原原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日拉格朗日对偶函数：偶函数：100100-Two-way partitioning problemn原原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日拉格朗日对偶函数：偶函数：101101-对偶函数与共轭函数n共共轭函数函数n共共轭函数与函数与对偶函数存在密切偶函数存在密切联系系n具有具有线性不等式性不等式约束和束和线性等式性等式约束的束的优化化问题：对偶函数：偶函数：102102-Equality constrained norm minimizationn问题描述：描述：n共共轭函数：函数：n对偶函数：偶函数：103103-Entropy maximizationn原始原始问题：n共共轭函数：函数：n对偶函数偶函数：104104-Minimum volume covering ellipsoidn原始原始问题：n对偶函数：偶函数：n共共轭函数：函数：105105-拉格朗日对偶问题n拉格朗日拉格朗日对偶偶问题的描述：的描述：n对偶可行域偶可行域n最最优值n最最优解解106106-LP问题的对偶问题n标准准LP问题n对偶函数偶函数n对偶偶问题n等价描述等价描述107107-弱对偶性n定理（弱定理（弱对偶性）偶性）：设原始原始问题的最的最优值为 ，对偶偶问题的最的最优值为 ，则 成立。成立。noptimal duality gapn可以利用可以利用对偶偶问题找到原始找到原始问题最最优解的下界。解的下界。108108-强对偶性n强对偶性并不是偶性并不是总是成立的。是成立的。n定定义（强对偶性）偶性）：设原始原始问题的最的最优值为 ，对偶偶问题的最的最优值为 。若。若 成立，成立，则称原称原始始问题和和对偶偶问题之之间具有具有强对偶性偶性。n凸凸优化化问题通常（但并不通常（但并不总是）是）具有具有强对偶性。偶性。nSlater定理：若凸定理：若凸优化化问题存在存在严格可行解，即存在格可行解，即存在 ，满足足则优化化问题具有具有强对偶性。偶性。该条件称条件称为Slater条件条件。109109-强对偶性存在存在 ，满足足n弱化的弱化的Slater条件：若不等式条件：若不等式约束条件的前束条件的前 个个为线性性不等式不等式约束条件，束条件，则Slater条件可以弱化条件可以弱化为：110110-Least-squares solution of linear equationsn原原问题：n对偶偶问题：n具有具有强对偶性偶性111111-Lagrange dual of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：偶函数：112112-Lagrange dual of QCQPn对偶偶问题：nSlater条件：存在条件：存在 ，满足足113113-Entropy maximizationn原始原始问题：n对偶函数：偶函数：n对偶偶问题：114114-Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足足115115-Minimum volume covering ellipsoidn原始原始问题：n对偶函数：偶函数：n对偶偶问题：116116-Minimum volume covering ellipsoidn弱化的弱化的Slater条件条件总成立，因此成立，因此该优化化问题具有具有强对偶性。偶性。n弱化的弱化的Slater条件：存在条件：存在 ，满足足117117-对偶可行解的不等式偶可行解的不等式n对于一于一优化化问题，若，若 为一可行解，一可行解，为对偶偶问题可可行解，行解，则有如下不等式：有如下不等式：为 次次优解，其中解，其中n不等式可以用于不等式可以用于对次次优解的精度估解的精度估计118118-互互补松弛条件松弛条件所以所以n设 为原始原始优化化问题的最的最优解，解，为对偶偶问题的最的最优解，若两者具有解，若两者具有强对偶性，偶性，则即即119119-KKT优化条件化条件n设优化化问题中，函数中，函数 可微。可微。设 为原始原始优化化问题的最的最优解，解，为对偶偶问题的最的最优解，且两者具有解，且两者具有强对偶性，偶性，则 满足如下条件：足如下条件：KKT条件条件为必要条件！必要条件！120120-凸凸优化化问题的的KKT条件条件可微。可微。设 满足足KKT条件，条件，则 为原始原始问题的最的最优解，而解，而 为对偶偶问题的最的最优解，且两者具有解，且两者具有强对偶偶性。性。n设原始原始问题为凸凸优化化问题中，函数中，函数121121-例例n原始凸原始凸优化化问题KKT条件条件122122-例例其中其中解得解得123123-凸凸优化化问题的的对偶求解偶求解存在唯一解存在唯一解 。若。若 为原始原始问题的可行解，的可行解，则 即即为原始原始问题的最的最优解；若解；若 不是原始不是原始问题的可行解，的可行解，则原始原始问题不存在最不存在最优解。解。n设原始原始优化化问题与与对偶偶问题具有具有强对偶性，且偶性，且 为对偶偶问题的最的最优解。解。存在唯一的最小解，即存在唯一的最小解，即124124-扰动问题n扰动问题：n当当 时即即为原始原始问题。n若若 为正，正，则第第 个不等式个不等式约束被放束被放宽；若；若 为负，则第第 个不等式个不等式约束被收束被收紧。n记 为扰动问题的最的最优解。若解。若扰动问题无最无最优解，解，则记125125-灵敏度分析灵敏度分析n设对偶偶问题存在最存在最优解，且与原始解，且与原始问题具有具有强对偶性，若非干偶性，若非干扰问题的最的最优对偶解偶解为 ，则有有n若若 在在 处可微，可微，则126126-n定定义（弱（弱选择性）：若两个不等式（等式）系性）：若两个不等式（等式）系统，至多有一个可，至多有一个可解，解，则称称这两个系两个系统具有弱具有弱选择性。性。选择定理定理n对偶不等式偶不等式组n设原始原始问题的的约束条件：束条件：n对偶偶问题n原始原始问题的的约束条件与束条件与对偶不等式偶不等式组具有弱具有弱选择性。性。127127-选择定理定理n对偶不等式偶不等式组n设原始原始问题的的严格不等式格不等式约束条件：束条件：n原始原始问题的的严格不等式格不等式约束条件与束条件与对偶不等式偶不等式组具有弱具有弱选择性。性。128128-n定定义（强选择性）：若两个不等式（等式）系性）：若两个不等式（等式）系统，恰有一个可解，恰有一个可解则称称这两个系两个系统具有具有强选择性。性。选择定理定理n对偶不等式偶不等式组n设原始原始问题为凸凸优化化问题，其，其严格不等式格不等式约束条件束条件为：n若存在若存在 ，满足足 ，则上述两上述两不等式不等式约束系束系统具有具有强选择性。性。129129-选择定理定理n对偶不等式偶不等式组n设原始原始问题为凸凸优化化问题，其不等式，其不等式约束条件束条件为：则原始原始问题的不等式的不等式约束条件与束条件与对偶不等式偶不等式组具有具有强选择性。性。n若存在若存在 ，满足足 ，且下述，且下述优化化问题存在最存在最优解解130130-罚函数的例n 范数：范数：n死区死区线性性罚函数：函数：n对数数门限限罚函数函数131131-鲁棒的罚函数n若若 大到一定程度大到一定程度时，罚函数函数为 的的线性函数，性函数，则称称该罚函数函数为鲁棒的棒的罚函数。函数。nHuber罚函数函数132132-最小范数最小范数问题n问题描述：描述：其中其中 为方程方程组 的解。的解。n可以消去等式可以消去等式约束将其束将其转换为范数逼近范数逼近问题：133133-最小范数最小范数问题n最小平方范数最小平方范数问题：范数：范数 ，最，最优解解满足：足：n最小最小罚问题：n绝对值和最小和最小问题：范数：范数 ，原，原问题可可转换为LP问题：134134-正正则逼近逼近n二元矢量二元矢量优化化问题描述：描述：n正正则化化问题：最最优解描述了两分量的一条折中曲解描述了两分量的一条折中曲线。135135-正正则逼近逼近nTikhonov正正则化化问题：为二次二次优化化问题：最最优解的形式解的形式：136136-正正则逼近逼近nTikhonov光滑正光滑正则化化问题：为二二阶差分算子：差分算子：137137-信号复原信号复原n已知加噪信号：已知加噪信号：信号复原信号复原问题的描述：的描述：函数函数 为正正则函数或光滑函数。函数或光滑函数。138138-信号复原信号复原139139-信号复原信号复原140140-信号复原信号复原141141-鲁棒逼近棒逼近n问题描述：描述：n随机随机鲁棒逼近：棒逼近：为随机随机变量，逼近量，逼近问题转换为最小最小化期望化期望n例：例：随机随机鲁棒逼近棒逼近为：转换为：142142-随机随机鲁棒逼近棒逼近n 为随机随机变量：量：最小平方随机最小平方随机鲁棒逼近棒逼近为：转换为：其中其中143143-最坏情况最坏情况鲁棒逼近棒逼近n考考虑 ，最坏情况，最坏情况鲁棒逼近棒逼近为：n例：例：随机随机鲁棒逼近棒逼近为：转换为：144144-凸凸优化理化理论与与应用用第第6 6章章 统计估估计145145-概率分布的参数估计n随机随机变量的概率密度量的概率密度为 ，其中，其中 为概率分布的概率分布的参数，且参数未知。参数估参数，且参数未知。参数估计的目的目标就是通就是通过一些已知一些已知样本估本估计获得参数的最得参数的最优近似近似值。n问题描述描述n 为样本本观测值；n 为对数似然函数；数似然函数；n若似然函数若似然函数为凹函数，凹函数，则优化化问题为凸凸优化化问题。146146-具有独立同分布噪声的线性测量n线性性测量模型：量模型：n 为观测值或或测量量值；n 为未知参数向量；未知参数向量；n 独立同分布噪声，其概率密度独立同分布噪声，其概率密度为 。n似然函数似然函数为n最大似然估最大似然估计问题为：147147-例例n高斯白噪声高斯白噪声对数似然函数：数似然函数：n区区间 上均匀分布的噪声：上均匀分布的噪声：对数似然函数：数似然函数：148148-逻辑回归n随机随机变量量 的概率分布的概率分布为：n 为参数；参数；n 为可可观测的解的解释变量；量；为观察察值。对数似然函数数似然函数：149149-假定测验n随机随机变量量 ，有，有 种可能（假定）种可能（假定）的分布；的分布；n假定假定 ：的概率分布的概率分布为n假定假定测验的目的目标：由：由观察察值猜猜测随机随机变量最有可能服从量最有可能服从哪种假定的分布。哪种假定的分布。n当当 时，称，称为二元假定二元假定测验。n随机随机检测子：非子：非负元素矩元素矩阵 150150-假定测验n 为当当 实际服从第服从第1种假定分布而猜种假定分布而猜测为第第2种假种假定分布的概率；定分布的概率；n 为当当 实际服从第服从第2种假定分布而猜种假定分布而猜测为第第1种假种假定分布的概率；定分布的概率；n多目多目标优化形式化形式：n检测概率矩概率矩阵151151-假定测验n最小最大最小最大值形式形式n尺度尺度优化形式：化形式：152152-例例n 在两种假在两种假设下的概率分布下的概率分布为：153153-例例154154-实验设计n线性性测量量问题n最大似然估最大似然估计值：n 独立同分布高斯白噪声，服从分布独立同分布高斯白噪声，服从分布 。n估估计误差差 均均值为0，方差，方差为信信赖椭圆为155155-实验设计n实验设计的目的目标：寻找找 ，使得，使得误差的方差矩差的方差矩阵最小。最小。n向量向量优化形式：化形式：n为整数整数问题，求解，求解较困困难。156156-实验设计n当当 时，令，令 近似近似为一一连续实数，原数，原问题可松弛可松弛转换为连续实数数优化：化：157157-凸凸优化理化理论与与应用用第第7 7章章 无无约束束优化化158158-无约束优化问题n问题描述：描述：n无无约束束问题求解的两种方法：求解的两种方法：n迭代逼近：迭代逼近：n求解梯度方程：求解梯度方程：n 为凸函数，且二次可微。凸函数，且二次可微。159159-例梯度方程梯度方程n二次二次优化：化：160160-迭代起始点迭代起始点n满足条件足条件2的几种函数：的几种函数：n起始点起始点 满足：足：n函数函数 任意下水平集都是任意下水平集都是闭集；集；n函数的定函数的定义域域为n当当 时，161161-强凸性n定定义：函数：函数 在在 上具有上具有强凸性，若凸性，若 满足足n若函数若函数 具有具有强凸性，凸性，则有有n 为最最优值，则162162-强凸性则有有n 为最最优值，则n若函数若函数 在在 上具有上具有强凸性，凸性，则可以可以证明存明存在在 ，满足足 163163-强凸性n对于于 ，矩，矩阵 的特征的特征值从大到小依次从大到小依次为 。则有：有：n定定义：矩：矩阵 的条件数的条件数为最大特最大特征征值与最小特征与最小特征值之比，即之比，即 。n条件数的上界：条件数的上界：164164-下降法n下降法的基本原理：下降法的基本原理：迭代迭代 ，满足足 为下降方向，下降方向，为步步长因子因子。n对于凸函数于凸函数 ，当，当 满足足 时，存在某个，存在某个 ，使得，使得 。165165-下降法n下降法的一般步下降法的一般步骤：n给出初始点出初始点 ；n循循环迭代迭代n计算下降方向算下降方向 ；n搜索步搜索步长因子因子 ；n迭代：迭代：166166-步长因子搜索n精确一精确一维搜索：搜索：n回溯一回溯一维搜索：搜索：给定参数定参数n循循环迭代迭代n初始化：令初始化：令 ；n若若 ，则终止退出；止退出；n否否则令令 167167-步长因子搜索168168-梯度下降法n算法算法简单，但收，但收敛速度速度较慢。慢。n下降方向：下降方向：n终止条件：止条件：n收收敛性：性：其中其中 。169169-收敛性分析则有：有：n设函数函数 具有具有强凸性，凸性，则存在存在 和和 ，满足：足：n若若 采用精确一采用精确一维搜索，搜索，则 ，收，收敛速度速度因子：因子：n若若 采用回溯一采用回溯一维搜索，收搜索，收敛速度因子：速度因子：n条件数越大，收条件数越大，收敛速度越小。速度越小。170170-例n当当 时，算法收，算法收敛速度速度很慢。很慢。n初始解初始解为 ，采用精确一，采用精确一维搜索；搜索；n迭代：迭代：171171-例n步步长因子采用回溯一因子采用回溯一维搜索。搜索。172172-最速下降法n归一化最速下降方向：一化最速下降方向：n非非归一化最速下降方向一化最速下降方向n欧式范数：欧式范数：n二次范数二次范数 ：n 范数：范数：173173-最速下降法174174-收敛性分析n范数界：范数界：n收收敛速度因子：速度因子：175175-牛顿法n设函数函数 二二阶可微，可微，则在在 附近，附近，的泰勒的泰勒展式展式为：n泰勒展开可作泰勒展开可作为 在在 附近的近似；附近的近似；n下降方向：下降方向：n为二次范数二次范数 上的最上的最速下降方向。速下降方向。176176-牛顿法177177-牛顿减量n令令n 为 在在 处的牛的牛顿减量。减量。n牛牛顿减量的性减量的性质1：n性性质2：牛牛顿减量可作减量可作为迭代求解的迭代求解的误差估差估计。n性性质3：牛：牛顿减量具有仿射不减量具有仿射不变性。性。178178-牛顿方法n初始化：初始化：给定初始解定初始解 以及以及nLOOP：n计算：算：n若若 则终止退出；止退出；n一一维线性搜索：性搜索：计算步算步长因子因子 ；n迭代：迭代：179179-收敛性分析n定理：假定理：假设 二二阶连续可微，具有可微，具有强凸性，即凸性，即存在存在 ，满足：足：则存在存在 ，且海森矩且海森矩阵满足足Lipschitz条件，即存在条件，即存在 ，满足：足：若若 ，则 ；若若 ，则 ，且，且180180-收敛性分析n定理：假定理：假设 二二阶连续可微，具有可微，具有强凸性，即凸性，即存在存在 ，满足：足：则存在存在 ，对于于 ，有，有且海森矩且海森矩阵满足足Lipschitz条件，即存在条件，即存在 ，满足：足：181181-例182182-凸凸优化理化理论与与应用用第第8 8章章 等式等式约束束优化化183183-等式约束优化问题n问题描述：描述：n 为凸函数，且二次凸函数，且二次连续可微，且可微，且n假假设最最优值 存在，存在，则 为最最优解当且解当且仅当存在当存在 ，满足（足（KKT条件）：条件）：184184-例KKT系系统：n二次二次优化：化：nKKT系系统可解，可解，则二次二次优化化问题存在最存在最优解。解。n系数矩系数矩阵称称为KKT矩矩阵。KKT矩矩阵非奇异当且非奇异当且仅当：当：185185-消去等式消去等式约束束n方程方程组 的解集：的解集：n 为方程方程组的一个特解，的一个特解，为 的零空的零空间范范围。n无无约束束优化形式：化形式：n若若 为最最优解，解，则有有186186-对偶偶问题n对偶形式：偶形式：187187-牛顿法n牛牛顿减量减量n 为等式等式约束束优化的可行解，化的可行解，则在在 附近原附近原问题的的二次近似二次近似为：n设 和和 分分别为该问题和和对偶偶问题的最的最优解，解，则满足：足：188188-n性性质2：牛：牛顿减量具有仿射不减量具有仿射不变性。性。牛顿减量n牛牛顿减量减量n牛牛顿减量的性减量的性质：189189-可行下降方向n可行下降方向：可行下降方向：设 满足方程足方程组 。若。若 满足方程足方程组 ，则 。称称为可行方向。若可行方向。若对于于较小的小的 ，有，有 ，则 为可行下降方向。可行下降方向。190190-等式约束的牛顿方法nLOOP：n计算算 及及 ；n若若 则终止退出；止退出；n一一维线性搜索：性搜索：计算步算步长因子因子 ；n迭代：迭代：n初始化：初始化：给定初始解定初始解 满足足 ，以及，以及191191-消去等式约束的牛顿方法n转换为等式等式约束下的牛束下的牛顿方法：方法：n初始初始值 ，第，第 次迭代次迭代值 ；n初始初始值：n迭代迭代值：192192-非可行解为初始点的牛顿法n函数函数 二二阶连续可微，因此有可微，因此有n 为等式等式约束束优化的非可行解，化的非可行解，则增量增量 应尽可尽可能使能使 满足足KKT条件，即：条件，即：n设 和和 为KKT条件的解，即有：条件的解，即有：193193-非可行解为初始点的牛顿法n则KKT条件可表示条件可表示为：n令令n设 为不不满足足KKT条件，条件，则其迭代量需其迭代量需满足：足：即即194194-n当当 且且 时，终止迭代。止迭代。非可行解为初始点的牛顿法nLOOP：n计算算 和和 ；n回溯一回溯一维线性搜索：性搜索：n迭代：迭代：n初始化：初始化：给定初始解定初始解 及及