非线性规划难点.pdf

《非线性规划难点.pdf》由会员分享，可在线阅读，更多相关《非线性规划难点.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、15.053 515.053 5月月 2525 日日z非线性规划理论z可分离规划分发：讲稿二维非线性规划几何分析：实例二维非线性规划几何分析：实例zMin(x14)2+(y15)2zS.t. (x-8)2+(y-9)249x2x13x+y24另一个例子另一个例子Min(x-8)2+(y-9)2那么全局无约束最小仍然可行。最优解不是可行域的边界。非线性规划难点非线性规划难点线性规划非线性规划哪里是最优解？哪里是最优解？注意：最优解不在拐角点上，而是在等值线第一次交于可行域之处。局部最优和全局最优局部最优和全局最优定义：设 x 是一个可行解，那么x 叫做全局最优解， 若对于任意可行解 y，f(x)

2、f(y)x 叫做局部最优解，若对于任意与x足够接近的可行解 y（如对任意 j 和足够小的， xj-yj xj+） ， 有 f(x)f(y)可能有多个局部最优解。什么条件下局部最优也是全局最优？什么条件下局部最优也是全局最优？z最小化问题。目标函数是凸函数，可行域是凸集。识别凸可行域识别凸可行域z若所有约束均是线性的，则可行域是凸集z凸集的交集是凸集z若对于任意可行解 x,y，他们的中点是可行解，那么该区域是凸的。 （除了非现实的例子）凸函数凸函数凸函数： 若对于任意y,z,01， 有 f(y+(1-)z)f(y)+(1-)f(z)例如：f(y+z)/2)f(y)/2+f(z)/2若上式为1，则

3、称为严格凸函数。连接任意点的线段总在曲线上端。（y+z） 2凸性与极值点凸性与极值点若对于任意两点 x,y， 实数0,1 ，x+(1-)y，那么 S 是凸集。线性规划的可行域是凸集。我们把 S 中的元素 W叫做极值点 （顶点或拐角点） ， 若 W 不是 S 中任何线段的中点。哪个是凸的？哪个是凸的？凹函数凹函数凹函数： 若对于任意y,z,01， 有 f(y+(1-)z)f(y)+(1-)f(z)例如：f(y+z)/2)f(y)/2+f(z)/2若上式为0,b0, h(x)=a f(x)+b g(x)也是凸函数。z若 y=f(x)是凸函数，那么 （x,y） ：f(x)y是凸集。哪个是凸可行域？哪

4、个是凸可行域？(x,y)：yx2+2(x,y)：yx2+2(x,y)：y=x2+2什么函数是凸函数？什么函数是凸函数？zf(x)=4x+7所有线性函数zf(x)=4x2-13部分二次函数zf(x)=exzf(x)=1/x x0zf(x)=|x|zf(x)=-ln(x) x0充分条件：对于所有 x, f ”(x)0局部最大（最小）的性质局部最大（最小）的性质z凸集上的凹函数的局部最大值也是全局最大值。z凸集上的凸函数的局部最小值也是全局最小值。z严格凹性或凸性意味着全局最优解唯一。z考虑到这些，可以准确地解：具有线性约束和目标函数是凹函数的最大化问题。具有线性约束和目标函数是凸函数的最小化问题。

5、局部最优性的更多内容局部最优性的更多内容z求解非线性规划最小问题通常会找到局部最优解。z当局部最优解是全局最优解时，这将会很有用。z在很多时候并不是如此。z结论：若求解非线性规划问题，试着看看局部最优解如何。用用 ExcelExcel 规划求解解非线性规划问题规划求解解非线性规划问题求一元非线性规划问题的局部最优解求一元非线性规划问题的局部最优解若 f()是凹函数 （或单峰函数） ， 且可微。Max f( )s.t. ab对半搜索/减半搜索z步骤 1.从不确定区域a,b开始，计算中点M =(a+b)/2 的导数。z步骤 2.若 f(M)0， 将区间a, M去掉。 若 f(M)0, 去掉区间M,

6、bz步骤 3. 计算新区间中点的一阶导数，返回步骤 2，直到不确定区间足够小。其他搜索技术其他搜索技术z不计算导数（可以精确计算） ，用 2个函数估值决定最新的区间zFibonacci 搜索z步骤 1. 从不确定区域 a,b开始。 估计区间中 2 个镜面对称点1f(2), 去掉区间2,b。z步骤 3. 在新区间选择点的镜面对称点，重新记作1和2，且12，计算函数值 f(1)和 f(2)。返回步骤 2 直到区间足够小为止。求一元非线性规划问题的局部最优解求一元非线性规划问题的局部最优解解一元非线性规划：Maxf()s.t. ab最优解是边界点或者满足 f(*)=0 并且 f(*)0。单峰函数单峰

