实现内点

Question

除了博伊德的凸规划书，

什么是最好的资源：

分析+的内点算法的实际执行？

Answer 1

如果你有博伊德的书，你知道约CVXOPT。看看它的内部。如果您对实现细节感兴趣，那么查看实现是非常宝贵的。与大多数复杂的数值算法一样，使用以前编写的代码要比编写自己的代码要好得多，但您可能知道这一点。还有许多其他内部点实现可供在线使用，用于线性编程，SOCP，二次编程，凸面编程等。我还使用了OOQP，并在内部查看了一下。这似乎很直接。

我也喜欢第一版Numerical Optimization。下半年，我对预测校正方法有了一个很好的，相当实用的概述。第二版毫无疑问具有相似的质量。

Answer 2

您可以通过两种方式实现：

如果你只有一个点，你会得到多边形的面积，然后检查是否n个三角形的面积与在verticle总和两个连续点中的点和另外两个点与多边形的面积相等。如果这是真的，那么重点就在里面，否则就在外面。

如果你有很多点（比方说M个点），你必须找到它是否在里面，你会在多边形内找到一个点，并将多边形分成n个三角形，另外两个在多边形上的两个连续点（形成一个边）。你将有n条线，在之前选择的点上有一个垂直线，而多边形的每个点上有一个点。你会按顺时针方向排列它们。然后，您将在M点中选择一个点，并选择其中一个M点。你会像第一个N一样对它们进行排序。然后，你可以在o（N + M）中找到M中的每个点，N中最近的左边和右边线（假设这些线是CenterAx和CenterAy。Next （1）检查三角形CenterAxAy的a是否等于面积（CenterAxP）+面积（CenterAyP）+面积（AxAyP）的面积是否等于CenterAxAy的三角形）。

我希望你能明白我在这里写的。