健壮优化的介绍[...和我忘记的一小部分购物清单...]

如何确定新工作需要雇用多少人，究竟要填补什么，以及在哪里放置特定产品？ 业务规模越大，不确定性就越大，错误的代价也就越大。 战胜混乱并选择最佳解决方案是数据科学团队的任务之一。 由于数学是数据分析的基础，因此我们将从它开始。

在这篇文章中，我们将考虑具有不确定性的优化问题，并通过确定性凸问题对其进行近似。 这是鲁棒优化的主要技巧之一-一种使您能够应对对输入数据的更改过于敏感的优化问题的技术。

敏感性问题非常重要。 对于任务而言，解决方案的质量几乎取决于数据的变化，因此使用常规的随机优化会更容易。 但是，在具有高敏感性的任务中，这种方法会产生不好的结果。 在财务，供应链管理，设计和许多其他领域中有许多此类任务。

是的，这是一个帖子的示例，其中复杂性呈指数增长（已删除）。

“解决”优化问题意味着什么？

让我们从简短的提醒开始。

通常，优化任务如下所示：

$$

$$\ min_ {x \ in R ^ n} f（x）\\ s.t. \\ x \ in X$$

在这里 $$$f（x）$ 叫做目标函数 $$$X$ -有效集。

通过解决优化问题，我们可以说出这一点 $$$x ^ * \ X$ 为此执行：

$$

$$f（x）-f（x ^ *）\ geq 0，\ quad \ forall x \ in X$$

这是解决不确定性优化问题的标准概念。

有不确定性的优化问题是什么？

现在是时候想知道函数的来源了 $$$f（x）$ 和局限性 $$$X$ 。

分享非常有用

• 问题的结构逻辑（换句话说，使用什么功能），
• 技术限制（与人为逻辑或数据无关），
• 从数据评估的参数。

例如，一个业务人员来找我们，展示了线性编程问题：

$$

$$\ min_ {x \ in R ^ 2} 2.16 x_1 + 3.7 x_2 \\ s.t. \\ 0.973 x_1 + 2.619 x_2 \ leq 3.32 \\ x_1 \ geq 0，x_2 \ geq 0$$

您是第一次看到此任务。 一个男人也是如此（也许不是，但是穿着一件蓝色外套，一切都那么抽象！）。 您不知道变量的含义。 但是即使现在，我们也可以充满信心地说：

1. 任务很可能是线性的，因为有人决定了。 线性是一个人选择的结构。
2. 局限性 $$$x_1 \ geq 0，x_2 \ geq 0$ 是技术性的。 也就是说，它们来自“物理”而不是数据（例如，销售额不能为负）。
3. 比系数 $$$\ {0.973，2.619，3.32 \}$ 在限制中 $$$0.973 x_1 + 2.619 x_2 \ leq 3.32$ 在我们的示例中，是根据数据进行评估的。 也就是说，起初有人说该变量 $$$x_1$ 与变量相关 $$$x_2$ ，则认为该关系是线性的，最后，从数据中估计出耦合方程中的系数。 赔率也是如此。 $$$\ {2.16，3.7 \}$ 在目标函数中。

当我们谈论具有不确定性的任务时，我们将根据数据估算的参数精确地确定为不确定性。 我们不涉及技术限制或问题结构的初始选择。

回到我们的故事。 我们有一个线性问题，有人以某种方式估计了其中的系数。 如果我们对函数中系数的性质是正确的，那么实际上我们被要求针对事件发展的一种情况 （问题的特定实例）解决问题。

有时候这对我们来说足够了，我们只需解决即可。

但是，有时针对一种情况解决问题是一个愚蠢的想法（例如，如果解决方案对数据变化非常敏感）。

在这种情况下该怎么办，以及如何对数据中的不确定性建模？

首先，请注意，数据不确定性始终可以从目标函数转移到约束，反之亦然。 怎么做，看下切。

随机，在线，可靠的优化和产品列表

