月机器学习-3.凸优化

历史遗留无偏均方误差准6月机器学习 无偏性 利用已知样本X1,X2,Xn能够得到参数的一个估计 ˆ，因此，ˆ可以写成 X2,Xn 于不同的样本，ˆ的值一般不同。因此，可 如果E 6月机器学习 举

2X1 1n1ˆ

n 6月机器学习 样本均值和方差是总体的无偏估 in ni则： i

1 1i

X6月机器学习 均值的无nnnniE E1 1 i

1 n

i6月机器学习 方差的无1

n 1

Var

Xini

2Var i1

nninnn 2 n Var

E n

X nn2 nn2ii i

2

nXE EX Xi

2n n6月机器学习 2用估计量 ˆ去估计θ，其误差是ˆ X1,X2,Xn而定，因此，ˆ

2显然， ˆ是无偏估计，则MSE即方差 V6月机器学习 凸优6月机器学习 思考两个不等 xT yTQ1y 2xT6月机器学习 思考凸集凸函数图像的上方区域，一定是凸集稍后给出上述表述的形式 6月机器学习 (超)几何体的向量表直x=θa+(1-θ)b,线x=θa+(1-θ)b,一般的，f(x,y)=0表示定义域在R2的曲特殊的，y=g(x)表示定义域在R的曲线，f(x,y)=y-一般的，f(x,y,z)=0表示定义域在R3的曲特殊的，z=h(x,y)表示定义域在R2的曲面，f(x,y,z)=z-记x=(u1,u2,…un)，则f(x)=0表示定义域在Rn的超曲面不特殊说明，后面将使用x1表示向量，如：定义两个点则x=θx1+(1-θ)x2,θ∈R表示经过这两点的直6月机器学习 仿射集(Affine集合C x1, C,则 C仿射集的例子：直线 6月机器学习 仿射仿 三角形的仿射维数为线段的仿射维数为球的仿射维数为6月机器学习 内点和相对内些点在“边界”上，哪些点在？对于集合中的某个点r的球B(>)BC()推广：求集合的仿射包A，对于集合为中心做半径rB(r>小)，若球和A的交集完全落在的 (：是)则。用relintC表示C的相对内点relint aff 6月机器学习 举6月机器学习 凸6月机器学习 仿射集和凸集的关6月机器学习 凸6月机器学习 凸6月机器学习 凸包的例6月机器学习 锥6月机器学习 6月机器学习 锥6月机器学习 思半正定阵的定6月机器学习 超平面和半空6月机器学习 超平面和半空6月机器学习 欧式球和6月机器学习 范数球和范数锥(欧式空间的推广6月机器学习 R3空间中的二阶6月机器学习 多面多面体有限个半空间和超平面的仿射集(如超平面、直线)多面体是凸此外：有界的多面体有时称作多胞形(polytope) 6月机器学习 多面6月机器学习 保持凸性的运思考：如何证明？(提示：根据定义6月机器学习 集合交运算：半空间的6月机器学习 仿射变伸缩、平移、投若f若S为凸集，则f(S)为凸若f(S)为凸集，则S为凸6月机器学习 进一步分析仿射变两个凸集 6月机器学习 变 小孔成6月机器学习 变换凸集 6月机器学习 投射函数(线性分式函数投射函数 g6月机器学习 1

fx1,

，dom x投射的作

6月机器学习 分割超平“和不相交”6月机器学习 分割超平6月机器学习 分割超平6月机器学习 思上述集合为(x，另一组集合为(x26月机器学习 支撑超平 6月机器学习 支撑超平6月机器学习 凸函6月机器学习 一阶可6月机器学习 进一步的6月机器学习 二阶可若f是一元函数，上式表示二阶导大于等于6月机器学习 凸函数举6月机器学习 上境函数f6月机器学习 凸函数与思考：如何证明？(提示：定义6月机器学习 Jensen不等式：若f是凸函基本Jensen不等若则若则6月机器学习 思 0,b 提示：任取a,b>0，θ=0.5带入基本Jensen不等6月机器学习 保持函数凸性的算凸函数的非 6月机器学习 凸函数的逐点最大f1,f2均为凸函数，定义函数6月机器学习 思OxNx点x到任意集合C的最远距离6月机器学习 共轭函原函 共轭函数定义显然，定义式的右端是关于f*()该名称的原6月机器学习 对共轭函6月机器学习 例：求共轭函可逆对称阵Q，对于任意的向量x，定义函 f*即是f6月机器学习 Fenchel不等6月机器学习 Fenchel不等式的应根据f(x)及其共轭函数带入Fenchel不等xT yTQ1y y6月机器学习 凸优6月机器学习 优化问题的基本形优优化问题的可行点(解可行域(可解集最优化最优化6月机器学习 局部最优6月机器学习 凸优化问题的可行域为凸凸优化问题的局部最优解即为全局最优6月机器学习 非凸优化问题的变6月机器学习 对偶问对固定的x，Lagrang函数Lx,λv)λv的仿射函数6月机器学习 Lagrange对偶函数(dualLagrange对偶函若没有下确∀>题有最优值p*进一步：Lagrange对偶函数为凹函6月机器学习 6月机器学习 线性方程的最小二乘问原问Lagrange函Lagrange对偶函6月机器学习 强对偶条 6月机器学习 Karush-Kuhn-Tucker(KKT)条6月机器学习 参考