鲁棒优化导论与应用

作者简介

内容简介

第1章 鲁棒优化简介
　　实际优化问题的参数（数据）往往带有一定的误差.这些误差可以是过时的参数引起的（解优化问题时，使用的参数已经是旧的），也可以是测量或估计参数时产生的;还有些误差是由于硬件无法准确执行优化问题的解（它等同于人工的参数误差）引起的.在某些优化应用中，很小的参数误差可能导致原问题的解变得毫无意义和不切实际.于是，需要寻找一套优化方法求解深受参数误差困扰的优化问题，有效地找到鲁棒解使得它能消除参数不确定性的影响.鲁棒优化就是一门提供这些方法的基础与应用学科.
　　1.1 鲁棒优化问题
　　1.1.1 鲁棒优化模型
　　鲁棒优化问题是具有参数不确定性的问题.假设目标函数f0:RN→R，约束函数fm:RN×Um→R，m=1，2， ，M，则鲁棒优化问题可以写成（见文献[1]）
　　(1.1)
　　我们不失一般性地假设：目标函数的参数是确定的；否则，目标函数用极大值代替，并且使用它的等价上图形式表示，即mint使得在问题(1.1)的约束中，不等式的右边不含不确定的参数.
　　特别地，当U1= =UM=U时，问题(1.1)则化为
　　(1.2)
　　显然，问题(1.1)的可行集是
　　(1.3)
　　F中的任意一点称为鲁棒可行解.如果
　　(1.4)
　　则称为鲁棒最优解.类似地，可以定义鲁棒局部最优解.
　　特别地，当（Zm称为参数扰动集合），m=1，2， ，M，则问题(1.1)是鲁棒线性规划问题：
　　(1.5)
　　这里Pm是确定的矩阵参数.
　　如果f0是凸函数，且对任意给定um∈Um，fm(x，um)是关于x的凸函数，m=1，2， ，M，则问题(1.1)是具有无穷多个约束的凸优化问题.注意，supum∈Umfm(x，um)是关于x的凸函数.因此，问题(1.1)的等价形式
　　(1.6)
　　也是凸的.
　　类似上述问题，问题(1.5)可改写为
　　(1.7)
　　假设参数扰动集合Zm是容易计算的（例如，它可被有限个线性矩阵不等式等价地刻画）.那么，易知gm(x)不仅是凸的，而且集合是容易计算的.因此，问题(1.7)也是容易计算的.
　　一般而言，鲁棒优化需要处理以下两类问题：确认问题(1.1)的计算复杂度（例如，容易计算、NP-难或计算复杂度未知），以及如何求解；如何定义有意义且切合实际应用的不确定集合Um(m=1，2， ，M).
　　1.1.2 鲁棒线性规划问题
　　考虑以下鲁棒线性规划问题
　　(1.8)
　　其中，不确定集合U定义为
　　(1.9)
　　在式(1.9)中，名义值[A0，b0]和基[Al，bl](l=1，2， ，L)，是给定的矩阵；ζ和Z分别是扰动向量和扰动集合.因此，问题(1.8)的约束可写为
　　(1.10)
　　亦即
　　(1.11)
　　1.一般形式不确定集合的特例
　　约束(1.10)的形式比较一般.例如，半无穷约束
　　(1.12)
　　是M×N矩阵，b是M维向量可改写为.其中，定义为
　　(1.13)
　　以及.在式(1.13)中，em代表M维单位矩阵的第m列， m=1，2， ，M.
　　又如，以下约束
　　(1.14)
　　等价.其中，定义为
　　(1.15)
　　再如，考虑以下条件
　　(1.16)
　　可改写为
　　(1.17)
　　以及
　　(1.18)
　　这里.
　　2.不确定集合的假设
　　不难证明一般的鲁棒线性约束
　　(1.19)
　　等价于
　　(1.20)
　　其中，是A的第m行向量，Um是U到第m个约束的参数空间的投影，即
　　(1.21)
　　另外，鲁棒线性约束(1.20)中的Um可改为它的闭凸包
　　(1.22)
　　即式(1.22)等同于式(1.20).因此，我们可不失一般性地做以下假设（见文献[2]、[3]）.
　　假设1.1.1 鲁棒线性约束(1.20)中的Um是闭凸集，以及式(1.19)的不确定集合U等于U1× ×UM.
　　若式(1.19)中的不确定集合如式(1.9)所给定，则U可替换为U1× ×UM，且
　　(1.23)
　　m=1，2， ，M，以及参数扰动集合Zm是闭凸的（它与U如何投影到Um有关）.例如，
　　(1.24)
　　等价于
　　(1.25)
　　其中，m和δTm分别是和Δ的第m行向量，参数扰动集合
　　(1.26)
　　另外，我们还可以假设：
　　假设1.1.2 鲁棒线性规划问题(1.8)每个约束中的扰动集合是独立的.
　　1.2 典型案例——小误差与大变化
　　某医药公司生产药物1和药物2两类药物，它们均含有有效成分A.有效成分A可以从市面上销售的原材料I和原材料II中提取.药物生产参数、原材料数据和资源数据列在表1.1～表1.3中.公司的目的是寻求某生产计划使利润极大化（见文献[2]、[4]）.
　　表1.1 药物生产参数
　　表1.2 原材料数据
　　表1.3 资源数据
　　1.2.1 药物生产问题的线性规划模型
　　假设w和x分别代表购得的原材料I和原材料II的重量（以kg计），y和z分别代表生产的药物1和药物2的数量（以千盒计）.根据给定的数据，极小化问题的目标函数是负收益
　　(1.27)
　　其中，f1(w，x，y，z)是支出函数，
　　(1.28)
　　包括购买原材料费用与运营费用.f2(w，x，y，z)是收入函数，