06-非线性规划-约束问题.pptx

《06-非线性规划-约束问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章最优化方法运筹学施鹏约束极值问题有约束无约束非线性线性约束极值问题等式约束问题直接代入法拉格朗日函数不等式约束问题库-塔条件广义（增广）拉格朗日函数罚函数法等式约束问题等式约束问题直接代入法求解一个变量，代入目标函数和约束方程适用于只含一个或两个等式约束直接代入法例求解解由约束条件得直接代入法代入目标函数，得求稳定点，得可求得x1的最优值等式约束问题Lagrange定理（1）x*是局部最优解（2）f，hj在x*的某一邻域内连续可微（3）彼此线性无关则存在一组实数，使得（一阶必要条件）Lagrange法约束问题转化为无约束问题最优解条件与原问

2、题等价Lagrange法构造Lagrange函数L（n+l维）：拉格朗日因子原约束极值问题化作无约束极值问题Lagrange法一阶必要条件Lagrange法例求解解：构造拉格朗日函数Lagrange法Lagrange法例求解解构造拉格朗日函数对x求偏导，得结合约束条件得Lagrange法即Lagrange法求解问题解令Lagrange法由必要条件得Lagrange法得x1=λ/4，x2=3λ/10，再代入得二阶充分条件如果（1）f，h1，h2…hl为n维空间上连续二阶可微函数（2）存在x*∈R(n)，λ*∈R(n)，使拉格朗日函数的梯度为零（3）对于

3、任意非零向量y∈R(n)且有则x*为严格极小点证明前述例题中（0.5，0.5）是否为函数的极小点因此有又因为代入，得故点（0.5，0.5）为最优点，最优值为-0.25Lagrange法n+l个变量，n+l个方程，运算量大只含有不等式约束的非线性问题非线性问题只含有不等式约束的非线性问题Kuhn-Tucker条件KTC（必要条件）适用于含不等式约束的非线性规划问题对凸规划既是必要条件，也是充分条件Kuhn-Tucker条件基本概念锥体一组点（一个集合）R存在λ≥0，满足则R为一个锥体凸圆锥：凸集形成的圆锥Kuhn-Tucker条件基本概念起作用约束&不

4、起作用约束规划问题的可行域（由约束条件决定）中的某个点（可行点）能使某个（些）不等式约束（gi(x)≥0）中的等号成立，则称该不等式约束为该可行点的起作用约束（有效约束），若某个（些）不等式约束的等号不成立，则称该不等式约束为该可行点的不起作用约束（非有效约束）KTC的几何描述前提：在任何约束问题的局部最优点，不能（或很少能）通过改变变量以改进目标函数值Kuhn-Tucker条件如非线性规划问题(1,1)为最优点g1，g2为点(1,1)的有效约束Kuhn-Tucker条件定义从某点处沿某方向移动，若不会违反任何约束条件，该方向称为可行方向对于点(1,

5、1)，可行方向为g1在该点的切线以及g2产生的圆锥中负梯度方向必须在g1，g2梯度向量形成的圆锥中Kuhn-Tucker条件一般性描述：目标函数的负梯度方向必须是有效约束的梯度向量的非负线性组合Kuhn-Tucker条件代数描述假设（1）x*是一个局部最优解（2）f(x)、gi(x)在点x*可微Kuhn-Tucker条件则存在一组不全为零的数使约束条件为不等式的拉格朗日函数对问题可构造拉格朗日函数不等式的拉格朗日函数例求解如下问题解构造拉格朗日函数不等式的拉格朗日函数满足必要条件不等式的拉格朗日函数μx1x2f(x)000A0鞍点0.5+3.54-3

6、.54B-12.5极小值-3.54+3.54C-12.5极小值-0.5+3.54+3.54D+12.5极大值-3.54-3.54E+12.5极大值另解剩余变量由必要条件μx1x2σf(x)000A50鞍点0.5+3.54-3.54B0-12.5极小值-3.54+3.54C0-12.5极小值-0.5+3.54+3.54D0+12.5极大值-3.54-3.54E0+12.5极大值同时具有等式约束和不等式约束的问题对于极小点x*，则存在λ*、μ*，满足对于不等式有二阶必要和充分条件矩阵J(x*)的行向量为x*处有效约束的梯度对于所有非零向量y有即对于y垂直

7、于有效约束梯度向量（切平面）L的Hessian矩阵正定（充分条件）当>变成≥，变成二阶必要条件，Hessian矩阵半正定例求解以下问题找到与(1,0)最接近的点拉格朗日函数KTC为可得三个解：由二阶充分条件可得前两个点为局部极小点，第三个点不是，判断过程如下：由得由二阶必要条件，Hessian矩阵在(0,0)处对有效约束的切平面半正定由得故切平面为有故不满足二阶必要条件，所以(0,0)点不是局部极小点对于有对于该点切平面为故有满足二阶充分条件，是局部极小值点罚函数法有约束问题一系列无约束问题罚函数r：惩罚参数罚函数法例最优化问题构造罚函数惩罚项罚函

8、数法基本思路：增大r，至违反等式约束。改变x，令等式约束得到满足。r*h2=0，以使f值接近P值。一般情况下