<p>I have a few observations which are too long for comments.  Here's a summary.</p>

<ol>
<li><p>Any algorithm to solve your problem exactly can be used to solve linear programs exactly (i.e., "strong linear programming", which is used in Sariel's solution, and presently does not have a polynomial time algorithm).</p></li>
<li><p>The natural follow-up is if approximate solutions (i.e., "weak linear programming") can provide a solution.  While the answer is yes, it appears that the stopping condition for this procedure requires quantities which, to the best of my knowledge, can not be computed in polynomial time.  (i.e., the algorithm finds something good, but certifying this is difficult.)  My main suggestion here is to make a meaningful definition of an "$\epsilon$-optimal solution" for your problem, in which case this approach is tractable.  (This strategy effectively throws out tiny faces of the polyhedron.)</p></li>
</ol>

<p>In general, while thinking about your present statement of your problem, I kept running into efficiency considerations.  But there's reasonable intuition to this: the objects we're throwing around -- vertices, faces, etc. -- are discrete, and exponentially abundant.</p>

<p><strong>(1.)</strong>  Suppose we have an algorithm which exactly solves your problem.  Notice that any exposed point of any face containing the provided midpoint will be an exact solution to the original linear program.  So proceed as follows.  Add a new linear constraint saying that the original objective value must be equal to the optimal one (which we now know), and set a new objective saying to maximize the first coordinate of the solution.  Repeat this procedure one time for each dimension, each time adding a constraint and choosing a new coordinate to maximize.  This process will reduce the dimension of the solution each time; necessarily, when the process completes, we have a 0-dimensional affine set, meaning a single point.  Thus with $\mathcal O(d)$ iterations of your midpoint-solving algorithm (and only increasing the problem description by an amount polynomial in $d$ each time), strong linear programming is solved.  This shows that while Sariel's solution requires strong linear programming, an exact solution to your question can not avoid it.  (<strong>Edit</strong>: note that my proof supposes a compact polyhedron (a polytope) as input; otherwise it has to work a little harder to find vertices.)</p>

<p><strong>(2.)</strong> Here's an iterative scheme, using a full blown convex solver in each iteration, whose solutions will converge to a mild notion of midpoint solution.  Choose a positive yet decreasing sequence of penalty parameters $\{\lambda_i\}_{i=1}^\infty\downarrow 0$; it is reasonable to have these go down geometrically, i.e. $\lambda_i = 2^{-i}$.  Now, for each $i$, approximately minimize the convex function</p>

<p>$$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$$</p>

<p>where $\langle c,x\rangle$ is your original objective, and $j$ ranges over the $m$ original constraints, now placed in the objective via logarithmic barriers (note, this is standard).  Now if we think about the minimizing face (of largest dimension) of your polyhedron, notice that for
sufficiently small $\lambda_i$ and tolerance $\tau$ to your convex opt black box, your approximate optimum will be close to this face, however the barriers will push it as far as possible from the other constraints.  Said another way, as $\lambda_i$ decreases, the original linear objective will eventually dominate some finicky barriers that were keeping you from the appropriate face, but won't impact the barriers keeping you from other boundaries, in particular those of the target face.</p>

<p>In a perfect world, we would sit down and analytically determine a perfect value $\lambda$, or at least a stopping time so you don't have to solve, well, infinitely many problems.  Unfortunately, this seems tough.  One idea is, say, to determine the smallest width of any face having dimension greater than 0; this is a well defined minimization problem with positive optimum, because there are finitely many faces (and width is computed relative to each).  With this, we can set $\lambda$ small enough that the influence of the barriers is tiny within the center of <em>every</em> face. Unfortunately, there could be exponentially many faces, so computing this quantity is nonsense.</p>

<p>All the stopping conditions I could come up with had these sorts computational difficulties.  (Moreover, many could again be used to turn this into a strong linear programming solver.)  </p>

<p>For this reason, my recommendation is to construct a notion of ``$\epsilon$-close optimal midpoint'', and solve for it by choosing $\lambda$ and your convex opt black box tolerance $\tau$ appropriately.  I think this is a reasonable choice because you may really not care about faces that have largest width at most $\epsilon$.</p>

<p><strong>(Some final comments.)</strong> It seems the notion of "midpoint" is crucial; Sasho's comment points out that the centroid (center of mass?) is an extremely difficult problem, whereas finding, say, the largest inscribed ball is easy.  The logarithmic barriers I have suggested above will in general not be consistent with either of these midpoint notions.  On the other hand, for the barriers and the ball, you can derive a lower bound on the distance from your centroid to the relative boundary of the face; maybe this is more useful to you?</p>

<p>Lastly, from your description, I believe you meant the "target face" to have as high a dimension as possible?  This is well defined, however there are also solution faces for all possible smaller dimensions as well.  Anyway, both Sariel's approach and the barrier approach above will work with the face of largest dimension.</p>

CC BY-SA 3.0
2012-03-20T14:52:14.560Z
Yes, I considered tricks like this, but I ultimately went with minimizing $\sum_i f_i(x)^2 + \sum_j x_j^2$ subject to $\sum_j x_j = 1$ using Lagrange multipliers.  It yields a weak centrality property for $x$ on the diagonal, which might not be the minimizing surface, but is certainly one of the constraint surfaces that never moves.  I simply run a separate linear program once the contraints stop evolving and I actually need the real minimum for $\epsilon$.  There was ultimately no need keep $\epsilon$ minimized to help the constraints evolve faster.  Thanks though!  :)
Jeff Burdges
CC BY-SA 3.0
2012-03-20T14:58:20.437Z
Ahh #2 looks interesting, not what I initially thought it was.  cute!  As I said, I forgive $x$ for not landing on the minimizing face, so long as it goes someplace reasonable quickly. I'll play with this at some point.  In fact, I'll need to read up on convex optimization anyways since I've found a reason to make my objective bilinear instead of linear.
Jeff Burdges
CC BY-SA 3.0
2012-03-20T16:34:57.087Z
I don't understand the point about "strong linear programming" and I have never heard this expression before. it is not known how to solve an LP in strong polynomial time. but solving an LP in time polynomial in the input description (i.e. weak polynomial time) is of course well known. if the OP wants an algorithm running in weak polynomial time then Sariel's solution + a poly-time interior point algorithm will do the job, no?
Sasho Nikolov
CC BY-SA 3.0
2012-03-20T19:24:09.747Z
@SashoNikolov, here is my present understanding.  Any existing (weak poly-time) solver will take a tolerance $\tau$ as input, and return a $\tau$-optimal solution.  Meanwhile, Sariel's solution crucially depends on an exact solution: in particular, an interior point method will return a relatively interior approximate optimum, which means that the step identifying the affine hull of the desired optimal face will actually pick out the hull of the whole feasible set.  I agree that I should revise what I wrote about strong/weak, where the key issue is really obtaining exact solutions in any way.
matus
CC BY-SA 3.0
2012-03-20T21:18:54.113Z
@SashoNikolov, now that I think about it, the same optimality notion (with the same issues) can be worked into Sariel's solution, for instance by treating constraints that are within some tiny tolerance to actually be tight, and tuning this value appropriately.  I'll update my solution tonight.
matus
CC BY-SA 3.0
2012-03-21T02:07:01.323Z
@matus, yes, i think you can include tolerance for error in Sariel's solution, as you describe. But I also recall that since the dependence of running time on the error $\tau$ in polytime LP algorithms is $\log 1/\tau$, there are some standard tricks to use a $\tau$-optimal solution to find an exactly optimal solution, given that $\tau$ is small enough.
Sasho Nikolov
CC BY-SA 3.0
2012-03-21T02:10:06.640Z
@matus note that for things like SDP an optimal solution can be irrational and the error is necessary. this is not true for LP: using Cramer's rule you can show that given rational coefficients, any vertex is rational and can be written in number of bits polynomial in the input size.
Sasho Nikolov
CC BY-SA 3.0
2012-03-21T05:29:10.387Z
@SashoNikolov, my basic complaint about the regime you describe is that the running time is determined by properties of the polytope.  You could feed me a simple polytope, and I could add tiny fractions to each coefficient, and now the running time of the scheme,  which depends on the structure of the polytope (suppose I caused the objective value to gain many bits but hardly change in value), has drastically changed.  But sometimes this accuracy is not necessary, which is why I prefer a scheme where the running time is parameterized by a desired level of optimality.
matus
CC BY-SA 3.0
2012-03-21T05:30:33.347Z
@SashoNikolov, note, this also lets you work with a reasonable notion of computable reals (i.e., potentially irrational), since the accuracy lets us work with rational approximations.  But anyway, thanks for your comments, I have a lot of revising to do above =)
matus
CC BY-SA 3.0
2012-03-20T06:28:33.797Z
2012-03-20T06:54:47.277Z
2012-03-20T06:54:47.277Z
matus
<p>First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want. </p>

