首页 > 代码库 > 多面体与优化

多面体与优化

2024-07-02 15:41:35   223人阅读

　　多面体和优化有很大的关系，很多实际问题都可以形式化成和多面体或多面体函数相关的问题。此外，若一个问题的约束是多面体，则往往可以设计出比一般凸约束问题解法更好的优化算法，之前我们已经碰到过一些：

  1. 凹函数f<script id="MathJax-Element-1" type="math/tex">f</script> 若在凸集C<script id="MathJax-Element-2" type="math/tex">C</script> 上不是常数函数，那么只可能在C<script id="MathJax-Element-3" type="math/tex">C</script> 的相对边界上取得最小值(命题1.3.4)。
  2. 线性函数或凸二次函数f<script id="MathJax-Element-4" type="math/tex">f</script> 在多面体C<script id="MathJax-Element-5" type="math/tex">C</script> 上有下界，那么f<script id="MathJax-Element-6" type="math/tex">f</script> 可在C<script id="MathJax-Element-7" type="math/tex">C</script> 上取得最小值(命题1.4.19)。

　　这一节我们更深入地介绍多面体在优化里的应用，尤其是线性规划(线性函数在多面体上的最小化问题)。线性规划里有一个经典结果：若多面体C<script id="MathJax-Element-8" type="math/tex">C</script> 至少有一个极点且线性函数f<script id="MathJax-Element-9" type="math/tex">f</script> 在C<script id="MathJax-Element-10" type="math/tex">C</script> 上可取得最小值，那么该最小值必然可在C<script id="MathJax-Element-11" type="math/tex">C</script> 的某些极点上取到(当然也可以在非极点上取到)。事实上，这是下面这个命题的特例，这里f<script id="MathJax-Element-12" type="math/tex">f</script> 是凹函数，C<script id="MathJax-Element-13" type="math/tex">C</script> 是闭凸集。

　　命题2.4.1：集合C<script id="MathJax-Element-14" type="math/tex">C</script> 是Rn<script id="MathJax-Element-15" type="math/tex">\mathbb{R}^n</script> 的闭凸子集且至少有一个极点，若凹函数f:C?R<script id="MathJax-Element-16" type="math/tex">f: C \mapsto \mathbb{R}</script> 在C<script id="MathJax-Element-17" type="math/tex">C</script> 上可取得最小值，那么该最小值必然可在C<script id="MathJax-Element-18" type="math/tex">C</script> 的某些极点上取到。

　　证明：设x?∈C<script id="MathJax-Element-19" type="math/tex">\boldsymbol{x}^* \in C</script> 且f<script id="MathJax-Element-20" type="math/tex">f</script> 在x?<script id="MathJax-Element-21" type="math/tex">\boldsymbol{x}^*</script> 处取得最小值。若x?∈ri(C)<script id="MathJax-Element-22" type="math/tex">\boldsymbol{x}^* \in ri(C)</script> ，由命题1.3.4知f<script id="MathJax-Element-23" type="math/tex">f</script> 是C<script id="MathJax-Element-24" type="math/tex">C</script> 上的常数函数，那么显然f<script id="MathJax-Element-25" type="math/tex">f</script> 可在C<script id="MathJax-Element-26" type="math/tex">C</script> 的某些极点上取到最小值。若x??ri(C)<script id="MathJax-Element-27" type="math/tex">\boldsymbol{x}^* \not \in ri(C)</script> ，由命题1.5.6的结论知存在超平面H1<script id="MathJax-Element-28" type="math/tex">H_1</script> 正常分离x?<script id="MathJax-Element-29" type="math/tex">\boldsymbol{x}^*</script> 和C<script id="MathJax-Element-30" type="math/tex">C</script> 。由于x?∈C<script id="MathJax-Element-31" type="math/tex">\boldsymbol{x}^* \in C</script> ，故H1<script id="MathJax-Element-32" type="math/tex">H_1</script> 包含x?<script id="MathJax-Element-33" type="math/tex">\boldsymbol{x}^*</script> ，于是H1<script id="MathJax-Element-34" type="math/tex">H_1</script> 不包含C<script id="MathJax-Element-35" type="math/tex">C</script> ，那么集合C∩H1<script id="MathJax-Element-36" type="math/tex">C \cap H_1</script> 的维度比C<script id="MathJax-Element-37" type="math/tex">C</script> 小。

　　若x?∈ri(C∩H1)<script id="MathJax-Element-38" type="math/tex">\boldsymbol{x}^* \in ri(C \cap H_1)</script> ，那么f<script id="MathJax-Element-39" type="math/tex">f</script> 是C∩H1<script id="MathJax-Element-40" type="math/tex">C \cap H_1</script> 上的常数函数，那么f<script id="MathJax-Element-41" type="math/tex">f</script> 在C∩H1<script id="MathJax-Element-42" type="math/tex">C \cap H_1</script> 的某些极点上取到最小值(由于C<script id="MathJax-Element-43" type="math/tex">C</script> 有极点，由命题2.1.2知C<script id="MathJax-Element-44" type="math/tex">C</script> 不包含直线，那么C∩H1<script id="MathJax-Element-45" type="math/tex">C \cap H_1</script> 也不会包含直线，再由命题2.1.2知C∩H1<script id="MathJax-Element-46" type="math/tex">C \cap H_1</script> 至少有一个极点)，又由命题2.1.1知这些极点也是C<script id="MathJax-Element-47" type="math/tex">C</script> 的极点，也即f<script id="MathJax-Element-48" type="math/tex">f</script> 可在C<script id="MathJax-Element-49" type="math/tex">C</script> 的某些极点上取到最小值。若x??ri(C∩H1)<script id="MathJax-Element-50" type="math/tex">\boldsymbol{x}^* \not \in ri(C \cap H_1)</script> ，则存在超平面H2<script id="MathJax-Element-51" type="math/tex">H_2</script> 正常分离x?<script id="MathJax-Element-52" type="math/tex">\boldsymbol{x}^*</script> 和C∩H1<script id="MathJax-Element-53" type="math/tex">C \cap H_1</script> ，那么集合C∩H1∩H2<script id="MathJax-Element-54" type="math/tex">C \cap H_1 \cap H_2</script> 的维度比C∩H1<script id="MathJax-Element-55" type="math/tex">C \cap H_1</script> 小。

　　若x?∈ri(C∩H1∩H2)<script id="MathJax-Element-56" type="math/tex">\boldsymbol{x}^* \in ri(C \cap H_1 \cap H_2)</script> ，那么f<script id="MathJax-Element-57" type="math/tex">f</script> 是C∩H1∩H2<script id="MathJax-Element-58" type="math/tex">C \cap H_1 \cap H_2</script> 上的常数函数，如此不断下去(由于每引进一个超平面都会使得集合C∩H1∩…<script id="MathJax-Element-59" type="math/tex">C \cap H_1 \cap \dots</script> 的维度降低，最多引进n<script id="MathJax-Element-60" type="math/tex">n</script> 个超平面该过程就会停止，最终集合变成单点集)，直到x?<script id="MathJax-Element-61" type="math/tex">\boldsymbol{x}^*</script> 是某个集合C∩H1∩?∩Hk<script id="MathJax-Element-62" type="math/tex">C \cap H_1 \cap \dots \cap H_k</script> 的相对内部点，那么f<script id="MathJax-Element-63" type="math/tex">f</script> 是C∩H1∩?∩Hk<script id="MathJax-Element-64" type="math/tex">C \cap H_1 \cap \dots \cap H_k</script> 上的常数函数，故此时f<script id="MathJax-Element-65" type="math/tex">f</script> 即在C∩H1∩?∩Hk<script id="MathJax-Element-66" type="math/tex">C \cap H_1 \cap \dots \cap H_k</script> 的极点上取得了最小值，再不断地利用命题2.1.1的结论可知这些极点也是C<script id="MathJax-Element-67" type="math/tex">C</script> 的极点，也即f<script id="MathJax-Element-68" type="math/tex">f</script> 可在C<script id="MathJax-Element-69" type="math/tex">C</script> 的某些极点上取到最小值。