7、函数z一元函数是单峰函数，若函数最多一元函数是单峰函数，若函数最多有一个局部极大值（或者最多有一有一个局部极大值（或者最多有一个局部极小值）个局部极小值）FibonacciFibonacci 搜索搜索1,1,2,3,5,8,13,21, 34迭代步骤 1，搜索区间的长度为第 k 个FibonacciFibonacci 数。迭代步骤 j. 搜索区间的长度为第 k-j+1个 FibonacciFibonacci 数。单峰函数时，该技术收敛于最优解用用 FibonacciFibonacci 搜索寻找局部最大解搜索寻找局部最大解搜 索 区 间长度 3最大值可能在哪？能够找到一个局部最大解，但不一定是能

8、够找到一个局部最大解，但不一定是全局最大解全局最大解可分离规划可分离规划z可分离规划具有形式：Max fj(xj)s.t. gij(xj)0, i=1,.,m每个变量 xj看上去是分离的，一个存在于函数 gij中，一个存在于目标函数 fj中。每个非线性函数都仅仅有一个变量。能够找到一个局部最大解，但不一定是能够找到一个局部最大解，但不一定是全局最大解全局最大解FibonacciFibonacci 搜索中函数估计的个数搜索中函数估计的个数z当对称选取新点时，连续搜索区间长度为：lk=lk+1+lk+2。z给定 Fibonacci 数列 1,2,3,5,8,13,21,34，要求最后区间长度为1，

9、即ln=1，求解区间长度。z因此，若初始区间长度为 34，大约需要 8 个函数值将区间长度减到 1。z评价：若函数是凸函数或者单峰函数，那么 Fibonacci 搜索收敛于全局最优解。可分离规划例子可分离规划例子用分段函数估计非线性函数用分段函数估计非线性函数z第一方面，选择估计函数z第二方面，什么时候分段估计函数是线性规划的变形？估计一个非线性一元函数：法估计一个非线性一元函数：法选择不同的x值描述 x轴。用分段线性规划近似。更多关于法的内容更多关于法的内容设-1x1,令 x=2(-3)+3(-1), 1，20 且1+2如何估计区间中的 f()?若-3x1会怎样？估计一个非线性一元函数估计一

10、个非线性一元函数更多关于法的内容更多关于法的内容假定-3x-1，将 x表 示 为 1(-3)+2(-1) ，1，20 且1+2。然后估计 f(x)=1(-20)+2(-7 1/3)近似法近似法原问题：minx3/3+2x-5+其他线性项s.t. 3 x3+更多约束近似问题：min1f(a1)+2f(a2)+3f(a3)+4f(a4)更多线性项s.t.1+2+3+4=1；0+更多其他约束为什么近似是错误的？为什么近似是错误的？近似问题： min1f(a1)+2f(a2)+3f(a3)+4f(a4)+其他线性项s.t. 1+2+3+4=1；0考虑13/2，24=当只有两个为正时，该方法给出的近似是

11、正确的。近似极小非线性规划问题的目标函数近似极小非线性规划问题的目标函数原问题： min f(y): yp设y=jjaj其中jj，且0近似 f(y)。min jjf(aj )： jjajp z注意：当考虑应用另一种方式表示 y 时，线性规划将选择目标函数近似值是最小的那种。忽略邻接条件的可行近似目标函数忽略邻接条件的可行近似目标函数+其他约束临接条件临接条件.最多有个权重是正数.若正好有个权重是正数，那么是j和j+1.对于其他近似函数该条件仍然适用对于凸函数极小化问题，法自动满足对于凸函数极小化问题，法自动满足附加的邻接条件附加的邻接条件+邻接条件邻接条件+ +其他约束其他约束但是同样情况下极小化总是发生在分段但是同样情况下极小化总是发生在分段线性曲线上线性曲线上+其他约束可分离规划（线性约束情况）可分离规划（线性约束情况）z从一个非线性规划开始：z变为可分离：z利用法近似如何建立可分离函数？如何建立可分离函数？原项替代项约束限制非线性规划总结非线性规划总结z凸函数，凹函数和凸集都是重要的特性zBolzano 搜索与 Fibonacci 搜索技术用来解一元单峰函数问题z可分离规划非线性目标与非线性约束是可分离的通用近似技术近似近似z用变量重新表示对任意 j,k 成立和邻接条件约束若原问题是凹性的，那么可以不用管邻接条件（邻接条件自动满足） 。转化实例转化实例代替， 并令加入约束