<p>Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...</p>

<p>==============</p>

<p>More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.</p>

<p>So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.</p>

<p>So, to summerize: 
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.</p>

CC BY-SA 3.0
2012-03-18T20:07:06.680Z
What is meant by "largest ball" in a polyhedron not of full dimension?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-03-19T01:38:39.897Z
@KristofferArnsfeltHansen the polyhedron surely is a convex set lying in an affine subspace of *some* dimension.
Sasho Nikolov
CC BY-SA 3.0
2012-03-19T02:04:40.487Z
for this to work, you'd need to specify a constraint limiting you to the face(s) you found in the first step. You'd also need to know that the solution was constant across this face (presumably complementary slackness would reveal this)
Suresh Venkat
CC BY-SA 3.0
2012-03-20T06:47:18.050Z
Is there some way to do the steps after the initial optimization in polynomial time?  As written, it seems to require consideration of all vertices in the target face, of which there may be exponentially many.
matus
CC BY-SA 3.0
2012-03-20T09:01:12.080Z
@KristofferArnsfeltHansen: A "ball" means the set of all points in the affine span of the optimal face within some distance $r$ of some point.  "Largest" means maximum Lebesgue measure, which is just what you think it is: length for 1d balls, area for 2d balls, volume for 3d balls, etc.
Jeffε
CC BY-SA 3.0
2012-03-20T09:02:03.693Z
@matus: No, you just need one additional equality constraint, describing the hyperplane normal to the objective direction through an arbitrary optimal point.
Jeffε
CC BY-SA 3.0
2012-03-20T09:11:46.077Z
@JɛﬀE: (followup to your reply to @matus) Is that really enough? That would move down only 1 in dimension. I think one really needs to do as Sariel indicates in his edit, namely move to a space of correct dimension. matus: One needs not look at all vertices of the optimal face. Just a set of vertices that span the smallest affine space containing the face.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-03-20T09:38:58.257Z
@KristofferArnsfeltHansen, ah okay thanks, something like this?  Starting with the optimal point $v_0$, if no constraints are satisfied strictly, stop.  Otherwise, choose any point $v_1 \neq v_0$ which satisfies all constraints, and add a new constraint $\langle x, v_1 - v_0\rangle = \langle v_0, v_1-v_0\rangle$, forcing new points to be orthogonal to this new direction.  Iterate this procedure as long as possible; it will terminate in $k<\infty$ steps, where $k$ is the dimension of the largest-dimensional optimal face, and provides a basis for the desired affine space.
matus
CC BY-SA 3.0
2012-03-20T21:52:40.210Z
It is easier than that - you need to consider only the vertices adjacent to the optimal vertex - there are at most $d$ adjacent to it, and you can compute them in polynomial time.... To see why its true, consider the polytope on the affine subspace - it is spanned by the neighbors of $v$ that lie on this affine subspace, but these are a subset of the vertices adjacent to v in the original polytope. And yes - it took me quite a bit of time to see that.
Sariel Har-Peled
CC BY-SA 3.0
2012-03-21T05:43:03.253Z
@SarielHar-Peled, I was trying to avoid any dependence on vertices, since they are not given in the description of the polytope, and must be constructed.  The shortest procedure I can see for what you describe is a complication of what I gave above.  Specifically, find the constraints tight at $v_0$, and choose one which can be made slack while maintaining tightness on the others, plus feasibility, plus your new constraint.  Move along this necessarily 1-dimensional face until a vertex is found.  Repeat this procedure, choosing an affine independent 1-d face each time.
matus
CC BY-SA 3.0
2012-03-21T06:11:55.590Z
@SarielHar-Peled, also, it seems to me that there are many adjacent vertices to choose from, and so the last step of my procedure is vague; can you explain how you got $d$ adjacent vertices?  For instance, take any polytope with a vertex with $>d$ adjacent vertices.  Let the objective function be $\langle 0, x\rangle$ and suppose the solver returns the vertex with $>d$ adjacent vertices as the solution.  The entire polytope is the optimal face.
matus
CC BY-SA 3.0
2012-03-21T20:44:38.570Z
Under general position assumptions, you are not going to get vertices that have degree larger than $d$. If you do, then you can introduce tiny noise to resolve this. The book by Vanderbei for example has a nice description of how to  do this. In any case, I have no objections to using LP to finding the subspace, it is just that as far as efficiency, using the neighbering vertices is way more efficient...
Sariel Har-Peled
CC BY-SA 3.0
2012-03-31T11:24:53.607Z
@matus, horrendous oversight in my construction; while it is true that a d-dimensional affine set contains a d-dimensional simplex, it is not necessarily the case that this simplex can be placed at a vertex (extreme point).. these can always be constructed at relative interior points, however, and so an interior point method can be used to do my construction properly..
matus
CC BY-SA 3.0
2012-03-18T19:01:03.897Z
2012-03-20T05:49:42.270Z
2012-03-20T05:49:42.270Z
Sariel Har-Peled
<p>There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.</p>

