凸集和凸函数和凸规划-课件.ppt

第3讲凸集 凸函数 凸规划 凸集 ConvexSet 凸函数 ConvexFunction 凸规划 ConvexProgramming 凸性 Convexity 是最优化理论必须涉及到基本概念 具有凸性的非线性规划模型是一类特殊的重要模型 它在最优化的理论证明及算法研究中具有非常重要的作用 凸集 定义 线性组合 linearCombination 仿射组合 AffineCombination 凸组合 ConvexCombination 凸锥组合 ConvexConeCombination 凸集 定义 例二维情况下 两点x1 x2的 a 线性组合为全平面 b 仿射组合为过这两点的直线 c 凸组合为连接这两点的线段 b 凸锥组合为以原点为锥顶并通过这两点的锥 凸集 定义 凸集 定义 常见的凸集 单点集 x 空集 整个欧氏空间Rn 超平面 半空间 则有 凸集 举例 凸集 性质 3 凸集 性质 凸集 性质 定义设S中任意有限个点的所有凸组合所构成的集合称为S的凸包 记为H S 即 凸集 凸包 ConvexHull 定理2 1 4H S 是Rn中所有包含S的凸集的交集 H S 是包含S的最小凸集 定义锥 凸锥 凸集 凸锥 ConvexCone 定义分离 Separation 凸集 凸集分离定理 性质定理2 1 5 凸集 凸集分离定理 定理2 1 5直观解释我们不妨把一个闭凸集想象为一个三维的充满了气体的气球 不一定为标准球形 但必须是凸的 那么 在气球外一点 到气球各点 包括内部 的距离是不一样的 但直觉告诉我们 肯定在气球上有一点 它到该点的距离是所有距离中最小的 这是凸集的特有性质 如果不是凸集 就不会这样了 比如一个平面上对称心形的图形 它不是凸的 外一点 至少可以找到2点 使其到外面那一点的距离最小 凸集 凸集分离定理 凸集分离定理定理2 1 6 凸集 凸集分离定理 点与闭凸集的分离定理 凸集分离定理应用 Farkas引理定理2 1 7 凸集 凸集分离定理应用 Farkas引理在我们即将学习的最优性条件中是重要的基础 Farkas引理 几何解释 设A的第i个行向量为ai i 1 2 m 则 2 1 4 式有解当且仅当凸锥 x Ax 0 与半空间 x bTx 0 的交不空 即 2 1 4 式有解当且仅当存在向量x 它与各ai的夹角钝角或直角 而与b的夹角为锐角 2 1 5 式有解当且仅当b在由a1 a2 am所生成的凸锥内 凸集 凸集分离定理应用 凸集分离定理应用 Gordan定理定理2 1 8 凸集 凸集分离定理应用 利用Farkas引理可推导下述的Gordan定理和择一性定理 凸集分离定理应用 择一性定理定理2 1 9 凸函数 凸函数 ConvexFunction 定义2 4 凸函数 严格凸函数 设 是非空凸集 若对任意的 及任意的 都有 则称函数 为 上的严格凸函数 注 将上述定义中的不等式反向 可以得到严格凹函数的定义 凸函数 几何性质 f X X f X1 f X2 X1 X2 f X X f X1 f X2 X1 X2 x1 1 x2 f x1 1 x2 f X X f x1 1 f x2 f X1 f X2 X1 X2 x1 1 x2 f x1 1 x2 f X X f X1 f X2 X1 X2 任意两点的函数值的连线上的点都在曲线的上方 x1 1 x2 f x1 1 x2 f x1 1 f x2 例4 2 1 a 凸函数 b 凹函数 该定义的一个应用 证明不等式例 证明 Young不等式 推广 H lder不等式 P412 37 证法 在Young不等式中令 凸函数 凸函数 凸函数 性质 詹生 Jensen 不等式 P412 36 凸函数 定理2 性质 正线性组合 凸函数 定理3 水平集 LevelSet 称为函数f在集合S上关于数的水平集 注 定理3的逆命题不成立 凸函数 凸函数 凸函数 凸函数的判别定理 凸函数 严格凸函数 充要条件 凸函数 凸函数的判别定理 一阶条件 注 定理4提供了一个判别可微函数是否为凸函数的依据 凸函数 定理4 几何解释 一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方 凸函数 定理4 几何解释 一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方 凸函数 凸函数的判别定理 二阶条件 例 凸函数 凸函数的判别定理 二阶条件 例 凸函数 凸函数的判别定理 二阶条件 凸规划 凸规划 ConvexProgramming 例 凸规划 凸规划 例 凸规划 定理2 4 凸规划的基本性质 定理凸规划的任一局部最优解都是它的整体最优解 证明 设x 是凸规划的一个局部解 则存在 0 使 如果x 不是整体最优解 则又因为f是凸函数 所以 取 0充分小 有 例如下非线性规划是否为凸规划 正定 凸函数 所以 该问题为凸规划 半正定 凸函数 半正定 凸函数 如图所示 该问题最优解 最小