非线性规划

缺点：每次迭代得到的解往往是不可行的！ 缺点：每次迭代得到的解往往是不可行的！ 对没有等式约束的问题，可采用内点法： 对没有等式约束的问题，可采用内点法：
I ( X , rk ) = f ( X ) + rk ∑ ln g i ( X ) or I ( X , rk ) = f ( X ) + rk ∑
其它情况: 其它情况 求目标函数的最大值或约束条件为小于等 于零的情况，都可通过取其相反数化为上述一般形式． 于零的情况，都可通过取其相反数化为上述一般形式．
定义1 把满足问题(1)中条件的解 中条件的解X∈ 称为可行解 或可行点 ， 可行解(或可行 定义 把满足问题 中条件的解 ∈Rn称为可行解 或可行点)， 所有可行点的集合称为可行集 可行域)．记为D． 可行集(或 所有可行点的集合称为可行集 或可行域 ．记为 ．即:
m m i =1 i =1
rk 单调递减趋于 0(如 rk + 1 = β rk ,0 < β < 1)!
缺点：不适用于等式约束问题！ 缺点：不适用于等式约束问题！
1 gi (X )
基本求解方法： 罚函数法——内点法/外点法 内点法/ 基本求解方法： (1)罚函数法 罚函数法 内点法
gi ( X ) ≥ 0 s .t . h j ( X ) = 0 min f ( X )
基本求解方法： 罚函数法——内点法/外点法 内点法/ 基本求解方法： (1)罚函数法 罚函数法 内点法
gi ( X ) ≥ 0 s .t . h j ( X ) = 0 min f ( X )
(2)序列线性规划法 序列线性规划法 (3)序列二次规划法 序列二次规划法 (4)信赖域算法 信赖域算法
约束条件为： 约束条件为：
2
6
∑ ∑
2 j =1 6 i =1
x ij = d i , i = 1,2,L ,6 x ij ≤ e j , j = 1,2
x ij ≥ 0, i = 1,2,L ,6; j = 1,2.
这是一个线性规划, 代入已知数据可方便求解问题 问题(1); 这是一个线性规划 代入已知数据可方便求解问题 这也是一个运输问题 也可计算运费之后列出运输表来求 是一个运输问题, 运输问题 问题(1); 解问题
(2)序列线性规划法 序列线性规划法 (3)序列二次规划法 序列二次规划法 (4)信赖域算法 信赖域算法
序列二次规划法——每次求解一个近似二次规划： 每次求解一个近似二次规划： 序列二次规划法 每次求解一个近似二次规划
1 T min f ( X ) ≈ f X + ∇f X d + d Bk d 2 k k T g i ( X ) ≈ gi ( X ) + ∇g i ( X ) d ≥ 0 i = 1, L , m
1、二次规划 、
1. 2. 3. 4. 5. 6.
x=quadprog(H,C,A,b); x=quadprog(H,C,A,b,Aeq,beq); x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); [x,fval,exitflag,output]=quaprog(...);
(1)的求解： 记工地的位置为 i，bi)，水泥日用量为 i, 的求解： 记工地的位置为(a 的求解 ，水泥日用量为w i=1,…,6; 料场位置为 j，dj), 日储量为 j，j=1,2; 从料场 向工 料场位置为(c 日储量为e 从料场j向工 的运送量为x 地i的运送量为 ij. 的运送量为
min f = ∑ ∑ xij (c j − ai ) 2 + (d j − bi ) 2 目标函数为： 目标函数为： j =1 i =1
k k T k
k k T k i
hj ( X ) ≈ hj X
( ) + ∇h ( X ) ( X − X ) = 0
k k T k j
i = 1,L , m
j = 1,L , l
X − Xk ≤ δk
δ k — —步长限制需进行适当更新 (需进行适当更新 )
基本求解方法： 罚函数法——内点法/外点法 内点法/ 基本求解方法： (1)罚函数法 罚函数法 内点法
1 T min f ( X ) ≈ f X + ∇f X d + d Bk d 2 k k T g i ( X ) ≈ gi ( X ) + ∇g i ( X ) d ≥ 0 i = 1, L , m
k k T
( )
( )
j
hj ( X ) ≈ hj X
( ) + ∇h ( X ) d = 0
k k T
4. 非线性规划
非线性规划建模——引例 引例 非线性规划建模 非线性规划模型、基本概念、 非线性规划模型、基本概念、性质 非线性规划重要算法 用MATLAB解无约束规划 解无约束规划
引例： 引例： 供应与选址
某公司有6个建筑工地要开工，每个工地的位置(用平面坐标系 ， 某公司有 个建筑工地要开工，每个工地的位置 用平面坐标系a， 个建筑工地要开工 用平面坐标系 b表示，距离单位：千米 )及水泥日用量 吨)由下表给出。目前有 表示， 及水泥日用量d(吨 由下表给出 由下表给出。 表示 距离单位： 及水泥日用量 两个临时料场位于A(5,1)，B(2,7)，日储量各有 吨。假设从料场 两个临时料场位于 ， ，日储量各有20吨 到工地之间均有直线道路相连。 到工地之间均有直线道路相连。 (1) 试制定每天的供应计划，即从 ，B两料场分别向各工地运 试制定每天的供应计划，即从A， 两料场分别向各工地运 送多少吨水泥，使总的吨千米数最小。 送多少吨水泥，使总的吨千米数最小。 吨千米数最小 (2) 为了进一步减少吨千米数，打算舍弃两个临时料场，改建 为了进一步减少吨千米数，打算舍弃两个临时料场， 两个新的，日储量各为20吨 问应建在何处， 两个新的，日储量各为 吨，问应建在何处，节省的吨千米数有多 大？ 工地位置(a， 及水泥日用量 及水泥日用量w 工地位置 ，b)及水泥日用量 1 需点 a 1.25 b 1.25 w(吨) 吨 3 2 8.75 0.75 5 3 0.5 4.75 4 4 5.75 5 7 5 3 6.5 6 6 7.25 7.75 11
k k T
( )
( )
j
hj ( X ) ≈ hj X
d ≤ δk
( ) + ∇h ( X ) d = 0
k k T
j = 1, L , l
Bk — —当前点 Lagrage 函数的 Hessen 矩阵近似， 矩阵近似， 新 用类似拟牛顿法迭代更 ！ δ k — —信赖域半径需要适当更新 (需要适当更新 )
(2)序列线性规划法 序列线性规划法 (3)序列二次规划法 序列二次规划法 (4)信赖域算法 信赖域算法
序列线性规划法——每次求解一个近似线性规划： 每次求解一个近似线性规划： 序列线性规划法 每次求解一个近似线性规划
min f ( X ) ≈ f X
i i
( ) + ∇f ( X ) ( X − X ) g ( X ) ≈ g ( X ) + ∇g ( X ) ( X − X ) ≥ 0
m
外点法——迭代求解如下无约束规划： 迭代求解如下无约束规划： 外点法 迭代求解如下无约束规划
T ( X , M k ) = f ( X ) + M k ∑ [min (0, g i ( X ))]
i =1
2
( X )]2 + M k ∑ [h j
l j =1
{Mk }为单调递增趋于+ ∞的数列 如Mk+1 = 10Mk )! (
迭代： X 迭代：
k +1
= X +d
k
*
用Matlab解非线性规划问题 解非线性规划问题
标准型为： 标准型为： Min Z= ½ XTHX+cTX s.t. AX<=b AeqX=beq VLB≤X≤VUB 软件求解,其输入格式如下 用MATLAB软件求解 其输入格式如下 软件求解 其输入格式如下:
特殊非线性规划: 特殊非线性规划:——二次规划 二次规划
1 min x ′Hx + c ′x 2 s .t . A ⋅ x ≤ b Aeq ⋅ x = beq V ≤ x≤U
二次规划有成熟的求解算法，特别当 正定或半正定时 二次规划有成熟的求解算法，特别当H正定或半正定时 (这时目标函数为凸函数 ，可得到全局最优解！ 这时目标函数为凸函数)， 这时目标函数为凸函数 可得到全局最优解！ 二次规划有着非常广泛的应用! 二次规划有着非常广泛的应用
D = X | g i ( X ) ≤ 0, h j ( X ) = 0, X ∈ R n
min f ( X )
X∈D ∈
{
}
问题(1)可简记为 问题 可简记为
定义2 局部极小值点(局部最优解 局部最优解); 定义2 局部极小值点 局部最优解 ; 严格局部极小值点(严格局部最优解 严格局部最优解). 严格局部极小值点 严格局部最优解 全局极小值点(全局最优解 全局最优解) 全局极小值点 全局最优解 严格全局极小值点(严格全局最优解 严格全局最优解). 严格全局极小值点 严格全局最优解 注记： ， 是凸函数而h 是线性函数时，局部最优为全局 注记：当f，gi是凸函数而 j是线性函数时，局部最优为全局 最优。 最优。 关键字： 函数， － 条件 关键字：Lagrange函数，K－T条件 函数 返回
例1
min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x2≤2 -x1+2x2≤2 2 - 2 − 2 x1≥0, x2≥0 H = − 2 4 , C = − 6