第一讲 最优化基础课件

1、最优化理论与方法,张平健华南理工大学计算机学院Email:Tel最优化历史,Fermat,1638;Newton,1670minf(x)Euler,1775minf(x,y,)Lagrange,1797minf(x,y,)s.t.g(x,y,)=0Euler,Langrange-calculusofvariations,最优化历史-近现代,1930s1940s：生产运输问题、资源规划问题、Kuhn-Tucker定理1940s：线性规划单纯型法1950s：动态规划1950s：凸分析1980s：非光滑分析1980s：椭圆算法,最优化的例子,参数优化的例子运筹学线性规划问题

2、、动态规划问题数据分析最小二乘方法、参数估计极值问题湖泊深度、蜂房结构、效用函数约束优化库存问题、能耗、功耗问题泛函最优化的方法等周线问题变分问题摆线问题最小时间最少燃料最优控制问题,最优化问题的模型,f(x),gi(x),hj(x):RnRminf(x)s.t.gi(x)0,i=1,2,mhj(x)=0,j=1,2,l更一般地，可写为minf(x),D可行域（约束域）xD,最优化问题的分类,按目标函数与约束函数的性质线性规划二次规划凸规划非线性规划按约束形式无约束问题等式约束问题不等式约束问题混合约束问题,最优化应用,管理经济工程技术人工智能,预备知识,二次型与正定矩阵多元函数的梯度多元函数

3、的Hessian矩阵多元函数的Taylor展开凸函数及其性质,二次型,f(x1,x2,xn)=a11x12+a12x1x2+a1nx1xn+a21x1x2+a22x22+a2nx2xn+an1x1xn+an2xnx2+annxn2=XTAX,其中X是向量(x1,x2,xn)T,T代表转置，A是n阶（对称）方阵,（半）正定矩阵,（半）正定矩阵是对称的（半）正定矩阵的所有特征值都(=)0（半）正定矩阵可用正交矩阵对角化,梯度,f(x)(f/x1,f/x2,f/xn)TRn线性函数：f(x)=cTx+b,f(x)=c二次函数：f(x)=(1/2)xTQx+cTx+b,f(x)=Qx+c例：f(x1,

4、x2)=4x1-3x2,f(x)(4,3)T=,梯度计算模块,用外推法计算梯度,Hessian矩阵（二阶偏导数矩阵）,2f/x122f/x2x12f/xnx12f(x)=2f/x1x22f/x222f/xnx22f/x1xn2f/x2xn2f/xn2线性函数：f(x)=cTx+b,2f(x)=0二次函数：f(x)=1/2xTQx+cTx+b,2f(x)=Q例：,Hessian矩阵计算模块,用外推法计算Hessian矩阵对角线元素非对角线元素,多元函数的Taylor展开,设f(x):RnR，二阶可导。在x*的邻域内一阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+o(x-x

5、*)二阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+(1/2)(x-x*)T2f(x*)(x-x*)+o(x-x*2)例：求在x*（1,1)T处的二阶Taylor展开式,凸集,设集合SRn，若x(1),x(2)S,0,1，必有x(1)(1-)x(2)S，则称S为凸集。规定：单点集x为凸集，空集为凸集。两个凸集的和、差、交集仍是凸集。两个凸集的并凸吗？（，）是凸集吗？,凸函数,设集合SRn为凸集，函数f:SR若x(1),x(2)S,(0,1)，均有f(x(1)(1-)x(2)f(x(1)+(1-)f(x(2)，则称f(x)为凸集S上的凸函数。（弦在线上）若进一步有上面不等

6、式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。,凸函数的判别条件,f是凸函数的充要条件是是a的凸函数。f是凸函数f是严格凸函数f是凸函数半正定。f是严格凸函数正定。反之不然，,凸函数的组合,思考：设f1,f2是凸函数，设1,20,1f1+2f2,1f1-2f2是否凸函数？f(x)=maxf1(x),f2(x),g(x)=minf1(x),f2(x)是否凸函数？,水平集,定义：设集合SRn，函数f:SR，R，称S=xSf(x)为f(x)在S上的水平集。定理：设集合SRn是凸集，函数f:SR是凸函数，则对R，S是凸集。反之不然，sgn(x)。,凸函数的性质,以下设SRn为非空凸集，函数f:SR1）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。例:f(x)2(x=1)；f(x)x2(x1)2）设f凸，则对任意方向方向导数存在。3）凸域上的凸函数的极小值必为最小值。严格凸时，极小点就是最小点。4）必要条件凸性充分条件,凸集分离定理,凸集边界上任意点存在支撑超平面。两个互相不交的凸集之间存在分离超平面。,支撑,强分离,分离,