Implementing Interior Point

Question

Besides Boyd's Convex Programming book,

what's the best resource for:

analysis + practical implementation of interior point algorithms?

Answer 1

If you have Boyd's book, you know about CVXOPT. Look inside of it. If you are interested in implementation details, looking at an implementation is invaluable. As with most complex numerical algorithms, you are going to be much better off using previously written code than writing your own, but you probably know that. There are many other interior point implementations available online for linear programing, SOCP, quadratic programming, convex programming, etc. I have also used OOQP, and looked a bit at the insides. It seemed straightforward enough.

I also liked the first edition of Numerical Optimization. I had a good, fairly practical, overview of predictor-corrector methods in the second half. The second edition is no doubt of similar quality.

Answer 2

You can implement it in two ways:

If you have only one point, you'll get the area of the polygon, and then check if the sum of the area of the n triangles with a verticle in the point and the other two in two consecutively points is equal with the area of the polygon. If it's true, the point is inside, otherwise it's outside.

If you have many points (let's say M points) and you have to find if it's inside, you'll find a point inside the polygon, and split the polygon into n triangles, with a verticle in that point and the other two in two consecutively points on the polygon (that form an edge). You will have n lines, with a verticle in the point choosed before and a point in each point of the polygon. You'll sort them by the angle, clockwise. Then, you'll have M lines with a verticle in the point choosed and the other in one of the M points. You'll sort them like the first N. Then, you can find in o(N + M), for each point in the M, the nearest left and right line from the N (let's say the lines are CenterAx and CenterAy. Next, you'll have to find if the point it's in the triangle CenterAxAy. You can do it in o(1) checking if the are a of the triangle CenterAxAy is equal with area(CenterAxP) + area(CenterAyP) + area(AxAyP).

I hope you'll understand what i've written here.