鲁棒优化(1)

“I work on planning under uncertainty. That's the big field as far as I'm concerned; that's the future.” - George Dantzig, 1999 on his 85thBirthday

参考资料主要是杨老师的鲁棒优化这门课的课件和下面这两本参考书。

• Panos Kouvelis、Gang Yu，《Robust Discrete Optimization and Applications》, Kluwer Academic Publishers,1996。
• A.Ben-Tal, L.El.Ghaoui, A.Nemirovski.《Robust Optimization》, Princeton University Press, 2009.

今天开启了鲁棒优化这门课的第一节，按照惯例都是介绍一下学科的背景和目录之类的

• 第1章 决策中处理不确定性的方法
• 第2章 离散鲁棒优化框架、应用与性能分析
• 第3章 鲁棒离散优化问题的计算复杂性结果
• 第4章 容易求解的鲁棒离散优化问题
• 第5章 难求解离散鲁棒优化问题的算法设计
• 第6章 连续鲁棒优化及其发展

感觉重点还是离散鲁棒优化相关问题。

决策：按照一定的准则或标准（偏好），在众多候选方案中选择方案的过程。

决策问题很广，常常借助数学模型来进行决策。

鲁棒优化方法主要解决决策中描述方案的不确定性问题。

引言这部分绝大部分都是介绍数学建模的基本知识，我就不多赘述了，下面主要说说鲁棒优化的提出过程。

鲁棒，robust，稳定性，就是围绕模型中随机因素展开的问题，不确定因素在问题中很常见：

• 价格、劳动力、生产费用、原材料供应等不确定性因素影响决策。
• 未来现金流的不确定性使长期投资决策变得困难。
• 产品开发项目中资源分配决策受开发任务（采用新的未经测试的原料、新的产品开发过程等）、市场对新产品的反应和增长、消费者喜好的潜在变化、竞争对手的反应（通过价格和/或引进新产品）、新的加工技术以及不确定的宏观经济条件（例如：通货膨胀条件影响顾客的购买行为）等不确定因素的影响。
• 设施选址决策受所考虑的选址范围中需求量的不确定性的影响。
• 决策中的鲁棒方法就是建立在这个基础之上的，它是刻画不确定性特征以及当不确定性出现进行决策的一种有效方法。

决策环境有三类：确定性环境、风险环境和不确定性环境。通过对决策环境的改变，我们依次提出确定性优化方法和随机优化方法，最后就引入了我们的鲁棒优化。

确定性优化方法

通过向一个决策模型的事例输入数据，就能够生成一个单目标（多目标）问题的“最优”决策。这种方法要么完全忽略了不确定性，要么用历史数据和趋势去预测未来。所选择事例的输入数据是对未来实现数据的一个最大可能估计。例如：考虑一个产品生成决策，为了满足消费者对不同产品的需求，并且考虑产品的生成费用和原料的供应情况，对于一个固定能力的生成工厂制定一个时段的生成计划，决策者要确定生产哪些产品以及相应产品的量，目标是最大化工厂的利润。在这个决策中，有很多不确定的输入数据；但是为了说明方便，我们只假设需求是不确定的。确定性优化方法的重点是用可利用的数据生成各种产品未来的一个需求量。然后把这些数据输入到决策模型中（线性规划模型可能最合适），得到这个具体输入实例各产品的最优产量。

确定性决策方法最大的弱点是没有意识到数据事例的似是而非的特点，而是“最大可能”的情景事例来生成“最优”决策，所生成的决策可能是次优的。尽管所做的决策对于“最有可能”的未来情景是“最优的”，不管未来实现的真正的情景如何，决策者必须承受所做决策带来的后果。若认为预测值能被所有的决策者接受，那通常是错误的。对于输入数据有很大的不确定性的决策环境，若对于未来情景不同于预测的“最大可能”情景没有一个正确的的判断，或者根本没有意识到这一点，那么任何决策方法都是不能接受的。

随机优化方法

