可行方向法-梯度投影法课件.ppt

1、4.非线性结构优化非线性结构优化4.4 4.4 可行方向法可行方向法min().()0(1,2,)jFindfs tgjnxxx有约束优化问题有约束优化问题非线性优化问题非线性优化问题线性优化问题线性优化问题非线性约束优化问题非线性约束优化问题线性约束优化问题线性约束优化问题（目标函数（目标函数非线性）非线性）（目标函数（目标函数线性）线性）（约（约 束束线性）线性）（目标函数（目标函数非线性）非线性）（约（约 束束非线性）非线性）（目标函数（目标函数非线性）非线性）（约（约 束束线线 性）性）K-K-TK-K-T条件条件（1 1）K-K-TK-K-T条件条件),2,1(0)(.)(minmj

2、gtsfj x x ),2,1()()5(0)4(0)()3(0)()2(0)()()1(1mjggggfjjjjjmjjj x x x xx K-K-TK-K-T条件条件（梯度条件）（梯度条件）（约束条件）（约束条件）（松弛互补条件）（松弛互补条件）（非负条件）（非负条件）（正则条件或约束规格）（正则条件或约束规格）线性无关线性无关 定义：定义：)()(),(1xxxmjjjgfL)(xfP 2 x0)(2g x)(2g x)(1g x0)(1g2)(xfP x0)(2g x)(2g x)(1g x0)(1g)(xfP*x)(xf0)(222 xg0)(111 xg)(xf0)(222 xg

3、0)(111 xg)(1xg00)()()(212211，xxxggf00)()()(112211，x xxggf)(xfP x0)(2g x)(2g x)(1g x0)(1g2*x最优点最优点 ，一定在一定在 与与 之间，之间，所以所以 可以起作用的可以起作用的 非负线性组合表示。非负线性组合表示。*x)(*xf x*)(2g x*)(1g)(*xf x*)(jg),2,1()()()1(1mjgfmjjj xx 0)4(j 起作用的约束经过最优点起作用的约束经过最优点，0,j x 0)()2(jg x 0)(jg0)()3(x jjg最优点满足所有的约束条件最优点满足所有的约束条件，这就是

4、这就是K-K-T条件条件，约束优化问题：约束优化问题：（1）搜索方向；受约束条件的限制。）搜索方向；受约束条件的限制。（2）迭代步长；受约束条件的限制。）迭代步长；受约束条件的限制。（一）基本概念：（一）基本概念：（1）起作用的约束：起到限制性作用的约束。）起作用的约束：起到限制性作用的约束。（2）可行方向：点）可行方向：点 在可行域内的点，在可行域内的点，方向迭代后的新的点方向迭代后的新的点 也是可行域内的点，则搜索方向也是可行域内的点，则搜索方向 称为可行方向。称为可行方向。（3）可行下降方向：使目标函数下降的可行方向，称为可行下降方向。）可行下降方向：使目标函数下降的可行方向，称为可行下

5、降方向。dxx(0)(0)xddd x 0)(jgd x 0)(jg x 0)(ig起作用的约束起作用的约束min().()0(1,2,)jFindfs tgjnxxxkkkkfffxxxx)(T)()()()()(1kkikikigggxxxx)(T)()()()()(1)()(xxx11kkk)(xf)(xk将每一个函数在将每一个函数在 处对函数处对函数 进行进行taylor展开，取一次近四，则；展开，取一次近四，则；（1）如果）如果 或或 ，则搜索方向是下降方向。，则搜索方向是下降方向。0)()(1)()(xxkkff0)(kkfxx)(T0)()(1)()(xxkkff0)(kkfxx

6、)(T（2）如果）如果 在可行域内，在可行域内，则总可取步长，则总可取步长 ，得，得 ，使使 仍在可行域内，即任意搜索方向是可行方向。仍在可行域内，即任意搜索方向是可行方向。)(xk0)()(xkig0)(kkkkkdxx)()(1)(x1k（3）如果）如果 在边界上，在边界上，则对某个步长，则对某个步长 来说，如果来说，如果 ，则，则 在可行域内，故可行的。在可行域内，故可行的。)(xk0)()(xkig0)(k)(x1kmigggkkikiki,2,1,0)()()(1 xxxx)(T)()(（4）如果）如果(3)的情况下，的情况下，或，或 则则 位于位于 在在 点的切平面上，只有点的切平

7、面上，只有 为现行时，为现行时，才是可行点。才是可行点。)(x1k0)(1)(xkig0)(kkigxx)(T)(xig)(x1k)(xig)(xk0)(kkigxx)(T线性条件下线性条件下0)(kkigxx)(T非线性条件下非线性条件下d x 0)(jg x 0)(ig线性条件下线性条件下)(x ig线性约束条件下线性约束条件下bxAAxxA(xkkkk)bAx kbxAkexEExxE(xkkkk)eEx k0 xEk搜索方向需要满足的条件：搜索方向需要满足的条件：0)(kkigxx)(T0)(kkigxx)(T0)(kkfxx)(T目标函数下降的条件：目标函数下降的条件：约束条件：约束

8、条件：约束条件约束条件0 xEkbxAk搜索方向需要满足的条件：搜索方向需要满足的条件：0)(kkfxx)(T目标函数下降的条件：目标函数下降的条件：约束条件：约束条件：bxAk0 xEkkkkkfffxxxx)(T)()()()()(1kkkkkkkffffxxxxxxx)(TT)(T)()()(21)()()(1kkkkfffdxxx)(T)()()()()(1kkkkkkkffffdxddxxx)(TT)(T)()()(21)()()(21二次规划二次规划可行方向法可行方向法kkkkfffdx xx)(T)()()(min)()(min1kkkkkkkffffdxddxxx)(TT)(T

9、)()()(21)(min)()(min(1bxAk0 xEk.ts0ad.tskkfdx)(T)(minkkkkkffdxddx )(TT)(T)(21)(min线性约束问题的线性约束问题的Zoutendijk可行方向法可行方向法 解析搜索法：可行方向法解析搜索法：可行方向法起作用的约束起作用的约束不起作用的约束不起作用的约束解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜

10、索法：可行方向法解析搜索法：可行方向法非线性约束问题的非线性约束问题的Zoutendijk可行方向法可行方向法 解析搜索法：可行方向法解析搜索法：可行方向法-)()()()()(0)(0)()()()(xgdxgxgxgdxgxgdxgdxgxgdxg解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法 起作用约束可行方向法起作用约束可行方向法 解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法解析搜索法：可行方向法Topkis Veinott 全约束可行

11、方向法全约束可行方向法 解析搜索法：可行方向法解析搜索法：可行方向法)()()()()(0)()()()(xgdxgxgxgdxgdxgdxgxgdxg解析搜索法：可行方向法解析搜索法：可行方向法4.非线性结构优化非线性结构优化4.5 4.5 梯度梯度投影投影法法投影矩阵的基本概念投影矩阵的基本概念解析搜索法：梯度投影法解析搜索法：梯度投影法xqpQPRN解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法约束优化问题：约束优化问题：（1）搜索方向；受约束条件的限制。）搜索方向；受约束条件的限制。（2）迭代步长；受约束条件的限制。）迭代步长；受约束条件的限制

12、。搜索方向需要满足的条件：搜索方向需要满足的条件：0)(kkigxx)(T0)(kkfxx)(T目标函数下降的条件：目标函数下降的条件：约束条件：约束条件：线性约束条件下线性约束条件下bxAk0 xEk.tskkfdx)(T)(min搜索方向搜索方向线性约束问题的线性约束问题的Zoutendijk可行方向法可行方向法 起作用的约束起作用的约束不起作用的约束不起作用的约束（1）搜索方向）搜索方向非线性约束问题的非线性约束问题的Zoutendijk可行方向法可行方向法 搜索方向搜索方向迭代步长迭代步长 起作用约束可行方向法起作用约束可行方向法 迭代步长迭代步长搜索方向搜索方向Topkis Vein

13、ott 全约束可行方向法全约束可行方向法 迭代步长迭代步长搜索方向搜索方向梯度投影法梯度投影法)(xfP 2 x0)(2g x)(2g x)(1g x0)(1g2)(xfP x0)(2g x)(2g x)(1g x0)(1g)(xfP*x)(xf0)(222 xg0)(111 xg)(xf0)(222 xg0)(111 xg)(1xg00)()()(212211，xxxggf00)()()(112211，x xxggf解析搜索法：梯度投影法解析搜索法：梯度投影法kkTkkkTkkklkklfflfffffdxxxxdxx dxxx)()()()()(T)()()()()()()()()(1解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法解析搜索法：梯度投影法