Yann
人工智能、计算机、机器学习、linux、程序员
Convex Optimization-10
本节专门回顾一下线性规划。
我们都知道对标准的线性规划问题，Dantzig提供了一种行之有效的方法——单纯形法（Simplex），他的主要想法就是先找一个初始的基可行解，判别是否最优；如不是再迭代到另一个“更好”的基可行解，再判别，如此迭代下去直到找到最优或者判定无界。
我们可以从数学上严格的证明该方法是正确的，这首先需要明确可行域的代数结构（非空多面凸集），再这之后我们通过证明最优性准则（定理1、定理2）和换基定理（定理3）就可完整把单纯形法中的第二个过程即如何判定最优与迭代这个问题搞清楚。
再次回顾时，发现这些证明蕴含着巧妙的构造式证明，值得深思。