我们可以有许多不确定性场景，以及如何处理不确定性的选项。 我们用一个简单的例子说明几种标准方法。

我不知道受尊敬的读者的情况如何，但是我在这里结婚（成功）并定期去杂货店。 当然可以（通过冲动购买获得无害性）。 有时不仅到商店，还到有条件的欧尚（Auchan），那里较便宜，但距离较远。

我们将为这种情况建模：我们带着叶子去购物的时候来到了欧尚。

注意，第一个问题：如何建模？

输入：有关要购买的产品和所需数量的信息。

为了方便起见，我们可以将传单视为一些整数非负向量 $$$y \在Z _ + ^ n $$ 。

作为变量，我们分别采用一个整数非负向量 $$$x \在Z _ + ^ n $$ -我们最终将购买多少和什么产品（我们的解决方案）。

重点很小-承担某种目标作用 $$$f（x，y）$ ，表示我们在选择产品时犯了多少错误。

根据上下文的不同，功能的类型可能会发生变化，但是对此有一些基本要求：

• 功能介绍 $$$f（x，y）$ 应该有一个最小值 $$$x ^ * = \ arg \ min_ {x \ in R ^ n} f（x，y）= y$ （也就是说，在最佳状态下，我们将完全购买传单中的内容）
• 功能介绍 $$$f（x，y）$ 必须凸入 $$$x$ （最好是平滑的）-能够有效地计算 $$$分钟$ 。

因此，我们得到了问题：

$$

$$min_ {x \ in R ^ n} f（x，y）$$

现在想象叶子留在家中...

因此，仅此而已，我们进入了不确定性的任务世界。

那么如果在任务中该怎么办 $$$min_ {x \ in R ^ n} f（x，y）$ 我们未知 $$$y$ ？

答案还是取决于上下文。

随机优化

随机优化（通常）涉及

• 数据中的不确定性具有随机性。 完全了解非确定性参数值的概率分布
• 局限性包括不确定性

在我们的示例中，如果我们使用随机优化对其建模，我们会说

• 好的，我不知道传单上写的是什么，但是我已经沿着传单走了8年了，而且我对矢量的分布有足够的了解 $$$y$
• 即使我在选择上犯了一个错误（即 $$$x$ ），回到家，我发现了真正的 $$$y$ 并且，如果我完全安全的话，我会去Pyaterochka并在那里购买，尽管价格更高。
• 现在我会选择一个 $$$x$ ，这将使原始目标函数和可能的错误“罚款”中的某种汇总最小化。

这将导致我们完成以下任务：

$$

$$\ min_ {x \ in R ^ n} E_y [f（x，y）+ \ psi（y，z）] \\ s.t. \\ x + z \ geq y$$

请注意，在此任务中，我们实际上要做出两次决定：首先，我们负责在欧尚购买产品的主要决定 $$$x$ ，然后使用 $$$z$ 。

这种方法的主要问题是：

• 通常没有关于参数分布的信息。
• 局限性可能很严重（对于高风险的任务-死亡，毁灭，核武器或僵尸末日等）
• 并非总是能够“纠正错误”（一次做出决定），反之亦然，经常做出决定（在这种情况下，会出现许多嵌套的积分，并且很难计数）。

在线优化

在线优化是一个探索一致决策的框架。 在此框架中进行建模的标准方法之一是多臂匪，该问题已在Habré上发表过多次。

在我们的玩具示例中，我们将：

• 没有（从未使用过）传单
  
• 在家里，我们会因购买的那些产品而受到称赞/责骂（同时我们只能猜测所需的套装）
• 任务是尽快学会买食物以及她以前的，虚构的王子，母亲或她母亲最好的儿子朋友。

稳健的优化

稳健的优化是minimax解决方案思想的逻辑扩展。

理想情况下，我们现在应该做出一个无论情况如何始终可以接受的决定。 在苏联设计锅，铁和冰箱的人是在进行强大优化的前提下做到这一点的：即使该产品已被用作消灭核战后出现的突变体的主要工具，它也已经可以使用20年了（它也必须生存）。

