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's gravatar image

FDahms
635
accept rate: 0%


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:

  1. 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)
  2. 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.
link

answered 09 Feb '15, 09:39

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

edited 09 Feb '15, 13:50

fbahr's gravatar image

fbahr ♦
4.6k716

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... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×101
×1
×1

Asked: 09 Feb '15, 09:17

Seen: 1,938 times

Last updated: 11 Feb '15, 22:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.