<p>A priori, we expect the minimizing face should be high dimensional for various reasons, including that the objective function being minimized is the maximum of many of the constraints :</p>

<p>Minimize $\epsilon$ subject to $f_i(\bar x) \leq \epsilon &lt; 0$ with $f_i$ linear and $x_i &gt; 0$ for all $i$ and $\sum_i x_i = 1$.</p>

<p>We'd never obtain any centrality-like property form the simplex algorithm of course.  Do any of the usual interior point algorithms exhibit such properties though?  Do any even guarantee they'll avoid vertices or lower dimensional faces whenever possible?</p>

<hr>

<p>In fact, I'm probably content with a easy quadratic program that finds the midpoint of the entire polytope since centrality matters more than minimality, just vaguely curious if other linear programming algorithms offer relevant properties.</p>

<p>Update : I've reduced the underlying problem to a simple constrained minimization problem solvable with Lagrange multipliers, but the question above remains interesting anyways. </p>

CC BY-SA 3.0
2012-03-12T23:49:56.983Z
not exactly your question but: computing the centroid is #P-hard; i am not sure what's the best approximation, but for some applications putting the polytope in isotropic position and taking the average of polynomially many uniform samples from the (transformed) polytope suffices. see these note, Lemma 15 for example: http://www.cc.gatech.edu/~vempala/acg/notes.pdf
Sasho Nikolov
CC BY-SA 3.0
2012-03-13T15:27:49.687Z
is this more a theoretical or more a practical question? perhaps it would be feasible to generate all vertices of the optimal face and then use some suitable convex combination of them.
anonymous
<ds.algorithms><linear-algebra><linear-programming>
Midpoint solutions to linear programs
Jeff Burdges
# Midpoint solutions to linear programs

