# Reference for finding optimal LP extreme point in polynomial time

 6 1 My problem is as follows: given some LP, we can find an optimal solution for it in (weakly) polynomial time via some interior point method. When there are multiple optima, the found solution might not be an extreme point but on the middle of one of the polyhedrons faces. Now I want to get from there to an optimal extreme point (for example because I have an integral IP formulation and only the extreme points are interesting for me). This should be possible in polynomial time by traversing the current face until hitting some inequality, reducing the dimension of the face by one and repeating until ending on a desired extreme point. Does anyone know a good reference or a text book where this issue is dealt with? So far I could not find a proper resource even though this argument seems to be relevant when making conclusions of the type: "This problem has an ideal and compact formulation and can therefore be solved in polynomial time" asked 09 Feb '15, 09:17 FDahms 63●5 accept rate: 0%

 9 A good starting point is Steven Wright, Primal-Dual Interior-Point Methods, SIAM Press, 1997. There are two steps to converting an interior-point solution to a basic solution: Project the approximate solution onto the optimal face. (E.g., Yinyu Ye, "On the finite convergence of interior-point algorithms for linear programming," Mathematical Programming 57, 1992 325-335) Select a basis corresponding to a corner point on the optimal face. (Nimrod Megiddo, "On finding primal and dual optimal bases," ORSA Journal on Computing 3, 1991, 63-65. answered 09 Feb '15, 09:39 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17% fbahr ♦ 4.6k●7●16 Thank you! 2 is exactly what I needed. (09 Feb '15, 09:46) FDahms Technically, for a proof of polynomial complexity, you really need both steps. The primal-dual method terminates close to--but not necessarily on--the optimal face. Megiddo's work assumes that you know precisely a strictly complementary solution, but at termination of the primal-dual method, you may have some small but nonzero primal/dual variable pairs that need to be complementary. You need to decide that one or the other of those is the true zero, and choosing incorrectly puts you on the wrong face. Ye's and related work shows how to do that in polynomial time. (11 Feb '15, 22:39) Matthew Salt... ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: