|
关于我们
 新书资讯 新书推荐 |
鲁棒优化 [以]阿哈龙·本-塔尔 [美]洛朗·艾尔·加豪伊 [美]阿尔卡迪·涅米洛夫斯基 ![鲁棒优化 [以]阿哈龙·本-塔尔 [美]洛朗·艾尔·加豪伊 [美]阿尔卡迪·涅米洛夫斯基](http://p.ceeol.cn/pic//uploadfile/202407/9787111754978.jpg)
定 价：139 元
9 7 7 8 5 7 4 1 9 1 7 1 8 
本书通过鲁棒优化的核心原理和应用，揭开不确定性的神秘面纱，为读者提供应对不可预测的挑战所需的见解和工具。作者首先简要介绍了不确定线性规划，然后深入分析了适当不确定性集的构建与经典机会约束（概率）方法之间的相互联系。接着，提出了针对不确定的锥二次优化和半定优化问题以及动态（多阶段）问题的鲁棒优化理论。最后，通过来自金融、物流和工程等不同领域的真实案例研究说明了鲁棒优化的多功能性和相关性。本书是从事不确定性优化和决策工作的人员的书籍，也是该方向很好的研究生教科书。
在数学学科领域，鲁棒优化与凸优化、分式优化、多目标优化等优化理论具有相同的重要地位。在经济、人工智能、通信、信号处理、电气自动化等领域，做出稳健的决策和得到可靠的分析结果至关重要。然而，随着影响决策和分析结果的因素不断增加，决策的稳健性和分析结果的可靠性难以保证。鲁棒优化为获得稳健决策和可靠分析结果提供了数学理论基础，在经济、人工智能、通信、信号处理、电气自动化等领域的作用和重要性日益凸显。目前国内有凸优化、分式优化和多目标优化相关书籍。但至今，还未出版一本系统性和权威性的鲁棒优化书籍。随着鲁棒优化重要性不断增加，亟须出版一本鲁棒优化书籍。鲁棒优化为求解受不确定性影响的优化问题提供了理论和方法，已经在实际应用中被证明非常有用。本书由鲁棒优化的理论奠基人所写，是一本全面讲述鲁棒优化的书。
前言
不确定让人不舒服，可确定又是荒谬的。 ——谚语 这本书致力于讨论鲁棒优化——一种用于处理不确定数据优化问题的特定及相对新颖的方法。此前言的第一个目标是让读者更清楚地理解以下两个问题： ●什么是数据不确定性，以及为什么要专门对它进行处理？ ●在鲁棒优化中如何处理这一现象，以及这种处理方法和那些对不确定数据进行处理的传统方法相比如何？ 第二个目标是概述本书主题以及描述相关内容。 A. 优化中的数据不确定性 在本书中，我们打算解决的第一个问题是潜在现象（数据不确定性）是否值得专门处理。为了回答这个问题，考虑一个简单的示例——来自著名的NETLIB库中的问题PILOT4。这是一个线性规划问题，具有1000个变量和410个约束条件，其中一个约束条件（#372）是 aTx≡-1579081x826-8598819x827-188789x828-1362417x829-1526049x830- 0031883x849-28725555x850-10792065x851-019004x852-2757176x853- 12290832x854+717562256x855-0057865x856-3785417x857-7830661x858- 122163055x859-646609x860-048371x861-0615264x862-1353783x863- 84644257x864-122459045x865-4315593x866-1712592x870-0401597x871+ x880-0946049x898-0946049x916≥b≡23387405（C） 根据CPLEX报告，该问题的最优解x*的相关非零坐标如下： x*826=2556112787181108x*827=6240488912232100x*828=3624613324098961 x*829=1820205065283259x*849=1743970389573037x*870=1425000176680900 x*871=2591000731692178x*880=1049583199274139 注意，机器保真度x*使式（C）为等式。 我们可以观察到，式（C）中的大多数系数是“丑陋的实数”，如-1579081或-84644257。这类系数（PILOT4也不例外）通常描述某些技术设备/过程、预测未来需求等，因此很难确切地知道它们的值。可以很自然地假设，“丑陋的实数”实际上是不确定的——它们与相应数据的“真实”值相符，精度最多在3～4位之间。唯一例外的是x880的系数1，可以肯定的是，它可能反映了问题的结构，因此是严谨的。 假设a的不确定项是系数a~“真实”向量的未知项中精度为01%的近似值，让我们看看这种不确定性在x*情况下对“真实”约束a~Tx≥b的影响是什么。情况如下： ●在系数a~与我们的不确定性为01%的假设相一致的所有向量中，a~Tx*-b的最小值＜-1049；换句话说，对约束条件的违背达到不等式右侧的45倍。 ●将上述最坏情况下的违背视为“最差情况”（为什么所有不确定系数的真实值应与式（C）中“最危险”的值不同？），考虑一种不那么极端的违背处理。具体来说，假设式（C）中不确定系数的真实值是通过随机扰动aja~j=(1+ξj)aj从“标准值”［如式（C）所示］获得的。aja~j=(1+ξj)aj在范围为［-0001,0001］的“相对扰动”ξj上是独立且均匀分布的。典型的相对违背可以定义如下： V=maxb-a~Tx*b,0×100% 在x*下，“真实”（现在为随机）约束a~Tx≥b的相对违背是多少？答案几乎和最坏的情况一样糟糕（见表1）。 表1PILOT4中约束372的相对违背（不确定数据中扰动为01%的1000个元素样本） Prob{V>0} Prob{V>150%} Mean(V) 0.50 0.18 125% 我们看到，“明显不确定”的数据系数的扰动非常小（仅01%），这使得“标准”最优解x*严重不可行，因此实际上毫无意义。 文献\[7\]的“案例研究”报告中显示，我们刚才描述的现象并不例外——在90个NETLIB线性规划问题中，有13个“丑陋”系数的001%扰动导致某些约束违背，在标准最优解中评估超过50%。在这13个问题中，有6个问题的约束违背幅度超过100%，在PILOT4（“冠军”）中，其规模高达210000%，也就是说，达到数据中的相对扰动的7个数量级。 本书中介绍的应用于NETLIB问题的技术可以使人们通过将标准最优解传递给鲁棒最优解来消除前文所述的现象。在01%的不确定性下，对于NETLIB中的每一个问题，这种“对不确定性的免疫”（从标准解到鲁棒解时目标值的增加）的代价不到1%（详情见文献\[7\]）。 从概述的案例研究和许多其他示例中可得出以下几个观察结果。 A.实际优化问题的数据往往是不确定的——不知道问题解决时的确切时间。数据存在不确定性的原因包括：由于不可能准确测量/估计代表物理系统/技术过程/环境条件等特征的数据项而产生的测量/估计错误等。 实现过程中的错误来自无法完全按照计算的方式实现解。例如，无论上述PILOT4中的标准解x*中的“实际”项是什么——物理系统的控制输入、用于各种目的分配的资源等——很显然它们无法达到与计算时相同的高精度。实现错误的影响，如x*j(1+j)x*j，就好像没有实现错误一样，但PILOT4约束中的系数aij受aij(1+j)aij的扰动。 B.在优化的实际应用中，人们不能忽视这样一种可能性，即使数据中的一个小的不确定性，也有可能使标准最优解在实际中失去意义。 C.因此，在优化中，确实需要一种能够在数据不确定情况下，检测严重影响标准最优解质量的方法，并在这些情况下生成一个对数据不确定影响产生免疫的鲁棒解。 鲁棒优化提供了满足这种需求的方法，同时这也是本书的内容。 B.鲁棒优化——范式 为了解释鲁棒优化（RO）的范式，我们首先讨论线性规划的特殊案例——通用优化问题，这可能是最知名以及在应用中最常用的。除了它的重要性，这个通用问题也非常适合我们目前的目的，因为线性规划（LP）程序minx{cTx:Ax≤b}的结构和数据是清楚的。给定规划的形式，结构是约束矩阵A的大小，而数据则由(c,A,b)中的数值组成。在鲁棒优化中，将不确定LP问题定义为在给定不确定性集U中数据(c,A,b)变化的情况下，一种通用结构的LP程序的集合{minx{cTx:Ax≤b}:(c,A,b)∈U}。后者总结了解决问题时可用的“真实”数据的所有信息。从概念上讲，最重要的是要解决不确定LP问题意味着什么。这个问题的答案，正如鲁棒优化在其最基本的形式中所提及的，取决于三个隐含的“决策环境”假设。 A.1.决策向量x中的所有项都表示“此时此地”的决策：在实际数据“显示”之前，它们应作为解决问题的结果而获得特定的数值。 A.2.当且仅当实际数据在预先指定的不确定性集U的范围内时，决策者对所做出决策的结果负责。 A.3 问题中不确定LP的约束是“严格的”——当数据在U内时，决策者不能容忍约束违背的行为。 这些假设直接决定了对不确定问题的“不确定性免疫”解的定义。事实上，根据A.1，这样的解应该是一个固定的向量，根据A2和A3，无论U内的数据实现如何，这些约束条件都应保持可行；我们称其为鲁棒可行解。因此，在我们的决策环境中，一个不确定问题有意义的解就是它的鲁棒可行解。在这样的解中，仍然需要决定如何解释目标的值（也可能是不确定的）。应用到目标时，“以最坏情况为导向”的理念使我们很自然地通过原始目标的确定值来量化一个鲁棒可行解的质量，也就是通过它的最大sup{cTx：(c,A,b)∈U}。因此，最优鲁棒可行解就是解决下列优化问题的可行解： minxsup(c,A,b)∈UcTx：Ax≤b,(c,A,b)∈U 或者，以下优化问题的可行解： minx,t{t：cTx≤t,Ax≤b，(c,A,b)∈U}（RC） 后一个问题称为原始不确定问题的鲁棒对等（RC）。RC的可行/最优解称为不确定问题的鲁棒可行/最优解。鲁棒优化方法（在其最简单的版本中）建议与一个不确定问题的鲁棒对等相关联，并将鲁棒最优解作为我们“实际生活”的决策。 在这一点上，将RO范式与更传统的方法进行比较，特别是将优化中的数据不确定性处理方法与随机优化和灵敏度分析进行比较，是具有指导意义的。 鲁棒优化与随机优化。在随机优化（SO）中，不确定的数值数据被假定为随机数据。在最简单的情况下，这些随机数据服从事先已知的概率分布，而在更高级的设置中，分布仅部分已知。一个不确定的LP问题再次与一个确定的对等问题相关，特别是与下列机会约束问题相关机会约束的概念可以追溯到ACharnes、WWCopper和GHSymonds于1958年发表的论文（见文献\[40\]）。机会约束设置的另一种选择是，我们希望在原始约束的某些部分中优化目标的期望值（后者可以包含违反不确定约束的惩罚项）。然而，这种方法关注的是“软”约束，而我们主要感兴趣的是硬约束。： minx,t{t：Prob(c,A,b)~P{cTx≤t,Ax≤b}≥1-}（ChC） 其中＜＜1是给定的容差，P是数据(c,A,b)的分布。当此分布仅部分已知时——众所周知，P属于数据空间上概率分布的给定集合P——上述设置被模糊的机会约束设置所取代， minx,t{t:Prob(c,A,b)~P{cTx≤t，Ax≤b}≥1-，P∈P}（Amb） SO方法似乎没有面向最坏情况的RO方法保守。然而，这一结论的前提是，如果不确定数据确实具有随机性，如果我们足够聪明地指出相关的概率分布（或者至少是真实数据所属的一个“狭窄”分布族），如果我们确实准备接受由机会约束给出的概率保证。在信号处理、业务系统分析与综合等应用中，上述三个条件确实得到了满足事实上，在这些领域中，随机因素（如信号处理中的观测噪声或服务系统中的间隔/服务时间）具有随机性质，其分布或多或少易于识别，尤其是当我们有理由相信随机数据下的不同组成部分（如观测噪声中的不同项，或单个到达间隔和服务时间）相互独立时。在这种情况下，识别数据分布可简化为识别一系列低维分布，这是相对容易的。此外，所讨论的系统旨在长期为许多客户提供服务，因此概率保证是有意义的。例如，每天有成千上万的用户发送/接收电子邮件或联系呼叫中心，对服务水平的概率描述（电子邮件丢失的概率，或因操作员的回应时间很长而无法接受的概率）很有意义，从长远来看，一定比例的用户/客户会不满意。。与此同时，在许多应用中，上述三个“如果”都过于严格。考虑个别问题的测量/估计错误，例如PILOT4。即使假设为PILOT4准备数据项确实涉及一些随机的东西，我们也许可以考虑在给定真实数据的情况下标准数据的分布，而不
阿哈龙·本-塔尔（Aharon Ben-Tal） 以色列理工学院荣誉教授。研究领域：鲁棒优化、连续优化。他获得了众多的荣誉和奖项，其中包括：2007年欧洲金奖，2009年美国运筹学和管理学研究协会会士，2015年美国工业与应用数学学会会士。
洛朗·艾尔·加豪伊（Laurent El Ghaoui） 加州大学伯克利分校教授。研究领域：鲁棒优化，机器学习和统计。他于1998年获得法国国家科学研究院颁发的铜牌奖章；于2000年获得美国国家科学基金会颁发的杰出青年学者成就奖（CAREER）；于2001年获得大川情报通信基金颁发的大川研究助成奖（Okawa Foundation Research Grant）；于2008年获得美国工业与应用数学学会颁发的SIAM活动组优化奖（Activity Group Optimization Prize）。 阿尔卡迪·涅米洛夫斯基（Arkadi Nemirovski） 美国国家工程院院士、美国艺术与科学学院院士和美国国家科学院院士。现为佐治亚理工学院教授。研究领域：凸优化、非参数统计、运筹学与管理学。为表彰他对以上领域做出的贡献，先后获得富尔克森奖（1982年）、丹齐克奖（1991年）、维纳应用数学奖（2019年）、约翰·冯·诺伊曼理论奖（2003年）。
译者序
前言 第一部分鲁棒线性优化 第1章不确定线性优化问题及其鲁棒对等2 1.1线性优化中的数据不确定性2 1.1.1示例介绍3 1.1.2数据不确定性及其后果3 1.2不确定线性问题及其鲁棒对等4 1.2.1鲁棒对等的更多信息7 1.2.2未来10 1.3鲁棒对等的易处理性11 1.3.1策略11 1.3.2式（1.3.6）的易处理表示：简单情况13 1.3.3式（1.3.6）的易处理表示：一般情况14 1.4非仿射扰动16 1.5练习17 1.6备注18 第2章标量机会约束下的鲁棒对等近似问题19 2.1如何指定一个不确定性集19 2.2机会约束及其保守易处理近似20 2.2.1模糊机会约束21 2.3标量机会约束的保守易处理近似：基本示例21 2.3.1实例：单期投资组合选择问题25 2.3.2实例：蜂窝通信27 2.4扩展32 2.4.1有界扰动情况下的改进35 2.4.2实例38 2.4.3更多实例43 2.4.4总结46 2.5练习48 2.6备注49 第3章不确定LO问题的全局鲁棒对等51 3.1全局鲁棒对等——动机和定义51 3.2GRC的计算易处理性52 3.3实例：天线阵列的综合问题54 3.3.1建立模型54 3.3.2标准解：梦想和现实56 3.3.3对不确定性的免疫能力58 3.4练习60 3.5备注60 第4章关于标量机会约束的保守易处理近似61 4.1标量机会约束的保守凸近似的鲁棒对等表示61 4.2机会约束的Bernstein近似62 4.2.1Bernstein近似：基本观察62 4.2.2Bernstein近似：对偶化63 4.2.3Bernstein近似：主要结果64 4.2.4Bernstein近似:示例65 4.3在风险与收益方面从Bernstein近似值到条件值68 4.3.1基于生成函数的近似方案68 4.3.2Γ的鲁棒对等表示69 4.3.3风险条件下生成函数和条件值的最优选择70 4.3.4易处理的问题72 4.3.5向量不等式的扩展73 4.3.6在Bernstein近似和CVaR近似之间架起桥梁74 4.4优化80 4.4.1优化定理82 4.5超出独立线性扰动的情况83 4.5.1相关线性扰动83 4.5.2修正85 4.5.3利用协方差矩阵87 4.5.4说明89 4.5.5二次扰动的机会约束的扩展91 4.5.6利用域和矩信息94 4.6练习104 4.6.1混合不确定性模型106 4.7备注111 第二部分鲁棒锥优化 第5章不确定锥优化：概念114 5.1不确定锥优化：初步研究114 5.1.1锥规划114 5.1.2不确定锥问题及其鲁棒对等115 5.2不确定锥问题的鲁棒对等：易处理性116 5.3不确定锥不等式RC的保守易处理近似117 5.4练习119 5.5备注119 第6章具有易处理鲁棒对等的不确定锥二次问题121 6.1一般可解情况：场景不确定性121 6.2可解情况Ⅰ：简单的区间不确定性122 6.3可解情况Ⅱ：非结构化范数有界不确定性122 6.4可解情况Ⅲ：具有非结构化范数有界不确定性的凸二次不等式126 6.5可解情况Ⅳ：简单椭球不确定性的锥二次不等式127 6.5.1具有简单椭球不确定性的不确定锥二次不等式的鲁棒对等的半定表示130 6.6实例：鲁棒线性估计131 6.7练习135 6.8备注135 第7章不确定锥二次问题的鲁棒对等近似136 7.1结构化范数有界不确定性136 7.1.1不确定最小二乘不等式鲁棒对等的近似137 7.1.2具有结构化范数有界不确定性的最小二乘不等式——复数情况140 7.1.3从不确定最小二乘到不确定锥二次不等式144 7.1.4具有结构化范数有界不确定性的凸二次约束146 7.2∩-椭球不确定性的情况149 7.2.1不确定最小二乘不等式鲁棒对等的近似149 7.2.2从不确定最小二乘到不确定锥二次不等式151 7.2.3带∩-椭球不确定性的凸二次约束152 7.3练习154 7.4备注154 第8章具有易处理鲁棒对等的不确定半定问题155 8.1不确定半定问题155 8.2不确定半定问题鲁棒对等的易处理性156 8.2.1非结构化范数有界扰动157 8.2.2应用：鲁棒的结构设计158 8.2.3鲁棒控制中的应用166 8.3练习169 8.4备注169 第9章不确定半定问题的鲁棒近似170 9.1具有结构化范数有界不确定性的不确定半定问题鲁棒对等的易处理紧近似170 9.1.1具有结构化范数有界扰动的不确定线性矩阵不等式170 9.1.2应用：回顾李雅普诺夫稳定性分析/综合171 9.2练习176 9.3备注177 第10章近似机会约束的锥二次不等式和线性矩阵不等式178 10.1机会约束的线性矩阵不等式178 10.1.1近似机会约束的线性矩阵不等式：初步研究178 10.2近似方案182 10.2.1基于模拟的式（10.2.4）的证明185 10.2.2修正187 10.2.3实例：重新审视例8.2.7189 10.3高斯优化190 10.4机会约束线性矩阵不等式：特殊情况193 10.4.1对角情况：机会约束线性优化194 10.4.2箭头情况：机会约束锥二次优化198<
你还可能感兴趣
我要评论
|
