第一讲 最优化基础.

最优化理论与方法张平健华南理工大学计算机学院Email:[e-mail]:15818160294最优化历史Fermat,1638;Newton,1670minf(x)Euler,1775minf(x,y,…)Lagrange,1797minf(x,y,…)s.t.g(x,y,…)=0Euler,Langrange-calculusofvariations最优化历史-近现代1930’s~1940’s：生产运输问题、资源规划问题、Kuhn-Tucker定理1940’s：线性规划单纯型法1950’s：动态规划1950’s：凸分析1980’s：非光滑分析1980’s：椭圆算法最优化的例子参数优化的例子1.运筹学－线性规划问题、动态规划问题2.数据分析－最小二乘方法、参数估计3.极值问题－湖泊深度、蜂房结构、效用函数4.约束优化－库存问题、能耗、功耗问题泛函最优化的方法1.等周线问题－变分问题2.摆线问题－最小时间3.最少燃料－最优控制问题最优化问题的模型f(x),gi(x),hj(x):RnRminf(x)s.t.gi(x)≤0,i=1,2,…,mhj(x)=0,j=1,2,…,l更一般地，可写为minf(x),D－可行域（约束域）x∈D最优化问题的分类按目标函数与约束函数的性质1.线性规划2.二次规划3.凸规划4.非线性规划按约束形式1.无约束问题2.等式约束问题3.不等式约束问题4.混合约束问题最优化应用管理经济工程技术人工智能预备知识二次型与正定矩阵多元函数的梯度多元函数的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)TRn线性函数：f(x)=cTx+b,f(x)=c二次函数：f(x)=(1/2)xTQx+cTx+b,f(x)=Qx+c例：f(x1,x2)=4x1-3x2,f(x)＝(4,3)T=43梯度计算模块用外推法计算梯度1()(,...,,...,)(/2)(/2)()()41'()36iiniiiiihfxxhxhhhhfxhhHessian矩阵（二阶偏导数矩阵）2f/x122f/x2x1…2f/xnx12f(x)=2f/x1x22f/x22…2f/xnx2…………2f/x1xn2f/x2xn…2f/xn2线性函数：f(x)=cTx+b,2f(x)=0二次函数：f(x)=1/2xTQx+cTx+b,2f(x)=Q例：222112223()37,()314fxxxxxfxHessian矩阵计算模块用外推法计算Hessian矩阵对角线元素非对角线元素::,0()();()()iijiiijijeeijhfxhehfxhe第二个单位向量;第分量为21''()[16()16()()()30(0)]322iiiiiiihhfxhhh21[16()16()()()30(0)]3221''()[''()''()]2ijijijijijijijijiijjhhzhhhfxzfxfx多元函数的Taylor展开设f(x):RnR，二阶可导。在x*的邻域内一阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+o(‖x-x*‖)二阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+(1/2)(x-x*)T2f(x*)(x-x*)+o(‖x-x*‖2)例：求在x*＝（1,1)T处的二阶Taylor展开式323121122(,)2fxxxxxx凸集设集合SRn，若x(1),x(2)S,[0,1]，必有x(1)＋(1-)x(2)S，则称S为凸集。规定：单点集{x}为凸集，空集为凸集。两个凸集的和、差、交集仍是凸集。两个凸集的并凸吗？（－∞，∞）是凸集吗？凸函数设集合SRn为凸集，函数f:SR若x(1),x(2)S,(0,1)，均有f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。（弦在线上）若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。凸函数的判别条件f是凸函数的充要条件是是a的凸函数。f是凸函数f是严格凸函数f是凸函数半正定。f是严格凸函数正定。反之不然，,,()()nxyRafxay()()()()Tfyfxfxyx()()()()Tfyfxfxyx2f2f4()fxx凸函数的组合思考：设f1,f2是凸函数，1)设1,20,1f1+2f2,1f1-2f2是否凸函数？2)f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？水平集定义：设集合SRn，函数f:SR，R，称S={xS∣f(x)≤}为f(x)在S上的水平集。定理：设集合SRn是凸集，函数f:SR是凸函数，则对R，S是凸集。反之不然，sgn(x)。凸函数的性质以下设SRn为非空凸集，函数f:SR1）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。例:f(x)＝2(x=1)；f(x)＝x2(x1)2）设f凸，则对任意方向方向导数存在。3）凸域上的凸函数的极小值必为最小值。严格凸时，极小点就是最小点。4）必要条件＋凸性＝充分条件凸集分离定理凸集边界上任意点存在支撑超平面。两个互相不交的凸集之间存在分离超平面。支撑强分离分离凸函数的判别例：1)f(x)＝x12+2x1x2+2x22+10x1-4；2)f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;3)f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4.5)；