非线性规划ppt课件

1、非线性规划非线性规划根底知识根底知识直线搜索问题直线搜索问题无约束问题无约束问题不等式约束问题不等式约束问题等式和不等式约束问题等式和不等式约束问题拉格朗日对偶问题拉格朗日对偶问题主要内容主要内容根底知识根底知识非线性规划的普通方式非线性规划的普通方式其中其中 ljXgmiXhXfji, 2 , 1, 0, 2 , 1, 0 s.t.minnTnRxxxX,21定义可行集定义可行集上述普通方式可简写成上述普通方式可简写成 1010lj,Xgm,i,XhRXjin XfX min XXfXfX,全局最优解全局最优解 ： XfXfX的的 邻域：邻域： ,XXRXXBnXX部分最优解部分最优解 ：

2、,XBXXfXf，且存在，且存在 满足满足0X假设在上面的定义中用假设在上面的定义中用 交换交换 ，那么称那么称 为严厉部分最优解和严厉全局最优解为严厉部分最优解和严厉全局最优解 f Xf XXX)(Xf部分最优解部分最优解全局最优解全局最优解邻域邻域标量函数求偏导数梯度标量函数求偏导数梯度nTTxXfxXfxXfXXfXf)(,)(,)()()(21nxXfxXfxXfXXfXf)()()()()(21向量函数求偏导数向量函数求偏导数TmXfXfXfXF)(,),(),()(21mnmmnmTXfXfXfXXfXXfXXfXXF)(,),(),()(,)(,)()(2121nmmTTTnmT

3、mTTTXfXfXfXXfXXfXXfXXF)()()()()()()(2121海赛海赛Hesse矩阵矩阵2221 112122222 122222212()()()()()()()()()()nnTnnnnf Xf Xf Xx xx xx xf Xf Xf Xf Xx xx xx xf XXf Xf Xf Xx xx xx x对向量函数的点积求偏导数对向量函数的点积求偏导数TmXfXfXfXF)(,),(),()(21TmXgXgXgXG)(,),(),()(21)()()()()()(XFXXGXGXXFXXGXFTTTTTTTTTXXFXGXXGXFXXGXF)()()()()()(对常

4、数矩阵和向量函数的乘积求偏导数对常数矩阵和向量函数的乘积求偏导数TmXfXfXfXF)(,),(),()(21mmRATTTTTAXXFXAXFXXAF)()()(TTXXFAXXAF)()(对二次函数求偏导数对二次函数求偏导数 mmTRAAAXXAAXXAXAXXXXAXXTTTT2AXAAXXXAXXAXXXAXXTTTTTTTTT2一元函数在原点的二阶泰勒一元函数在原点的二阶泰勒Taylor展开展开221)(21)0()(tctcgtgt0其中其中tdttgdc222)()(0)(1tdttdgct0221)(21)()(tctcXftDXf多元函数在给定点沿给定方向的二阶泰勒展开多元函

5、数在给定点沿给定方向的二阶泰勒展开其中其中DDXfDtdttDXfdcT)()(2222DXftdttDXdfcT)(0)(1221()()()()2TTf XtDf Xf X DtDf XD Dt无约束优化问题最优性条件无约束优化问题最优性条件 XfnRXmin1 是部分最优解的必要条件：是部分最优解的必要条件： *X, 0, 0)()(*tXftDXf0)(*Xf)(*XfD0)(*Xf理由：理由：DtDXfDXftDtDXfDtXfXftDXfTTTT)(21)()(21)()()(*22*2*22*X不是部分最优解不是部分最优解2 是严厉部分最优解的充分条件：是严厉部分最优解的充分条件

6、：*XnTRDDtDXfDXftDXf,)(21)()(2*2*0)(*Xf0)(*2XfnTRDDXf, 0)(*理由：理由： 0)(*Xf0)(*2Xf, 0, 0)(*2DXf, 0,),()(*tRDXftDXfn,),()(XBXXfXf凸集上的凸函数和凹函数凸集上的凸函数和凹函数设设 是定义在集合是定义在集合 上的函数，假设上的函数，假设是凸集，并且对是凸集，并且对 中恣意两点中恣意两点 以及闭区间以及闭区间 中恣意一点中恣意一点 都满足都满足nR21,XX1, 0 212111XfXfXXf那么称那么称 是凸集是凸集 上的凸函数，假设上的凸函数，假设是凸集是凸集 上的凸函数，那么

7、称上的凸函数，那么称 是凸集是凸集上的凹函数，此时在上面的条件下应满足上的凹函数，此时在上面的条件下应满足)(Xf)(Xf)(Xf)(Xf 212111XfXfXXf一元凸凹函数的图象一元凸凹函数的图象1X2X1Xf2Xf211XX211XXf 211XfXf1X2X1Xf2Xf211XX211XXf 211XfXf凸函数凸函数凹函数凹函数一元可导凸凹函数的充要条件一元可导凸凹函数的充要条件2Xf1X2X1Xf1121fXfXXX凸函数凸函数凸函数凸函数11212fXfXXXfX 凹函数凹函数11212fXfXXXfX 多元可导凸凹函数的一阶充要条件多元可导凸凹函数的一阶充要条件 211212

8、1,XXXfXfXXXfT必要性：必要性：21211)(21)()()(DDXfDDXfXfXfTTDDXfDDXfXfXfXfXfXfTT)(21)()()()()()1 ()(121212121112,(1),DXXXXDXX利用二阶泰勒展开可得利用二阶泰勒展开可得记记令令 充分小，由凸凹性可得上面的不等式充分小，由凸凹性可得上面的不等式充分性：充分性：用用 和和 分别乘以上两式再相加，再利用分别乘以上两式再相加，再利用 2112121,XXXfXfXXXfT可得可得0)1 (21XXXX记记 ，那么，那么 ，利用给定条件，利用给定条件21)1 (XXXX XfXfXXXfXfXfXXXf

9、TT22111可得可得 211XfXfXf凸凹函数的二阶充分条件凸凹函数的二阶充分条件 XXf,002XXDXXDXXX221121,)1 (2222222)(5 . 0)()()(DDXfDDXfXfXfTT1112111)(5 . 0)()()(DDXfDDXfXfXfTT0)1 ()1 (2121XXXDD212111122222()(1) ()()0.5()0.5(1)()TTf Xf Xf XDf XD DDf XD D记记由于由于 )()()1 ()(21XfXfXf假设假设 是开集，前面的充分条件也是必要条件是开集，前面的充分条件也是必要条件DZDXfZDXT,00,2假设存在假

10、设存在 和和 使得使得 ，必存在充分小的必存在充分小的 满足满足 XnRZ 002ZXfZT0ZD取取 满足满足 ，利用，利用ZDZDXfZDXfXfDXfTT)(5 . 0)()()(22记记 ，由以上条件可得，由以上条件可得XXDXX,12 2112121,XXXfXfXXXfT和前面证明的凸凹函数的充要条件矛盾和前面证明的凸凹函数的充要条件矛盾凸性对优化问题的根本作用凸性对优化问题的根本作用 XfX min假设假设 是凸集，是凸集， 是其上的延续凸函数，称是其上的延续凸函数，称 Xf解，那么它也是该问题的全局最优解解，那么它也是该问题的全局最优解是凸规划问题是凸规划问题*X假设假设 是凸

11、规划问题的恣意一个部分最优是凸规划问题的恣意一个部分最优证明：假设存在证明：假设存在 满足满足接近接近 ，阐明，阐明 不是部分最优解，矛盾不是部分最优解，矛盾X10),()1 ()()1 (*XfXfXXf又由于又由于*()(),0f Xf X*X)()(*XfXf10),()1 (*XfXXf由于对充分小的由于对充分小的 ， 可以充分可以充分0*)1 (XX*X可行下降方向可行下降方向对于优化问题对于优化问题 ，给定可行解，给定可行解 以以 XfX min称为可行下降方向称为可行下降方向X称称 是是 处的可行方向，假设存在处的可行方向，假设存在 满足满足及向量及向量 ，假设存在，假设存在 满足满足nRDtttDX0,DX0tttXftDXf0),(称称 是是 处的下降方向，既可行又下降的方向处的下降方向，既可行又下降的方向DX0tX)(Xf的等值线的等值线可行不下降方向可行不下降方向可行下降方向可行下降方向不可