凸优化理论与应用.ppt

信息与通信工程学院庄伯金bjzhuang 1 凸优化理论与应用 庄伯金bjzhuang 信息与通信工程学院庄伯金bjzhuang 2 优化理论概述 什么是优化问题 objectivefunction constraintfunctions 信息与通信工程学院庄伯金bjzhuang 3 几类经典的优化问题 线性规划问题 最小二乘问题 凸优化问题 凸优化问题理论上有有效的方法进行求解 信息与通信工程学院庄伯金bjzhuang 4 本课程的主要内容 理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法 信息与通信工程学院庄伯金bjzhuang 5 熟悉了解凸优化理论的基本原理和基本方法 掌握实际问题转化为凸优化问题的基本方法 掌握最优化问题的经典算法 课程要求 信息与通信工程学院庄伯金bjzhuang 6 参考书目 stephenboydandlievenvandenberghe convexoptimization cambridgeuniversitypress 袁亚湘 孙文瑜 最优化理论与方法 科学出版社 1999 信息与通信工程学院庄伯金bjzhuang 7 凸优化理论与应用 第一章凸集 信息与通信工程学院庄伯金bjzhuang 8 仿射集 affinesets 直线的表示 线段的表示 信息与通信工程学院庄伯金bjzhuang 9 仿射集 affinesets 仿射集的定义 过集合c内任意两点的直线均在集合c内 则称集合c为仿射集 仿射集的例 直线 平面 超平面 信息与通信工程学院庄伯金bjzhuang 10 仿射集 仿射包 包含集合c的最小的仿射集 仿射维数 仿射包的维数 信息与通信工程学院庄伯金bjzhuang 11 仿射集 内点 interior 相对内点 relativeinterior 信息与通信工程学院庄伯金bjzhuang 12 凸集 convexsets 凸集的定义 集合c内任意两点间的线段均在集合c内 则称集合c为凸集 信息与通信工程学院庄伯金bjzhuang 13 凸集 凸包的定义 包含集合c的最小的凸集 信息与通信工程学院庄伯金bjzhuang 14 锥 cones 锥的定义 凸锥的定义 集合c既是凸集又是锥 锥包的定义 集合c内点的所有锥组合 信息与通信工程学院庄伯金bjzhuang 15 超平面和半空间 超平面 hyperplane 半空间 halfspace 信息与通信工程学院庄伯金bjzhuang 16 欧氏球和椭球 欧氏球 euclideanball 椭球 ellipsoid 信息与通信工程学院庄伯金bjzhuang 17 范数球和范数锥 范数 norm 范数球 normball 范数锥 normcone 信息与通信工程学院庄伯金bjzhuang 18 多面体 polyhedra 多面体 单纯形 simplex 信息与通信工程学院庄伯金bjzhuang 19 半正定锥 positivesemidefinitecone n阶对称矩阵集 n阶半正定矩阵集 n阶正定矩阵集 n阶半正定矩阵集为凸锥 信息与通信工程学院庄伯金bjzhuang 20 保持凸性的运算 集合交运算仿射变换透视 投射函数 perspectivefunction 信息与通信工程学院庄伯金bjzhuang 21 保持凸性的运算 线性分式函数 linear fractionalfunction 信息与通信工程学院庄伯金bjzhuang 22 真锥 propercone 真锥的定义 锥满足如下条件 k具有内点 k内不含直线 信息与通信工程学院庄伯金bjzhuang 23 广义不等式 真锥下的偏序关系 例 逐项不等式矩阵不等式 广义不等式 严格广义不等式 信息与通信工程学院庄伯金bjzhuang 24 广义不等式的性质 信息与通信工程学院庄伯金bjzhuang 25 严格广义不等式的性质 信息与通信工程学院庄伯金bjzhuang 26 最值和极值 最小元的定义 设 对 都有成立 则称为的最小元 极小元的定义 设 对于 若 则成立 则称为的极小元 信息与通信工程学院庄伯金bjzhuang 27 分割超平面 separatinghyperplane 定理 设和为两不相交凸集 则存在超平面将和分离 即 信息与通信工程学院庄伯金bjzhuang 28 支撑超平面 supportinghyperplane 定义 设集合 为边界上的点 若存在 满足对任意 都有成立 则称超平面为集合在点处的支撑超平面 定理 凸集边界上任意一点均存在支撑超平面 定理 若一个闭的非中空集合 在边界上的任意一点存在支撑超平面 则该集合为凸集 信息与通信工程学院庄伯金bjzhuang 29 对偶锥 dualcone 对偶锥的定义 设为锥 则集合称为对偶锥 对偶锥的性质 真锥的对偶锥仍然是真锥 信息与通信工程学院庄伯金bjzhuang 30 对偶广义不等式 广义不等式与对偶等价性质 最小元的对偶特性 信息与通信工程学院庄伯金bjzhuang 31 对偶广义不等式 极小元的对偶特性 反过来不一定成立 信息与通信工程学院庄伯金bjzhuang 32 作业 p602 8p602 10p602 14p622 16p622 18p642 30p642 31p642 33 信息与通信工程学院庄伯金bjzhuang 33 凸优化理论与应用 第二章凸函数 信息与通信工程学院庄伯金bjzhuang 34 凸函数的定义 1 定义域为凸集 2 有 凸函数的定义 函数 满足 凸函数的扩展定义 若为凸函数 则可定义其扩展函数为 凸函数的扩展函数也是凸函数 信息与通信工程学院庄伯金bjzhuang 35 凸函数的一阶微分条件 若函数的定义域为开集 且函数一阶可微 则函数为凸函数当且仅当为凸集 且对 信息与通信工程学院庄伯金bjzhuang 36 凸函数的二阶微分条件 若函数的定义域为开集 且函数二阶可微 则函数为凸函数当且仅当为凸集 且对 其hessian矩阵 信息与通信工程学院庄伯金bjzhuang 37 凸函数的例 幂函数 负对数函数 负熵函数 范数函数 指数函数 信息与通信工程学院庄伯金bjzhuang 38 凸函数的例 信息与通信工程学院庄伯金bjzhuang 39 下水平集 sublevelset 定理 凸函数的任一下水平集均为凸集 任一下水平集均为凸集的函数不一定为凸函数 信息与通信工程学院庄伯金bjzhuang 40 函数上半图 epigraph 定理 函数为凸函数当且仅当的上半图为凸集 信息与通信工程学院庄伯金bjzhuang 41 jensen不等式 为凸函数 则有 jensen不等式的另外形式 信息与通信工程学院庄伯金bjzhuang 42 保持函数凸性的算子 凸函数的逐点最大值 凸函数与仿射变换的复合 凸函数的非负加权和 信息与通信工程学院庄伯金bjzhuang 43 保持函数凸性的算子 复合运算 最小值算子 凸函数的透视算子 信息与通信工程学院庄伯金bjzhuang 44 共轭函数 conjugatefunction 定义 设函数 其共轭函数 定义为 共轭函数的例 共轭函数具有凸性 信息与通信工程学院庄伯金bjzhuang 45 共轭函数的性质 fenchel sinequality 性质 若为凸函数 且的上半图是闭集 则有 信息与通信工程学院庄伯金bjzhuang 46 准凸函数 quasiconvexfunction 准凸函数的例 信息与通信工程学院庄伯金bjzhuang 47 准凸函数的判定定理 定理 函数为准凸函数 当且仅当为凸集 且对 有 定理 若函数一阶可微 则为准凸函数 当且仅当为凸集 且对 有 信息与通信工程学院庄伯金bjzhuang 48 最小值函数 非负权值函数的最大值函数 保持准凸性的算子 复合函数 信息与通信工程学院庄伯金bjzhuang 49 准凸函数的凸函数族表示 若为准凸函数 根据的任意下水平集 我们可以构造一个凸函数族 使得 性质 若为准凸函数的凸函数族表示 对每一个 若 则有 信息与通信工程学院庄伯金bjzhuang 50 对数凸函数 对数凸函数的例 信息与通信工程学院庄伯金bjzhuang 51 对数凸函数和凹函数的性质 性质 对数凸性与凹性对函数乘积和正数数乘运算均保持封闭 定理 函数二阶可微 则为对数凸函数当且仅当 性质 对数凸性对函数加运算保持封闭 但对数凹性对函数加运算不封闭 推论 函数对每一个在上对数凸 则函数也是对数凸函数 信息与通信工程学院庄伯金bjzhuang 52 对数凸函数和凹函数的性质 定理 函数为对数凹函数 则函数是对数凹函数 信息与通信工程学院庄伯金bjzhuang 53 广义不等式下的凸性 广义单调性的定义 设为真锥 函数称为单调增 若函数满足 定理 对偶等价 函数为凸函数 当且仅当对所有 为凸函数 信息与通信工程学院庄伯金bjzhuang 54 作业 1 p1163 16p1163 21 信息与通信工程学院庄伯金bjzhuang 55 作业 2 p1213 41p1223 49 1 2 信息与通信工程学院庄伯金bjzhuang 56 凸优化理论与应用 第三章凸优化 信息与通信工程学院庄伯金bjzhuang 57 优化问题的基本形式 优化问题的基本描述 优化变量 不等式约束 等式约束 无约束优化 信息与通信工程学院庄伯金bjzhuang 58 优化问题的基本形式 最优化值 最优化解 优化问题的域 可行点 解 feasible 满足约束条件 可行域 可解集 所有可行点的集合 信息与通信工程学院庄伯金bjzhuang 59 局部最优问题 局部最优问题 信息与通信工程学院庄伯金bjzhuang 60 优化问题的等价形式 1 信息与通信工程学院庄伯金bjzhuang 61 优化问题的等价形式 2 信息与通信工程学院庄伯金bjzhuang 62 优化问题的等价形式 3 定理 设为严格单调增函数 满足当且仅当 满足当且仅当 则原优化问题与以下优化问题等价 信息与通信工程学院庄伯金bjzhuang 63 优化问题的等价形式 4 定理 原优化问题与以下优化问题等价 称为松弛变量 信息与通信工程学院庄伯金bjzhuang 64 优化问题的等价形式 5 定理 设满足等式成立 当且仅当 则原优化问题与以下优化问题等价 信息与通信工程学院庄伯金bjzhuang 65 可分离变量优化问题 信息与通信工程学院庄伯金bjzhuang 66 优化问题的上半图形式 信息与通信工程学院庄伯金bjzhuang 67 凸优化问题的基本形式 凸优化问题的基本描述 为仿射函数 为凸函数 若为准凸函数 则优化问题称为准凸优化问题 性质 凸优化问题的可行域是凸集 信息与通信工程学院庄伯金bjzhuang 68 凸优化问题的例 例 等价于凸优化问题 信息与通信工程学院庄伯金bjzhuang 69 凸优化问题的局部最优解 定理 凸优化问题的局部最优解均是全局最优解 信息与通信工程学院庄伯金bjzhuang 70 凸优化问题最优解的微分条件 定理 设为凸优化问题的可行域 可微 则为最优解当且仅当成立 定理 非约束凸优化问题中 若可微 则为最优解当且仅当成立 信息与通信工程学院庄伯金bjzhuang 71 凸优化问题的等价形式 信息与通信工程学院庄伯金bjzhuang 72 凸优化问题的等价形式 信息与通信工程学院庄伯金bjzhuang 73 凸优化问题的等价形式 信息与通信工程学院庄伯金bjzhuang 74 凸优化问题的等价形式 等价于 定理 设凸优化问题 信息与通信工程学院庄伯金bjzhuang 75 准凸优化问题 注 准凸优化问题的局部最优解不一定是全局最优解 信息与通信工程学院庄伯金bjzhuang 76 准凸优化问题的上半图形式 设为准凸函数的凸函数族表示 即 则准凸优化问题的可行解问题为 设为准凸优化问题的最优解 若上述问题可解 则 否则 信息与通信工程学院庄伯金bjzhuang 77 准凸优化问题二分法求解 给定一个足够小的和足够大的 使得区间能包含最优解 给定 loop 令求解可行解问题 若可解 则令 否则令若 则结束 否则gotoloop 信息与通信工程学院庄伯金bjzhuang 78 线性规划 linearprogram lp lp问题的一般描述 信息与通信工程学院庄伯金bjzhuang 79 lp问题的几种类型 标准lp问题 不等式形式lp问题 信息与通信工程学院庄伯金bjzhuang 80 标准lp问题的转换 信息与通信工程学院庄伯金bjzhuang 81 lp问题的例 chebyshevcenterofapolyhedron piecewise linearminimization linear fractionalprogramming 信息与通信工程学院庄伯金bjzhuang 82 chebyshevcenterofapolyhedron 多面体 chebyshevcenter 到多面体边界距离最大的内点 最深的点 问题描述 lp形式 信息与通信工程学院庄伯金bjzhuang 83 piecewise linearminimization 问题描述 上半图形式 lp形式 信息与通信工程学院庄伯金bjzhuang 84 linear fractionalprogramming 问题描述 lp形式 信息与通信工程学院庄伯金bjzhuang 85 二次规划 quadraticprogram qp qp问题的基本描述 信息与通信工程学院庄伯金bjzhuang 86 二次约束二次规划 quadraticallyconstrainedquadraticprogram qcqp 信息与通信工程学院庄伯金bjzhuang 87 qp问题的例 least squaresandregression distancebetweenpolyhedra 信息与通信工程学院庄伯金bjzhuang 88 least squaresandregression 问题描述 信息与通信工程学院庄伯金bjzhuang 89 distancebetweenpolyhedra 问题描述 qp形式 信息与通信工程学院庄伯金bjzhuang 90 second orderconeprogram socp socp问题的基本描述 二次锥约束条件 信息与通信工程学院庄伯金bjzhuang 91 socp问题的例 robustlinearprogramming 例 为确定的常数 为变量 其范围满足 socp形式 信息与通信工程学院庄伯金bjzhuang 92 几何规划 geometricprogramming 单项式与多项式 几何规划的基本描述 信息与通信工程学院庄伯金bjzhuang 93 几何规划的凸形式转换 令 几何规划的凸形式 信息与通信工程学院庄伯金bjzhuang 94 广义不等式约束 广义不等式约束的优化问题 socp的描述 信息与通信工程学院庄伯金bjzhuang 95 凸优化理论与应用 第四章对偶问题 信息与通信工程学院庄伯金bjzhuang 96 优化问题的拉格朗日函数 设优化问题 拉格朗日 lagrangian 函数 对固定的 拉格朗日函数为关于和的仿射函数 信息与通信工程学院庄伯金bjzhuang 97 拉格朗日对偶函数 拉格朗日对偶函数 lagrangedualfunction 若拉格朗日函数没有下界 则令 拉格朗日对偶函数为凹函数 对和 若原最优化问题有最优值 则 信息与通信工程学院庄伯金bjzhuang 98 对偶函数的例 least squaressolutionoflinearequations standardformlp two waypartitioningproblem 信息与通信工程学院庄伯金bjzhuang 99 least squaressolutionoflinearequations 原问题 拉格朗日函数 拉格朗日对偶函数 信息与通信工程学院庄伯金bjzhuang 100 standardformlp 原问题 拉格朗日函数 拉格朗日对偶函数 信息与通信工程学院庄伯金bjzhuang 101 two waypartitioningproblem 原问题 拉格朗日函数 拉格朗日对偶函数 信息与通信工程学院庄伯金bjzhuang 102 对偶函数与共轭函数 共轭函数 共轭函数与对偶函数存在密切联系 具有线性不等式约束和线性等式约束的优化问题 对偶函数 信息与通信工程学院庄伯金bjzhuang 103 equalityconstrainednormminimization 问题描述 共轭函数 对偶函数 信息与通信工程学院庄伯金bjzhuang 104 entropymaximization 原始问题 共轭函数 对偶函数 信息与通信工程学院庄伯金bjzhuang 105 minimumvolumecoveringellipsoid 原始问题 对偶函数 共轭函数 信息与通信工程学院庄伯金bjzhuang 106 拉格朗日对偶问题 拉格朗日对偶问题的描述 对偶可行域 最优值 最优解 信息与通信工程学院庄伯金bjzhuang 107 lp问题的对偶问题 标准lp问题 对偶函数 对偶问题 等价描述 信息与通信工程学院庄伯金bjzhuang 108 弱对偶性 定理 弱对偶性 设原始问题的最优值为 对偶问题的最优值为 则成立 optimaldualitygap 可以利用对偶问题找到原始问题最优解的下界 信息与通信工程学院庄伯金bjzhuang 109 强对偶性 强对偶性并不是总是成立的 定义 强对偶性 设原始问题的最优值为 对偶问题的最优值为 若成立 则称原始问题和对偶问题之间具有强对偶性 凸优化问题通常 但并不总是 具有强对偶性 信息与通信工程学院庄伯金bjzhuang 110 强对偶性 存在 满足 弱化的slater条件 若不等式约束条件的前个为线性不等式约束条件 则slater条件可以弱化为 信息与通信工程学院庄伯金bjzhuang 111 least squaressolutionoflinearequations 原问题 对偶问题 具有强对偶性 信息与通信工程学院庄伯金bjzhuang 112 lagrangedualofqcqp qcqp 拉格朗日函数 对偶函数 信息与通信工程学院庄伯金bjzhuang 113 lagrangedualofqcqp 对偶问题 slater条件 存在 满足 信息与通信工程学院庄伯金bjzhuang 114 entropymaximization 原始问题 对偶函数 对偶问题 信息与通信工程学院庄伯金bjzhuang 115 entropymaximization 弱化的slater条件 存在 满足 信息与通信工程学院庄伯金bjzhuang 116 minimumvolumecoveringellipsoid 原始问题 对偶函数 对偶问题 信息与通信工程学院庄伯金bjzhuang 117 minimumvolumecoveringellipsoid 弱化的slater条件总成立 因此该优化问题具有强对偶性 弱化的slater条件 存在 满足 信息与通信工程学院庄伯金bjzhuang 118 对偶可行解的不等式 对于一优化问题 若为一可行解 为对偶问题可行解 则有如下不等式 为次优解 其中 不等式可以用于对次优解的精度估计 信息与通信工程学院庄伯金bjzhuang 119 互补松弛条件 所以 设为原始优化问题的最优解 为对偶问题的最优解 若两者具有强对偶性 则 即 信息与通信工程学院庄伯金bjzhuang 120 kkt优化条件 设优化问题中 函数可微 设为原始优化问题的最优解 为对偶问题的最优解 且两者具有强对偶性 则满足如下条件 kkt条件为必要条件 信息与通信工程学院庄伯金bjzhuang 121 凸优化问题的kkt条件 信息与通信工程学院庄伯金bjzhuang 122 例 原始凸优化问题 kkt条件 信息与通信工程学院庄伯金bjzhuang 123 例 其中 解得 信息与通信工程学院庄伯金bjzhuang 124 凸优化问题的对偶求解 信息与通信工程学院庄伯金bjzhuang 125 扰动问题 扰动问题 当时即为原始问题 若为正 则第个不等式约束被放宽 若为负 则第个不等式约束被收紧 记为扰动问题的最优解 若扰动问题无最优解 则记 信息与通信工程学院庄伯金bjzhuang 126 灵敏度分析 设对偶问题存在最优解 且与原始问题具有强对偶性 若非干扰问题的最优对偶解为 则有 若在处可微 则 信息与通信工程学院庄伯金bjzhuang 127 定义 弱选择性 若两个不等式 等式 系统 至多有一个可解 则称这两个系统具有弱选择性 选择定理 对偶不等式组 设原始问题的约束条件 对偶问题 原始问题的约束条件与对偶不等式组具有弱选择性 信息与通信工程学院庄伯金bjzhuang 128 选择定理 对偶不等式组 设原始问题的严格不等式约束条件 原始问题的严格不等式约束条件与对偶不等式组具有弱选择性 信息与通信工程学院庄伯金bjzhuang 129 定义 强选择性 若两个不等式 等式 系统 恰有一个可解 则称这两个系统具有强选择性 选择定理 对偶不等式组 设原始问题为凸优化问题 其严格不等式约束条件为 若存在 满足 则上述两不等式约束系统具有强选择性 信息与通信工程学院庄伯金bjzhuang 130 选择定理 对偶不等式组 设原始问题为凸优化问题 其不等式约束条件为 信息与通信工程学院庄伯金bjzhuang 131 罚函数的例 范数 死区线性罚函数 对数门限罚函数 信息与通信工程学院庄伯金bjzhuang 132 鲁棒的罚函数 若大到一定程度时 罚函数为的线性函数 则称该罚函数为鲁棒的罚函数 huber罚函数 信息与通信工程学院庄伯金bjzhuang 133 最小范数问题 问题描述 其中为方程组的解 可以消去等式约束将其转换为范数逼近问题 信息与通信工程学院庄伯金bjzhuang 134 最小范数问题 最小平方范数问题 范数 最优解满足 最小罚问题 绝对值和最小问题 范数 原问题可转换为lp问题 信息与通信工程学院庄伯金bjzhuang 135 正则逼近 二元矢量优化问题描述 正则化问题 最优解描述了两分量的一条折中曲线 信息与通信工程学院庄伯金bjzhuang 136 正则逼近 tikhonov正则化问题 为二次优化问题 最优解的形式 信息与通信工程学院庄伯金bjzhuang 137 正则逼近 tikhonov光滑正则化问题 为二阶差分算子 信息与通信工程学院庄伯金bjzhuang 138 信号复原 已知加噪信号 信号复原问题的描述 函数为正则函数或光滑函数 信息与通信工程学院庄伯金bjzhuang 139 信号复原 信息与通信工程学院庄伯金bjzhuang 140 信号复原 信息与通信工程学院庄伯金bjzhuang 141 信号复原 信息与通信工程学院庄伯金bjzhuang 142 鲁棒逼近 问题描述 随机鲁棒逼近 为随机变量 逼近问题转换为最小化期望 例 随机鲁棒逼近为 转换为 信息与通信工程学院庄伯金bjzhuang 143 随机鲁棒逼近 为随机变量 最小平方随机鲁棒逼近为 转换为 其中 信息与通信工程学院庄伯金bjzhuang 144 最坏情况鲁棒逼近 考虑 最坏情况鲁棒逼近为 例 随机鲁棒逼近为 转换为 信息与通信工程学院庄伯金bjzhuang 145 凸优化理论与应用 第6章统计估计 信息与通信工程学院庄伯金bjzhuang 146 概率分布的参数估计 随机变量的概率密度为 其中为概率分布的参数 且参数未知 参数估计的目标就是通过一些已知样本估计获得参数的最优近似值 问题描述 为样本观测值 为对数似然函数 若似然函数为凹函数 则优化问题为凸优化问题 信息与通信工程学院庄伯金bjzhuang 147 具有独立同分布噪声的线性测量 线性测量模型 为观测值或测量值 为未知参数向量 独立同分布噪声 其概率密度为 似然函数为 最大似然估计问题为 信息与通信工程学院庄伯金bjzhuang 148 例 高斯白噪声 对数似然函数 区间上均匀分布的噪声 对数似然函数 信息与通信工程学院庄伯金bjzhuang 149 逻辑回归 随机变量的概率分布为 为参数 为可观测的解释变量 为观察值 对数似然函数 信息与通信工程学院庄伯金bjzhuang 150 假定测验 随机变量 有种可能 假定 的分布 假定 的概率分布为 假定测验的目标 由观察值猜测随机变量最有可能服从哪种假定的分布 当时 称为二元假定测验 随机检测子 非负元素矩阵 信息与通信工程学院庄伯金bjzhuang 151 假定测验 为当实际服从第1种假定分布而猜测为第2种假定分布的概率 为当实际服从第2种假定分布而猜测为第1种假定分布的概率 多目标优化形式 检测概率矩阵 信息与通信工程学院庄伯金bjzhuang 152 假定测验 最小最大值形式 尺度优化形式 信息与通信工程学院庄伯金bjzhuang 153 例 在两种假设下的概率分布为 信息与通信工程学院庄伯金bjzhuang 154 例 信息与通信工程学院庄伯金bjzhuang 155 实验设计 线性测量问题 最大似然估计值 独立同分布高斯白噪声 服从分布 估计误差均值为0 方差为 信赖椭圆为 信息与通信工程学院庄伯金bjzhuang 156 实验设计 实验设计的目标 寻找 使得误差的方差矩阵最小 向量优化形式 为整数问题 求解较困难 信息与通信工程学院庄伯金bjzhuang 157 实验设计 当时 令近似为一连续实数 原问题可松弛转换为连续实数优化 信息与通信工程学院庄伯金bjzhuang 158 凸优化理论与应用 第7章无约束优化 信息与通信工程学院庄伯金bjzhuang 159 无约束优化问题 问题描述 无约束问题求解的两种方法 迭代逼近 求解梯度方程 为凸函数 且二次可微 信息与通信工程学院庄伯金bjzhuang 160 例 梯度方程 二次优化 信息与通信工程学院庄伯金bjzhuang 161 迭代起始点 满足条件2的几种函数 起始点满足 函数任意下水平集都是闭集 函数的定义域为 当时 信息与通信工程学院庄伯金bjzhuang 162 强凸性 定义 函数在上具有强凸性 若满足 若函数具有强凸性 则有 为最优值 则 信息与通信工程学院庄伯金bjzhuang 163 强凸性 则有 为最优值 则 若函数在上具有强凸性 则可以证明存在 满足 信息与通信工程学院庄伯金bjzhuang 164 强凸性 对于 矩阵的特征值从大到小依次为 则有 定义 矩阵的条件数为最大特征值与最小特征值之比 即 条件数的上界 信息与通信工程学院庄伯金bjzhuang 165 下降法 对于凸函数 当满足时 存在某个 使得 信息与通信工程学院庄伯金bjzhuang 166 下降法 下降法的一般步骤 给出初始点 信息与通信工程学院庄伯金bjzhuang 167 步长因子搜索 精确一维搜索 信息与通信工程学院庄伯金bjzhuang 168 步长因子搜索 信息与通信工程学院庄伯金bjzhuang 169 梯度下降法 算法简单 但收敛速度较慢 下降方向 终止条件 信息与通信工程学院庄伯金bjzhuang 170 收敛性分析 若采用精确一维搜索 则 收敛速度因子 若采用回溯一维搜索 收敛速度因子 条件数越大 收敛速度越小 信息与通信工程学院庄伯金bjzhuang 171 例 当时 算法收敛速度很慢 初始解为 采用精确一维搜索 迭代 信息与通信工程学院庄伯金bjzhuang 172 例 步长因子采用回溯一维搜索 信息与通信工程学院庄伯金bjzhuang 173 最速下降法 归一化最速下降方向 非归一化最速下降方向 欧式范数 二次范数 范数 信息与通信工程学院庄伯金bjzhuang 174 最速下降法 信息与通信工程学院庄伯金bjzhuang 175 收敛性分析 范数界 收敛速度因子 信息与通信工程学院庄伯金bjzhuang 176 牛顿法 设函数二阶可微 则在附近 的泰勒展式为 泰勒展开可作为在附近的近似 下降方向 为二次范数上的最速下降方向 信息与通信工程学院庄伯金bjzhuang 177 牛顿法 信息与通信工程学院庄伯金bjzhuang 178 牛顿减量 令 为在处的牛顿减量 牛顿减量的性质1 性质2 牛顿减量可作为迭代求解的误差估计 性质3 牛顿减量具有仿射不变性 信息与通信工程学院庄伯金bjzhuang 179 牛顿方法 初始化 给定初始解以及 loop 计算 若则终止退出 一维线性搜索 计算步长因子 迭代 信息与通信工程学院庄伯金bjzhuang 180 收敛性分析 定理 假设二阶连续可微 具有强凸性 即存在 满足 则存在 且海森矩阵满足lipschitz条件 即存在 满足 若 则 若 则 且 信息与通信工程学院庄伯金bjzhuang 181 收敛性分析 定理 假设二阶连续可微 具有强凸性 即存在 满足 则存在 对于 有 且海森矩阵满足lipschitz条件 即存在 满足 信息与通信工程学院庄伯金bjzhuang 182 例 信息与通信工程学院庄伯金bjzhuang 183 凸优化理论与应用 第8章等式约束优化 信息与通信工程学院庄伯金bjzhuang 184 等式约束优化问题 问题描述 为凸函数 且二次连续可微 且 假设最优值存在 则为最优解当且仅当存在 满足 kkt条件 信息与通信工程学院庄伯金bjzhuang 185 例 kkt系统 二次优化 kkt系统可解 则二次优化问题存在最优解 系数矩阵称为kkt矩阵 kkt矩阵非奇异当且仅当 信息与通信工程学院庄伯金bjzhuang 186 消去等式约束 方程组的解集 为方程组的一个特解 为的零空间范围 无约束优化形式 若为最优解 则有 信息与通信工程学院庄伯金bjzhuang 187 对偶问题 对偶形式 信息与通信工程学院庄伯金bjzhuang 188 牛顿法 牛顿减量 为等式约束优化的可行解 则在附近原问题的二次近似为 设和分别为该问题和对偶问题的最优解 则满足 信息与通信工程学院庄伯金bjzhuang 189 性质2 牛顿减量具有仿射不变性 牛顿减量 牛顿减量 牛顿减量的性质 信息与通信工程学院庄伯金bjzhuang 190 可行下降方向 可行下降方向 设满足方程组 若满足方程组 则 称为可行方向 若对于较小的 有 则为可行下降方向 信息与通信工程学院庄伯金bjzhuang 191 等式约束的牛顿方法 loop 计算及 若则终止退出 一维线性搜索 计算步长因子 迭代 初始化 给定初始解满足 以及 信息与通信工程学院庄伯金bjzhuang 192 消去等式约束的牛顿方法 转换为等式约束下的牛顿方法 初始值 第次迭代值 初始值 迭代值 信息与通信工程学院庄伯金bjzhuang 193 非可行解为初始点的牛顿法 函数二阶连续可微 因此有 为等式约束优化的非可行解 则增量应尽可能使满足kkt条件 即 设和为kkt条件的解 即有 信息与通信工程学院庄伯金bjzhuang 194 非可行解为初始点的牛顿法 则kkt条件可表示为 令 设为不满足kkt条件 则其迭代量需满足 即 信息与通信工程学院庄伯金bjzhuang 195 当且时 终止迭代 非可行解为初始点的牛顿法 loop 计算和 回溯一维线性搜索 迭代 初始化 给定初始解及 以及 令 while 信息与通信工程学院庄伯金bjzhuang 196 其中 且满足 kkt系统的求解 1 分解 2 若非奇异 则可消元 3 若奇异 则kkt系统可改写为 kkt系统 信息与通信工程学院庄伯金bjzhuang 197 凸优化理论与应用 第9章内点法 信息与通信工程学院庄伯金bjzhuang 198 则优化问