(Asked by: username_0 on 2012-03-12)

There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.

A priori, we expect the minimizing face should be high dimensional for various reasons, including that the objective function being minimized is the maximum of many of the constraints :

Minimize $\epsilon$ subject to $f\_i(\bar x) \leq \epsilon < 0$ with $f\_i$ linear and $x\_i > 0$ for all $i$ and $\sum\_i x\_i = 1$.

We'd never obtain any centrality-like property form the simplex algorithm of course. Do any of the usual interior point algorithms exhibit such properties though? Do any even guarantee they'll avoid vertices or lower dimensional faces whenever possible?

---

In fact, I'm probably content with a easy quadratic program that finds the midpoint of the entire polytope since centrality matters more than minimality, just vaguely curious if other linear programming algorithms offer relevant properties.

Update : I've reduced the underlying problem to a simple constrained minimization problem solvable with Lagrange multipliers, but the question above remains interesting anyways.

**Tags:** ds.algorithms, linear-algebra, linear-programming

> **Comments:**
> **username_1**: not exactly your question but: computing the centroid is #P-hard; i am not sure what's the best approximation, but for some applications putting the polytope in isotropic position and taking the average of polynomially many uniform samples from the (transformed) polytope suffices. see these note, Lemma 15 for example: http://www.cc.gatech.edu/~vempala/acg/notes.pdf  
> **username_2**: is this more a theoretical or more a practical question? perhaps it would be feasible to generate all vertices of the optimal face and then use some suitable convex combination of them.  

