9
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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: cc.gatech.edu/~vempala/acg/notes.pdf $\endgroup$
    – Sasho Nikolov
    Mar 12, 2012 at 23:49
  • $\begingroup$ 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. $\endgroup$
    – anonymous
    Mar 13, 2012 at 15:27

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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! :) $\endgroup$
    – Jeff Burdges
    Mar 20, 2012 at 14:52
  • $\begingroup$ 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. $\endgroup$
    – Jeff Burdges
    Mar 20, 2012 at 14:58
  • $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    Mar 20, 2012 at 16:34
  • $\begingroup$ @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. $\endgroup$
    – matus
    Mar 20, 2012 at 19:24
  • $\begingroup$ @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. $\endgroup$
    – matus
    Mar 20, 2012 at 21:18
6
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ What is meant by "largest ball" in a polyhedron not of full dimension? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Mar 18, 2012 at 20:07
  • $\begingroup$ @KristofferArnsfeltHansen the polyhedron surely is a convex set lying in an affine subspace of some dimension. $\endgroup$
    – Sasho Nikolov
    Mar 19, 2012 at 1:38
  • $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Mar 19, 2012 at 2:04
  • $\begingroup$ 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. $\endgroup$
    – matus
    Mar 20, 2012 at 6:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Mar 20, 2012 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.