最优化与最优控制补充变分幻灯片.ppt

《最优化与最优控制补充变分幻灯片.ppt》由会员分享，可在线阅读，更多相关《最优化与最优控制补充变分幻灯片.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化与最优控制补充变分第1页，共31页，编辑于2022年，星期六变分不等式实例变分不等式实例Wardrop平衡配流原则描述如下：平衡配流原则描述如下：在在起起终终点点之之间间所所有有可可供供选选择择的的路路线线中中，使使用用者者所所利利用用的的各各条条路路线线上上的的出出行行费费用用全全都都相相等等，而而且且不不大大于于未未被被利利用用路路线线上上的的出出行行费费用用。满满足足这这一一原原则则的的交交通通状状态态被被定定义义为为Wardrop平平衡衡状状态态，上上述述配配流流原原则则又又可可称称为为用用户户平平衡衡配配流流。Beckmann采用以下数学形式描述采用以下数学形式描述Wardro

2、p平衡状态：平衡状态：其中为平衡状态下其中为平衡状态下O-D对之间的出行费用。对之间的出行费用。，第2页，共31页，编辑于2022年，星期六变分不等式实例变分不等式实例在在路路段段费费用用是是流流量量的的严严格格增增函函数数的的假假定定下下，Dafermos（1980）将将城城市市交交通通网网络络均均衡衡流流问问题题改改写写为为变变分分不不等等式式问问题题，最最一一般般的的形形式式就就是是：寻寻找均衡路段流量找均衡路段流量，使得对所有，使得对所有有有其中其中其其中中 为为路路段段阻阻抗抗向向量量函函数数，它它是是流流量量的的严严格格增增函函数数，为为路路径径流流量量，为为O-D需需求求量量，代

3、代表表路路段段/路路径径关关联联矩矩阵阵，代代表表O-D对对/路路径径关关联联矩矩阵阵。在在路路段段费费用用是是流流量量的的严严格格增增函函数数的的假假定定下下，这这个个变变分分不不等式有唯一路段解。等式有唯一路段解。第3页，共31页，编辑于2022年，星期六1.1 变分不等式基本概念变分不等式基本概念变变变变分分分分不不不不等等等等式式式式广广广广泛泛泛泛应应应应用用用用于于于于各各各各种种种种问问问问题题题题的的的的数数数数学学学学建建建建模模模模，主主主主要要要要有有有有以以以以下下下下优点：优点：优点：优点：（1 1）变变变变分分分分不不不不等等等等式式式式问问问问题题题题给给给给出出

4、出出了了了了包包包包括括括括优优优优化化化化问问问问题题题题、互互互互补补补补问问问问题题题题、方程组问题和不动点理论在内的一些数学问题的一般描述。方程组问题和不动点理论在内的一些数学问题的一般描述。方程组问题和不动点理论在内的一些数学问题的一般描述。方程组问题和不动点理论在内的一些数学问题的一般描述。（2 2）变变变变分分分分不不不不等等等等式式式式问问问问题题题题与与与与等等等等价价价价的的的的优优优优化化化化问问问问题题题题之之之之间间间间的的的的关关关关系系系系是是是是非非非非常常常常重重重重要要要要的的的的，根根根根据据据据其其其其等等等等价价价价的的的的优优优优化化化化问问问问题题

5、题题，可可可可直直直直接接接接得得得得到到到到各各各各种种种种求求求求解解解解变分不等式的算法。变分不等式的算法。变分不等式的算法。变分不等式的算法。（3 3）变分不等式问题的唯一性证明非常简单。）变分不等式问题的唯一性证明非常简单。）变分不等式问题的唯一性证明非常简单。）变分不等式问题的唯一性证明非常简单。（4 4）变分不等式问题的几何解释非常直观。）变分不等式问题的几何解释非常直观。）变分不等式问题的几何解释非常直观。）变分不等式问题的几何解释非常直观。第4页，共31页，编辑于2022年，星期六现给出变分不等式问题的精确定义：现给出变分不等式问题的精确定义：设设为一维实值函数，定义为一维实

6、值函数，定义，则称，则称为一向量值函数。为一向量值函数。定定义义3.1有有限限维维变变分分不不等等式式问问题题（简简称称为为VIP）就就是是确确定定一一个个向向量量，使得，使得，（2.1）其中其中 是给定的连续向量值函数，是给定的连续向量值函数，是非空闭凸集。是非空闭凸集。第5页，共31页，编辑于2022年，星期六2.2.1优化问题优化问题一一般般优优化化问问题题的的特特征征是是：有有一一个个取取最最小小或或最最大大值值的的目目标标，同同时时满满足足一一定的约束。因此，优化问题可描述为：定的约束。因此，优化问题可描述为：（2.2）其中其中是特定的优化目标，为决策变量是特定的优化目标，为决策变量

7、的函数，的函数，是可行集。是可行集。定理定理2.1（最优性条件）（最优性条件）令令 是非空闭凸集是非空闭凸集 上的连上的连续可微函数，且续可微函数，且 ，若，若 是优化问题（是优化问题（2.2）的解，）的解，那么那么 也是也是VIP（2.1）的解。反之，当）的解。反之，当 伪凸时成立。伪凸时成立。1.2 与变分不等式相关的数学问题与变分不等式相关的数学问题第6页，共31页，编辑于2022年，星期六定定理理2.2如如果果在在上上是是连连续续可可微微的的,且且其其雅雅克克比比矩矩阵阵是是对对称称且且半半正正定定的的，则则存存在在一一个个实实值值函函数数满满足足，此此时时上上述述变变分分不不等等式式

8、问问题题的的解解也是下面优化问题也是下面优化问题的最优解。的最优解。第7页，共31页，编辑于2022年，星期六定义定义2.2令令是连续的，互补问题即确定是连续的，互补问题即确定，使得，使得互互补补问问题题是是定定义义在在非非负负卦卦限限上上由由等等式式和和不不等等式式构构成成的的系统。系统。定理定理2.3定义在定义在 上的上的VIP（2.1）和互补问题）和互补问题（2.4）（2.62.6）若都有解，则其解相同。）若都有解，则其解相同。2.2.2互补问题（互补问题（ComplementarityProblems，简称，简称CP）（2.4）（2.5）（2.6）第8页，共31页，编辑于2022年，星

9、期六2.2.3方程组（方程组（EquationSystems）定定义义2.3令令定定义义在在上上，方方程程组组问问题题指指的的是是确定确定，使得，使得。定理定理2.4向量向量是是VIP（2.1）的解，当且仅当）的解，当且仅当。2.2.4不动点问题（不动点问题（FixedPointProblems）定定义义2.4令令连连续续，不不动动点点问问题题就就是是确确定定，使使得得（2.12）第9页，共31页，编辑于2022年，星期六定定理理2.5向向量量是是VIP（2.1）的的解解，当当且且仅仅当当对对任任意意的的，是映射的不动点，即，是映射的不动点，即（2.13）其中其中是正交投影映射，即是正交投影映

10、射，即（2.14）第10页，共31页，编辑于2022年，星期六1.3 1.3 变分不等式在交通平衡配流问题中的应用变分不等式在交通平衡配流问题中的应用变分不等式在交通平衡配流问题中的应用变分不等式在交通平衡配流问题中的应用第11页，共31页，编辑于2022年，星期六第12页，共31页，编辑于2022年，星期六第13页，共31页，编辑于2022年，星期六第14页，共31页，编辑于2022年，星期六第15页，共31页，编辑于2022年，星期六随着人类社会的不断发展，实际问题的规模越来越大，结构越来越随着人类社会的不断发展，实际问题的规模越来越大，结构越来越复杂，涉及到对问题做出决策的人也越来越多，

11、而且这些决策者各自处复杂，涉及到对问题做出决策的人也越来越多，而且这些决策者各自处于不同的层次上。一般的，高一级决策机构（者）自上而下的对下一级于不同的层次上。一般的，高一级决策机构（者）自上而下的对下一级决策机构（者）行使某种控制、引导权，而下一级决策机构（者）在这决策机构（者）行使某种控制、引导权，而下一级决策机构（者）在这一前提下，亦可以在其管理职责范围内行使一定的决策权，虽然这种决一前提下，亦可以在其管理职责范围内行使一定的决策权，虽然这种决策权比较起来处于从属的地位。另外，在这种多层次决策系统中，每一策权比较起来处于从属的地位。另外，在这种多层次决策系统中，每一级都有自身的目标函数，

12、而越高层机构的决策目标越重要，越权威，越级都有自身的目标函数，而越高层机构的决策目标越重要，越权威，越具有全局性，因此最终的决策结果往往是寻求使各层决策机构之间达到具有全局性，因此最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案。某种协调的具体方案。2双层规划简介双层规划简介第16页，共31页，编辑于2022年，星期六在这一方案下，既可使最高层决策机构的目标达在这一方案下，既可使最高层决策机构的目标达到到“最优最优”，也可使作为上级决策的，也可使作为上级决策的“约束约束”的的较低层决策机构的目标在从属位置上相应达到较低层决策机构的目标在从属位置上相应达到“最优最优”，即下层决策

13、以上层决策变量为参数，一，即下层决策以上层决策变量为参数，一般称具有以上基本特征的决策问题为主从递阶般称具有以上基本特征的决策问题为主从递阶（或多层）决策问题。主从递阶决策问题最初是（或多层）决策问题。主从递阶决策问题最初是由由VonStackelberg于于1952年在研究市场经济问题年在研究市场经济问题时提出的，因此此问题有时候也称为时提出的，因此此问题有时候也称为Stackelberg问题，也就是通常所说的多层规划问题。问题，也就是通常所说的多层规划问题。第17页，共31页，编辑于2022年，星期六 双层规划是具有两个层次系统的规划与管理（控制）问双层规划是具有两个层次系统的规划与管理（