---

## 2 answers

### Answer by username_3 on 2012-03-20. Score: 4 | Accepted answer

I have a few observations which are too long for comments. Here's a summary.

1. Any algorithm to solve your problem exactly can be used to solve linear programs exactly (i.e., "strong linear programming", which is used in Sariel's solution, and presently does not have a polynomial time algorithm).
2. The natural follow-up is if approximate solutions (i.e., "weak linear programming") can provide a solution. While the answer is yes, it appears that the stopping condition for this procedure requires quantities which, to the best of my knowledge, can not be computed in polynomial time. (i.e., the algorithm finds something good, but certifying this is difficult.) My main suggestion here is to make a meaningful definition of an "$\epsilon$-optimal solution" for your problem, in which case this approach is tractable. (This strategy effectively throws out tiny faces of the polyhedron.)

In general, while thinking about your present statement of your problem, I kept running into efficiency considerations. But there's reasonable intuition to this: the objects we're throwing around -- vertices, faces, etc. -- are discrete, and exponentially abundant.

**(1.)** Suppose we have an algorithm which exactly solves your problem. Notice that any exposed point of any face containing the provided midpoint will be an exact solution to the original linear program. So proceed as follows. Add a new linear constraint saying that the original objective value must be equal to the optimal one (which we now know), and set a new objective saying to maximize the first coordinate of the solution. Repeat this procedure one time for each dimension, each time adding a constraint and choosing a new coordinate to maximize. This process will reduce the dimension of the solution each time; necessarily, when the process completes, we have a 0-dimensional affine set, meaning a single point. Thus with $\mathcal O(d)$ iterations of your midpoint-solving algorithm (and only increasing the problem description by an amount polynomial in $d$ each time), strong linear programming is solved. This shows that while Sariel's solution requires strong linear programming, an exact solution to your question can not avoid it. (**Edit**: note that my proof supposes a compact polyhedron (a polytope) as input; otherwise it has to work a little harder to find vertices.)

**(2.)** Here's an iterative scheme, using a full blown convex solver in each iteration, whose solutions will converge to a mild notion of midpoint solution. Choose a positive yet decreasing sequence of penalty parameters $\{\lambda\_i\}\_{i=1}^\infty\downarrow 0$; it is reasonable to have these go down geometrically, i.e. $\lambda\_i = 2^{-i}$. Now, for each $i$, approximately minimize the convex function

$$\langle c,x\rangle - \lambda\_i\sum\_{j=1}^m \ln(\langle a\_j,x\rangle - b),$$

where $\langle c,x\rangle$ is your original objective, and $j$ ranges over the $m$ original constraints, now placed in the objective via logarithmic barriers (note, this is standard). Now if we think about the minimizing face (of largest dimension) of your polyhedron, notice that for
sufficiently small $\lambda\_i$ and tolerance $\tau$ to your convex opt black box, your approximate optimum will be close to this face, however the barriers will push it as far as possible from the other constraints. Said another way, as $\lambda\_i$ decreases, the original linear objective will eventually dominate some finicky barriers that were keeping you from the appropriate face, but won't impact the barriers keeping you from other boundaries, in particular those of the target face.

In a perfect world, we would sit down and analytically determine a perfect value $\lambda$, or at least a stopping time so you don't have to solve, well, infinitely many problems. Unfortunately, this seems tough. One idea is, say, to determine the smallest width of any face having dimension greater than 0; this is a well defined minimization problem with positive optimum, because there are finitely many faces (and width is computed relative to each). With this, we can set $\lambda$ small enough that the influence of the barriers is tiny within the center of *every* face. Unfortunately, there could be exponentially many faces, so computing this quantity is nonsense.

All the stopping conditions I could come up with had these sorts computational difficulties. (Moreover, many could again be used to turn this into a strong linear programming solver.)

For this reason, my recommendation is to construct a notion of ``$\epsilon$-close optimal midpoint'', and solve for it by choosing $\lambda$ and your convex opt black box tolerance $\tau$ appropriately. I think this is a reasonable choice because you may really not care about faces that have largest width at most $\epsilon$.

**(Some final comments.)** It seems the notion of "midpoint" is crucial; Sasho's comment points out that the centroid (center of mass?) is an extremely difficult problem, whereas finding, say, the largest inscribed ball is easy. The logarithmic barriers I have suggested above will in general not be consistent with either of these midpoint notions. On the other hand, for the barriers and the ball, you can derive a lower bound on the distance from your centroid to the relative boundary of the face; maybe this is more useful to you?

Lastly, from your description, I believe you meant the "target face" to have as high a dimension as possible? This is well defined, however there are also solution faces for all possible smaller dimensions as well. Anyway, both Sariel's approach and the barrier approach above will work with the face of largest dimension.

> **Comments:**
> **username_0**: Yes, I considered tricks like this, but I ultimately went with minimizing $\sum_i f_i(x)^2 + \sum_j x_j^2$ subject to $\sum_j x_j = 1$ using Lagrange multipliers.  It yields a weak centrality property for $x$ on the diagonal, which might not be the minimizing surface, but is certainly one of the constraint surfaces that never moves.  I simply run a separate linear program once the contraints stop evolving and I actually need the real minimum for $\epsilon$.  There was ultimately no need keep $\epsilon$ minimized to help the constraints evolve faster.  Thanks though!  :)  
> **username_0**: Ahh #2 looks interesting, not what I initially thought it was.  cute!  As I said, I forgive $x$ for not landing on the minimizing face, so long as it goes someplace reasonable quickly. I'll play with this at some point.  In fact, I'll need to read up on convex optimization anyways since I've found a reason to make my objective bilinear instead of linear.  
> **username_1**: I don't understand the point about "strong linear programming" and I have never heard this expression before. it is not known how to solve an LP in strong polynomial time. but solving an LP in time polynomial in the input description (i.e. weak polynomial time) is of course well known. if the OP wants an algorithm running in weak polynomial time then Sariel's solution + a poly-time interior point algorithm will do the job, no?  
> **username_3**: @SashoNikolov, here is my present understanding.  Any existing (weak poly-time) solver will take a tolerance $\tau$ as input, and return a $\tau$-optimal solution.  Meanwhile, Sariel's solution crucially depends on an exact solution: in particular, an interior point method will return a relatively interior approximate optimum, which means that the step identifying the affine hull of the desired optimal face will actually pick out the hull of the whole feasible set.  I agree that I should revise what I wrote about strong/weak, where the key issue is really obtaining exact solutions in any way.  
> **username_3**: @SashoNikolov, now that I think about it, the same optimality notion (with the same issues) can be worked into Sariel's solution, for instance by treating constraints that are within some tiny tolerance to actually be tight, and tuning this value appropriately.  I'll update my solution tonight.  
> **username_1**: @username_3, yes, i think you can include tolerance for error in Sariel's solution, as you describe. But I also recall that since the dependence of running time on the error $\tau$ in polytime LP algorithms is $\log 1/\tau$, there are some standard tricks to use a $\tau$-optimal solution to find an exactly optimal solution, given that $\tau$ is small enough.  
> **username_1**: @username_3 note that for things like SDP an optimal solution can be irrational and the error is necessary. this is not true for LP: using Cramer's rule you can show that given rational coefficients, any vertex is rational and can be written in number of bits polynomial in the input size.  
> **username_3**: @SashoNikolov, my basic complaint about the regime you describe is that the running time is determined by properties of the polytope.  You could feed me a simple polytope, and I could add tiny fractions to each coefficient, and now the running time of the scheme,  which depends on the structure of the polytope (suppose I caused the objective value to gain many bits but hardly change in value), has drastically changed.  But sometimes this accuracy is not necessary, which is why I prefer a scheme where the running time is parameterized by a desired level of optimality.  
> **username_3**: @SashoNikolov, note, this also lets you work with a reasonable notion of computable reals (i.e., potentially irrational), since the accuracy lets us work with rational approximations.  But anyway, thanks for your comments, I have a lot of revising to do above =)  

