优化问题的并行算法

今天我们讨论并行算法，首先我们来形象的介绍一下这三个算法（不要杠我，提前声明，非常不严谨的比喻）。 在之前，你只有一个打工人（处理器）可以使用，而在这一节，你有 $p$ 个打工人（处理器）可以奴役。那么你会怎么提高效率呢，理想状态下，把你的工作分成多块，然后这些打工人每个人独立的做自己的事情，最后合起来，这是最完美的状态。可惜呢，咱们这个优化问题是是个技术活，这些运算都是相互关联的，很难分成独立的一些任务，也就是说，特别遗憾，这些打工人不能同时为你工作，那么还有没有能够提高效率的方法呢？当然有！让处理器卷起来！（学名叫做：处理器达尔文主义(¬‿¬)）

1.PVD算法，一个人工作效率低，同样还是一个人的任务，如果这个位置变成竞争上岗，那效率也许就上去了。这真是个提高效率的好方法😉！所以PVD算法就是这样一个思路， $p$ 个处理机，谁也别闲着，都尽自己的努力去搜索下一步的迭代点 $x^{(i+1)}$ ，因此你每次迭代就能获得 $p$ 个候选方案，然后你只需选一个最好的，淘汰其他的就可以了。

2.PVT算法是PVD算法的一个推广，处理器并行计算的时候优化的函数更一般了，最后选择候选方案的时候，是所有备选点的一个组合（换言之，博采众长）。

3.异步PVT算法是思想是，并行计算部分有短板效应，要等最计算最慢的人结束我们才能从备选方案中选择下一步的迭代点，所以干脆只要存在处理机的优化结果能够达到我所设置的标准，我就直接结束并行步骤，不再等其他人了。然后从满足条件的点进行同步计算。