14、控制）问题。很多决策问题由多个具有层次性的决策者组成，这些决题。很多决策问题由多个具有层次性的决策者组成，这些决策者具有相对的独立性，即是说上层决策只是通过自己的决策者具有相对的独立性，即是说上层决策只是通过自己的决策去指导（或引导）下层决策者，不直接干涉下层的决策；策去指导（或引导）下层决策者，不直接干涉下层的决策；而下层决策者只需把上层的决策作为参数或约束，它可以在而下层决策者只需把上层的决策作为参数或约束，它可以在自己的可能范围内自由决策。如果组成这种上、下层关系不自己的可能范围内自由决策。如果组成这种上、下层关系不止一个时，这样的系统为多层决策系统。如果只有一个上、止一个时，这样的系统

15、为多层决策系统。如果只有一个上、下层关系时，这样的系统通常称为双层规划问题。由此可见，下层关系时，这样的系统通常称为双层规划问题。由此可见，双层规划问题虽然是多层决策系统的特殊形式，但它是最基双层规划问题虽然是多层决策系统的特殊形式，但它是最基本的形式。本的形式。第18页，共31页，编辑于2022年，星期六其中其中 由下述规划求得由下述规划求得（U）（L）上层决策者通过设置上层决策者通过设置 的值影响下层决策者。下层决策的值影响下层决策者。下层决策变量变量 是上层决策变量的函数，即是上层决策变量的函数，即 ,这个函数这个函数一般被称为反应函数。一般被称为反应函数。v一般来说，双层规划（简称一般

16、来说，双层规划（简称BPBP）模型具有如下形式）模型具有如下形式 第19页，共31页，编辑于2022年，星期六 双层规划系统按如下过程进行决策：上层给下双层规划系统按如下过程进行决策：上层给下层一定的信息，下层在这些信息下，按自己的利益层一定的信息，下层在这些信息下，按自己的利益或偏好做出反应（决策），上层再根据这些反应，或偏好做出反应（决策），上层再根据这些反应，做出符合全局利益的决策。上层给出的信息是以一做出符合全局利益的决策。上层给出的信息是以一种可能的决策形式给出的，下层的反应实际上是对种可能的决策形式给出的，下层的反应实际上是对上层决策的对策，这种对策在下层看来是最好的，上层决策的对

17、策，这种对策在下层看来是最好的，它显然与上层给出的信息有关，为了使整个系统获它显然与上层给出的信息有关，为了使整个系统获得得“最好的最好的”利益，上层必须综合下层的对策，调利益，上层必须综合下层的对策，调整自己的决策。整自己的决策。第20页，共31页，编辑于2022年，星期六 如果每个决策者都按规定的指标函数在其可能如果每个决策者都按规定的指标函数在其可能范围内做出决策，那么，双层决策系统可能描述为范围内做出决策，那么，双层决策系统可能描述为双层规划问题。如果每个决策者的指标函数由单个双层规划问题。如果每个决策者的指标函数由单个函数组成，这样的双层规划为双层单目标规划问题；函数组成，这样的双层

18、规划为双层单目标规划问题；如果有的决策者的指标函数是一组函数，这样的双如果有的决策者的指标函数是一组函数，这样的双层规划问题为双层多目标规划问题。层规划问题为双层多目标规划问题。第21页，共31页，编辑于2022年，星期六双层规划问题一般具有如下几大特点：双层规划问题一般具有如下几大特点：层次性层次性系统分层管理，下层服从上层，但下层有相对的自系统分层管理，下层服从上层，但下层有相对的自主权。主权。独立性独立性各层决策者各自控制一部分决策变量，以优化各自各层决策者各自控制一部分决策变量，以优化各自的目标。的目标。冲突性冲突性各层决策者有各自不同的目标，且这些目标往往是各层决策者有各自不同的目标

19、，且这些目标往往是相互矛盾的。相互矛盾的。优先性优先性上层决策者优先做出决策，下层决策者在优化自己上层决策者优先做出决策，下层决策者在优化自己的目标而选择策略时，不能改变上层的决策。的目标而选择策略时，不能改变上层的决策。第22页，共31页，编辑于2022年，星期六自主性自主性上层的决策可能影响下层的行为，因而部分地上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内，下层有自主决策权。为，在上层决策允许范围内，下层有自主决策权。制约性制约性下层的决策不但决定着自身目标的实现，而且下

20、层的决策不但决定着自身目标的实现，而且也影响上层目标的实现，因此上层在选择策略优化自己的也影响上层目标的实现，因此上层在选择策略优化自己的目标时，必须考虑到下层可能采取的策略对自己的不利影目标时，必须考虑到下层可能采取的策略对自己的不利影响。响。依赖性依赖性各层决策者的容许策略集通常是不可分离的，各层决策者的容许策略集通常是不可分离的，形成一个相关联的整体。形成一个相关联的整体。第23页，共31页，编辑于2022年，星期六第24页，共31页，编辑于2022年，星期六第25页，共31页，编辑于2022年，星期六第26页，共31页，编辑于2022年，星期六第27页，共31页，编辑于2022年，星期六第28页，共31页，编辑于2022年，星期六第29页，共31页，编辑于2022年，星期六第30页，共31页，编辑于2022年，星期六第31页，共31页，编辑于2022年，星期六