确实认识到了多个数据事例在未来都可能会实现。但是在把这些数据输入到决策模型之前，要求决策者必须得到可能实现的这些事例明确的概率信息。通常决策模型会产生一个最大化（或最小化）一个期望性能度量的决策，期望是关于假设的概率分布的。多数情况下，为了便于求解或者其他一些技术原因，当输入数据中有多个不确定因素时，要假设这些不确定因素是独立分布的。把可能事例的概率信息和相关假设输入到决策模型之后，就会得到一个“随机优化”决策。这些决策的“最优性”的传统解释如下。最多的解释是长期运行最优性，如果决策者反复做相同的决策，并且数据事例按照假设的概率分布随机产生，从长期运行重复这一决策看，决策者能够实现最大性能。另一种解释是输入数据事例最优性。根据决策者建议的概率值，把各种事例情景加权生成一个输入数据情景的期望值，对于这个期望输入数据事例，用随机优化模型生成最优决策。

对于有不确定性的决策环境而言，随机优化方法因从多个角度不能满足决策者的需求而受到批评。首先，决策者要为未来的不同数据事例（情景）赋予一个概率值。对于决策者而言，为每个情景赋予发生概率或给出一个发生的概率分布绝非易事；尤其是当决策环境有多个相互影响的不确定因素时更是如此。当不确定因素是指其他公司、代理或者政府的未来行为，或者公众态度的优先权的变化时，用概率表示未来的情景是困难的。另一个不足是描述决策环境所做的分布假设不合适，例如，前面的单机调度问题，一些因素（机器或工具的状况、供应问题、工人的技术水平）是决定数据集合（工作的加工时间）的多个不确定因素，这样，相应的概率分布之间具有强的但是很难具体化的相关关系。

鲁棒决策的提出

通过对不确定条件下传统决策方法的详细解释和建设性的批判，得到了这类决策问题的关键要素。当前组织中的决策者大多数是风险厌恶的，他们会基于实现的情景进行事后评估，他/她们遇到的决策情景具有唯一性（非重复性）特征。这样，决策者所需要的不是对某个具体情景（最可能情景）的性能“最优”，也不是长期运行效果最好，而是对所有情景效果都不错的一个决策。按照我们的术语，在不确定性环境下，决策者想要的是一个鲁棒决策，该决策对所有的情景效果都不错，并且能够对冲掉所有可能情景的最坏可能。

• 最小最大准则（也称为绝对鲁棒准则），该准则最大（小）化所有未来输入数据情景获利（费用）的最小（大）值。最小最大准则基于最坏的情况总会发生，得到的结果具有很强的保守性。
• 最小最大后悔准则，根据后悔的不同定义有两个版本。这种准则的第一步是对于决策和输入数据情景的不同组合，计算相应的后悔值。后悔值可以定义为决策得到的利润（成本）与决策者在决策时能够知道发生那个输入数据情景采取最优决策得到的利润（成本）之差。另一种定义是前面这两个数值的比，即某一决策的利润（成本）与知道某一具体输入数据情景下的最优决策的利润（成本）之比，作为鲁棒决策与给定数据情景下最优决策偏离百分比的替代度量。对后悔值采用最小最大原则，选择最大后悔值最小的决策。对于前者，后悔值定义为两个值的差，我们称得到的决策为鲁棒偏离决策；对于后者，后悔值定义为两个值的比，我们称得到的决策为相对鲁棒决策。用后面这两个准则得到的决策具有较弱的保守性，因为它们根据事后最优决策的性能为参照标准，考虑了决策中失去机会的数量。不同鲁棒准则的正式定义在后续章节还有描述。

鲁棒优化方法

我们用基于情景的方法来描述决策模型中输入数据的不确定性。一个具体的输入数据情景表示决策模型中一些重要参数可能的实现（会有一个正的发生概率，但是这个概率可能是不知道的）。用情景来刻画输入数据的不确定性，决策者要描述决策环境中一些不确定因素与决策模型中输入参数集合之间的关系，这些模型参数会同时受这些因素中一个或多个的影响。采用情景的方法便于描述一些主要因素同时影响输入数据。鲁棒优化方法严格依赖于情景生成的过程，因为这样做，决策者对决策环境有一个直觉的认识。