---

### Answer by username_4 on 2012-03-18. Score: 6

First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want.

Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...

==============

More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.

So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.

So, to summerize:
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.

> **Comments:**
> **username_5**: What is meant by "largest ball" in a polyhedron not of full dimension?  
> **username_1**: @KristofferArnsfeltHansen the polyhedron surely is a convex set lying in an affine subspace of *some* dimension.  
> **username_6**: for this to work, you'd need to specify a constraint limiting you to the face(s) you found in the first step. You'd also need to know that the solution was constant across this face (presumably complementary slackness would reveal this)  
> **username_3**: Is there some way to do the steps after the initial optimization in polynomial time?  As written, it seems to require consideration of all vertices in the target face, of which there may be exponentially many.  
> **username_7**: @KristofferArnsfeltHansen: A "ball" means the set of all points in the affine span of the optimal face within some distance $r$ of some point.  "Largest" means maximum Lebesgue measure, which is just what you think it is: length for 1d balls, area for 2d balls, volume for 3d balls, etc.  
> **username_7**: @username_3: No, you just need one additional equality constraint, describing the hyperplane normal to the objective direction through an arbitrary optimal point.  
> **username_5**: @JɛﬀE: (followup to your reply to @username_3) Is that really enough? That would move down only 1 in dimension. I think one really needs to do as Sariel indicates in his edit, namely move to a space of correct dimension. username_3: One needs not look at all vertices of the optimal face. Just a set of vertices that span the smallest affine space containing the face.  
> **username_3**: @KristofferArnsfeltHansen, ah okay thanks, something like this?  Starting with the optimal point $v_0$, if no constraints are satisfied strictly, stop.  Otherwise, choose any point $v_1 \neq v_0$ which satisfies all constraints, and add a new constraint $\langle x, v_1 - v_0\rangle = \langle v_0, v_1-v_0\rangle$, forcing new points to be orthogonal to this new direction.  Iterate this procedure as long as possible; it will terminate in $k<\infty$ steps, where $k$ is the dimension of the largest-dimensional optimal face, and provides a basis for the desired affine space.  
> **username_4**: It is easier than that - you need to consider only the vertices adjacent to the optimal vertex - there are at most $d$ adjacent to it, and you can compute them in polynomial time.... To see why its true, consider the polytope on the affine subspace - it is spanned by the neighbors of $v$ that lie on this affine subspace, but these are a subset of the vertices adjacent to v in the original polytope. And yes - it took me quite a bit of time to see that.  
> **username_3**: @SarielHar-Peled, I was trying to avoid any dependence on vertices, since they are not given in the description of the polytope, and must be constructed.  The shortest procedure I can see for what you describe is a complication of what I gave above.  Specifically, find the constraints tight at $v_0$, and choose one which can be made slack while maintaining tightness on the others, plus feasibility, plus your new constraint.  Move along this necessarily 1-dimensional face until a vertex is found.  Repeat this procedure, choosing an affine independent 1-d face each time.  
> **username_3**: @SarielHar-Peled, also, it seems to me that there are many adjacent vertices to choose from, and so the last step of my procedure is vague; can you explain how you got $d$ adjacent vertices?  For instance, take any polytope with a vertex with $>d$ adjacent vertices.  Let the objective function be $\langle 0, x\rangle$ and suppose the solver returns the vertex with $>d$ adjacent vertices as the solution.  The entire polytope is the optimal face.  
> **username_4**: Under general position assumptions, you are not going to get vertices that have degree larger than $d$. If you do, then you can introduce tiny noise to resolve this. The book by Vanderbei for example has a nice description of how to  do this. In any case, I have no objections to using LP to finding the subspace, it is just that as far as efficiency, using the neighbering vertices is way more efficient...  
> **username_3**: @username_3, horrendous oversight in my construction; while it is true that a d-dimensional affine set contains a d-dimensional simplex, it is not necessarily the case that this simplex can be placed at a vertex (extreme point).. these can always be constructed at relative interior points, however, and so an interior point method can be used to do my construction properly..  

---

