大数据计算方法 课件 chap6-优化与凸优化

1大数据计算方法Chap6：优化问题与凸优化简介优化问题与凸集凸函数与凸优化问题凸优化问题举例-几何问题Outline2优化问题与凸集优化问题基础凸集3

优化问题基础4Costfunction

对称阵Lossfunction(损失函数)

优化变量最优解为最优值

根据代价函数对优化问题分类代价函数不同，对应优化问题求解难度也不同半正定二次函数是一种凸函数优化问题基础5代价函数是非负二次函数线性函数是半正定二次函数的特例如果把代价函数、以及可能存在的约束函数，都限定到

凸函数，通常能在可接受的时间内找到优化问题的最优解

凸集6

非凸集也称为凹集

(concaveset)凸包一定是凸集!

凸集7

Affinespace对称正定矩阵呢?是的凸集8

凸集凸集的和是凸集

affine凸函数与凸优化问题凸函数优化问题的一般形式可行集凸优化910下凸函数!凸函数

凸函数11

定义域内任意直线上的函数值也形成凸函数

切面总在下方Hessianmatrix

凸函数12例子当0a1时呢?几何解释

任何向量/矩阵范数都是凸的(convexandconcave)

凸函数13

凸函数的积是凸函数吗？

凸函数14

优化问题的一般形式15实际的优化问题往往除了代价函数，还有一些约束条件要满足例子:minimax优化问题—无穷范数度量的线性拟合引入松弛变量t,问题转化为:

是这个误差的最大值!Minimizethemaximalabsoluteerrors.t.(subjectto)优化问题的一般形式16非线性优化问题的两种一般形式一个等式约束可表示为两个不等式约束minimax优化问题:s.t.s.t.s.t.(写成上面的一般形式)可行集17可行点与可行集满足所有约束条件的点称为可行点所有可行点的集合称为约束集或可行集如果一个优化问题的可行集非空，则称该优化问题可行对于带约束优化问题,即使代价函数是凸的，其求解的难度也依赖于可行集的特点s.t.(feasiblepoint)(feasibleset)好的可行集(凸集)不太好的可行集(凹集)非常不好的可行集（不连续的凹集）凸优化18

Convex

optimizations.t.

(最大化凸函数)(可行集非凸)(在凸可行集上最小化凸代价函数的问题)

凸优化19原始的minimax优化问题代价函数为虽是凸优化,代价函数不光滑,求解有难度变换后的minimax优化问题凸优化问题线性规划问题凸优化求解器MOSEK;CVX例如：Minimax问题xs.t.使用高效的LP和凸优化求解算法Simplexmethod(单纯形法)Interior-pointmethod(内点法)凸优化20定理6.10:

凸优化问题的局部最优就是全局最优总结凸函数的判断方法根据定义一阶导数条件看Hessian矩阵的正定性(对足够光滑函数)降维判断的定理凸函数的非负线性组合最小化凸函数比非凸函数的最小化问题容易!术语小结21非线性优化问题,nonlinearoptimizationproblem代价函数,costfunction约束,constraint半正定矩阵,positivesemi-definitematrix半正定二次函数,positivesemi-definitequadraticfunction凸函数, convexfunction黑森矩阵, Hessianmatrix可行(约束)集,feasible(constraint)set凸集, convexset

-下水平集,

-sublevelset凸优化问题, convexoptimizationproblem线性规划, linearprogramming凸优化问题举例-几何问题几何优化问题求最大内切椭球22许多几何问题可转化为凸优化问题我们以求最大内切椭球的问题为例推导出它对应的凸优化问题几何问题23求最大内切椭球求最小外接椭球问题定义给定一个多面体求其内部的体积最大的椭球椭球的表示椭球内点的集合求最大内切椭球2401

坐标放缩、旋转、平移

d

x1x2

求最大内切椭球25

两个

特征值为

求最大内切椭球26

上确界

这就是优化变量须满足的约束条件最大内切椭球

求最大内切椭球27

正交变换相当于坐标轴旋转,面积不变

椭圆方程

高维情况也成立

求最大内切