此外，我希望将难题放入常规求解器中，并且他们不理解“对随机变量的任何实现”的限制（如果这些实现的数量有限）。

如果有传单问题，应立即做出决定，并在任何情况下均有效：

$$

$$\ min_ {x \ in R ^ n，t \ in R} t \\ s.t. \\ f（x，y）\ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

很明显，即使在这个玩具示例中，如果您不需要 $$$y$ ，那么就没有有意义的解决方案了。

那么，您如何处理此类任务？

使用LP任务示例构建可靠的任务版本

考虑具有不确定性的线性优化问题：

$$

$$\ min_ {x \ in R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

参量 $$$\开始{pmatrix} c ^ T，d \\ A，b \结束{pmatrix}$ 从数据中得出，并包括不确定性。

假设1：许多价值观（实现） $$$\开始{pmatrix} c ^ T，d \\ A，b \结束{pmatrix}$ 可以被参数化，即 有这样 $$$\开始{pmatrix} c_0 ^ T，d_0 \\ A_0，b_0 \结束{pmatrix}，\开始{pmatrix} c_1 ^ T，d_1 \\ A_1，b_1 \结束{pmatrix}，\点，\开始{pmatrix } c_k ^ T，d_k \\ A_k，b_k \ end {pmatrix}$ 任何数据实现 $$$\开始{pmatrix} c ^ T，d \\ A，b \结束{pmatrix}$ 位于集合中：

$$

$$\开始{pmatrix} c ^ T，d \\ A，b \结束{pmatrix} \ in U = \左\ {\开始{pmatrix} c_0 ^ T，d_0 \\ A_0，b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \开始{pmatrix} c_i ^ T，d_i \\ A_i，b_i \结束{pmatrix} | \ quad \ zeta \在Q \子集R ^ k \正确\}$$

在这里 $$$\开始{pmatrix} c ^ T_0，d_0 \\ A_0，b_0 \结束{pmatrix}$ 被称为“名义”数据，并且 $$$\开始{pmatrix} c ^ T_i，d_i \\ A_i，b_i \结束{pmatrix} \ quad（1 \ leq i \ leq k）$ -“转变”。



我们已经知道问题中的所有不确定性都可以通过限制来消除。 来吧

我们得到了问题

$$

$$\ min_ {x \ in R ^ n，t \ in R} t \\ st \\ c ^ Tx + d \ leq t，\ quad \ forall \ begin {pmatrix} c ^ T，d \ end {pmatrix} \在U \\ Ax \ leq b，\ quad \ forall \开始{pmatrix} A，b \结束{pmatrix} \在U \\ $$

健壮的任务版本

现在是时候进行鲁棒性优化中最酷的技巧之一了-如何从无限数量的限制过渡到有限数量的良好限制。

首先，考虑一个简单的例子

$$

$$Q = \ {\ zeta \ in R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

系统中的所有限制

$$

$$c ^ Tx + d \ leq t，\ quad \ forall \ begin {pmatrix} c ^ T，d \ end {pmatrix} \ in U \\ Ax \ leq b，\ quad \ forall \ begin {pmatrix} A， b \ end {pmatrix} \在U \\ $$

相同的类型-只是线性不等式。 学会与一个人一起工作-学习与每个人一起工作。

因此，我们考虑不平等类型的一种限制：

$$

$$a ^ Tx \ leq b \ quad \ forall（a，b）\ in U = \ {（a_0，b_0）+ \ sum_ {i = 1} ^ k \ zeta_i \ cdot（a_i，b_i）| \ quad \ zeta \ in Q \} \\（a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i）^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot（a_i ^ T x-b_i）\ leq b_0-a_0 ^ Tx \ quad \ forall \ zeta \ in Q \\ \ max _ {\ zeta \在Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot（a_i ^ T x-b_i）\ leq b_0-a_0 ^ Tx$$

让我解释一下发生了什么。

首先，我们将所有不确定的部分转移到不等式的左侧。 $$$\ zeta$ 。
之后，我们研究了最坏的情况 $$$x$ 他是他的）。
结果，我们得到了以下记录：

$$

$$g（x）= max _ {\ zeta \ in Q} f（x，\ zeta）\ leq b_0-a_0 ^ Tx$$

。

下一步是编写一个显式函数 $$$g（x）$ 。 为此，通过以下方法解决优化问题就足够了 $$$\ zeta$ 并替代最优 $$$\ zeta *$ ：

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i（a_i ^ Tx-b_i）= \ sqrt {\ sum_ {i = 1} ^ k（a_i ^ Tx -b_i）^ 2}$$

导致不平等：

$$

$$\ sqrt {\ sum_ {i = 1} ^ k（a_i ^ Tx-b_i）^ 2} + a_0 ^ Tx \ leq b_0$$

请注意，产生的不等式是凸的，并且任何 $$$x$ 让他满意，使他满意 $$$a ^ Tx \ leq b$ 对于任何实施 $$$（a，b）\以U$ ...

局限性 $$$\ sqrt {\ sum_ {i = 1} ^ k（a_i ^ Tx-b_i）^ 2} + a_0 ^ Tx \ leq b_0$ 称为约束的健壮版本 $$$a ^ Tx \ leq b \ quad \ forall（a，b）\ in U$ 。

这是鲁棒优化中的主要工作之一-通过有限的一组凸约束来逼近概率约束。

如何处理更复杂的（非线性）约束？

使用圆锥对偶性构造约束的健壮版本

许多标准非线性约束可以圆锥形表示（即 $$$Ax + b \以K$ 在哪里 $$$K$ 是一些封闭的凸锥）：

• 非负性 $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ in R ^ n _ +$
• 规范限制 $$$\ | x \ | _p \ leq p \ Quad \ leftrightarrow \ Quad \开始{pmatrix} x \\ p \ end {pmatrix} \ in K_p ^ n = \ left \ {（x，t）\ in R ^ n \次R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• 约束矩阵的正定性 $$$x_1F_1 + \点x_nF_n + G \ succeq 0$

回到强大的限制。

假设关于 $$$\ zeta$ 设法缩小为圆锥形

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i（a_i ^ Tx-b_i）\\ s.t \\ C \ zeta + d \ in K$$

我们为此问题构造了对偶。

不久前，我发表了一篇有关圆锥对偶性的文章 ，目的是为了减少对该文章中的技术的关注。

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx-b_1 \\ \点\\ a_k ^ Tx-b_k \ end {pmatrix} = 0_k \\ \ lambda \ in K ^ *$$

现在到了小事情-弱对偶定理：

$$

$$\ max _ {[\ zeta：\ quad C \ zeta + d \ in K]} \ sum_ {i = 1} ^ k \ zeta_i（a_i ^ Tx-b_i）\ leq \ min _ {\ lambda \ in G} \ lambda ^ Td \\其中\\ G = \左\ {\ lambda | \ quad C ^ T \ lambda + \开始{pmatrix} a_1 ^ Tx-b_1 \\ \点\\ a_k ^ Tx-b_k \结束{pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

因此，作为初始约束的稳健近似 $$$a ^ Tx \ leq b，\ quad（a，b）\ in U$ 可以使用限制

$$

$$\ lambda ^ Td \ leq b_0-a_0 ^ Tx \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \开始{pmatrix} a_1 ^ Tx-b_1 \\ \点\\ a_k ^ Tx-b_k \结束{pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

在哪里 $$$\ lambda$ 与相同的变量 $$$x$ 。

因此，我们为原始不等式建立了鲁棒约束。

结论

我们研究了通过一组好的凸约束近似逼近坏（随机）约束的技术。 例如，这在以下情况下很有用：

• 您不想自己编写算法，但是您使用的求解器不知道如何使用概率约束。
• 随机参数存在问题，而最佳参数对数据的波动非常敏感。
• 当然，还有不确定性的任务，其中所有限制都是严格的（错误的代价太高）