　　命题2.4.2[线性规划基本定理]：若多面体P<script id="MathJax-Element-70" type="math/tex">P</script> 至少有一个极点，则在P<script id="MathJax-Element-71" type="math/tex">P</script> 上有下界的线性函数f<script id="MathJax-Element-72" type="math/tex">f</script> 必然可在P<script id="MathJax-Element-73" type="math/tex">P</script> 的某些极点上取到最小值。

　　证明：由于f<script id="MathJax-Element-74" type="math/tex">f</script> 在P<script id="MathJax-Element-75" type="math/tex">P</script> 上有下界，那么由命题1.4.19知f<script id="MathJax-Element-76" type="math/tex">f</script> 在P<script id="MathJax-Element-77" type="math/tex">P</script> 上可取得最小值，由命题2.4.1知结论成立。线性规划的两种可能：(a)(b)是P有极点的情况，(c)是P无极点的情况

　　上图展示了线性规划的两种可能：

  1. 约束集合P<script id="MathJax-Element-78" type="math/tex">P</script> 有极点，那么此时目标线性函数要么在P<script id="MathJax-Element-79" type="math/tex">P</script> 上无下界，要么在P<script id="MathJax-Element-80" type="math/tex">P</script> 的极点上取得最小值。例如设P =[0,∞)<script id="MathJax-Element-81" type="math/tex">P = [0, \infty)</script> ，那么目标线性函数1?x<script id="MathJax-Element-82" type="math/tex">1 \cdot \boldsymbol{x}</script> 在P<script id="MathJax-Element-83" type="math/tex">P</script> 的极点0<script id="MathJax-Element-84" type="math/tex">0</script> 处取得最小值；目标线性函数0?x<script id="MathJax-Element-85" type="math/tex">0 \cdot \boldsymbol{x}</script> 在P<script id="MathJax-Element-86" type="math/tex">P</script> 的任意一点处都取得最小值；目标线性函数?1?x<script id="MathJax-Element-87" type="math/tex">-1 \cdot \boldsymbol{x}</script> 在P<script id="MathJax-Element-88" type="math/tex">P</script> 上无下界，故在P<script id="MathJax-Element-89" type="math/tex">P</script> 上无法取得最小值。
  2. 约束集合P<script id="MathJax-Element-90" type="math/tex">P</script> 没有极点，那么由命题2.1.2知P<script id="MathJax-Element-91" type="math/tex">P</script> 包含直线，那么P<script id="MathJax-Element-92" type="math/tex">P</script> 的回收锥的线性空间LP<script id="MathJax-Element-93" type="math/tex">L_P</script> 的维度大于0<script id="MathJax-Element-94" type="math/tex">0</script> ，若目标线性函数在P<script id="MathJax-Element-95" type="math/tex">P</script> 有下界，那么由命题1.4.19知f<script id="MathJax-Element-96" type="math/tex">f</script> 在P<script id="MathJax-Element-97" type="math/tex">P</script> 上取得最小值。又f<script id="MathJax-Element-98" type="math/tex">f</script> 在LP<script id="MathJax-Element-99" type="math/tex">L_P</script> 的所有方向上都必须是常数函数(否则f<script id="MathJax-Element-100" type="math/tex">f</script> 无界)，故取得最小值的点集是线性空间为LP<script id="MathJax-Element-101" type="math/tex">L_P</script> 的一个多面体，故取得最小值的点集是无界的。例如设P=R<script id="MathJax-Element-102" type="math/tex">P = \mathbb{R}</script> ，那么目标线性函数1?x<script id="MathJax-Element-103" type="math/tex">1 \cdot \boldsymbol{x}</script> 在P<script id="MathJax-Element-104" type="math/tex">P</script> 上无下界，故在P<script id="MathJax-Element-105" type="math/tex">P</script> 上无法取得最小值；目标线性函数0?x<script id="MathJax-Element-106" type="math/tex">0 \cdot \boldsymbol{x}</script> 在P<script id="MathJax-Element-107" type="math/tex">P</script> 上取得最小值的点集就是P<script id="MathJax-Element-108" type="math/tex">P</script> 。


联系
我们