實現內點

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的三角形）。

我希望你能明白我在這裏寫的。