{"id":94,"date":"2016-10-23T23:32:19","date_gmt":"2016-10-23T23:32:19","guid":{"rendered":"http:\/\/www.aarondefazio.com\/tangentially\/?p=94"},"modified":"2016-10-23T23:32:19","modified_gmt":"2016-10-23T23:32:19","slug":"everything-is-easy-in-low-dimensions-part-1-linear-programming","status":"publish","type":"post","link":"https:\/\/www.aarondefazio.com\/tangentially\/?p=94","title":{"rendered":"Everything is Easy in Low Dimensions (Part 1): Linear Programming"},"content":{"rendered":"

<\/p>\n

I recently came across this remarkable randomized algorithm due to Seidel
\n(1991) for linear programming in 2 dimensions that takes only time
\nO<\/mi>(<\/mo>n<\/mi><\/mrow>)<\/mo><\/mrow><\/math> for
\nn<\/mi><\/math>
\nconstraints (in expectation). It’s de\ufb01nitely worth a close inspection, so I thought I
\nwould write a short article about it.\n<\/p>\n

<\/p>\n

Note that my presentation of this algorithm assumes that there are no redundant
\nor colinear constraints, that the solution is bounded, and that the solution for each
\nsubproblem encountered is unique. These assumptions are easy to remove
\nwithout slowing the algorithm down, but they complicate the presentation a
\nlittle.\n<\/p>\n

<\/p>\n

\n

F<\/span>U<\/span>N<\/span>C<\/span>T<\/span>I<\/span>O<\/span>N<\/span> <\/span>lpsolve
\n<\/p>\n

I<\/span>N<\/span>P<\/span>U<\/span>T<\/span><\/span>: Set H<\/mi><\/math>
\nof constraints & vector c<\/mi><\/math>.\n<\/p>\n

<\/p>\n

O<\/span>U<\/span>T<\/span>P<\/span>U<\/span>T<\/span><\/span>: A point v<\/mi><\/math>
\nin the polytope de\ufb01ned by H<\/mi><\/math>
\nminimizing c<\/mi><\/mrow>T<\/mi><\/mrow><\/msup \n>v<\/mi><\/math>.\n<\/p>\n

<\/p>\n

BA<\/span>S<\/span>E<\/span> CA<\/span>S<\/span>E<\/span>: <\/span>If
\n|<\/mo>H<\/mi>|<\/mo> =<\/mo> 2<\/mn><\/math>
\nthen return the unique intersecting point.\n<\/p>\n

<\/p>\n

NO<\/span>N<\/span> B<\/span>A<\/span>S<\/span>E<\/span> CA<\/span>S<\/span>E<\/span>:<\/span>\n <\/p>\n

    \n
  1. Pick a constraint B<\/mi><\/math>
    \n uniformly at random from H<\/mi><\/math>.\n <\/li>\n
  2. v<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n><\/math>
    \n = lpsolve(H<\/mi> \u2212<\/mo>B<\/mi><\/mrow><\/mfenced><\/math>,
    \n c<\/mi><\/math>).\n <\/li>\n
  3. If v<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n><\/math>
    \n is in the half-space de\ufb01ned by B<\/mi><\/math>
    \n R<\/span>E<\/span>T<\/span>U<\/span>R<\/span>N<\/span> <\/span>v<\/mi> =<\/mo> v<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n><\/math>,
    \n otherwise:\n <\/li>\n
  4. R<\/span>E<\/span>T<\/span>U<\/span>R<\/span>N<\/span> <\/span>v<\/mi><\/math>,
    \n the solution of the 1D LP consisting of the projection of
    \n H<\/mi><\/math>
    \n &<\/mi><\/math>
    \n c<\/mi><\/math>
    \n onto B<\/mi><\/math>.<\/li>\n<\/ol><\/div>\n

    <\/p>\n

    This algorithm is quite remarkable in its simplicity. It takes the
    \nform of an recursive algorithm, where we solve a base case, then add<\/p>\n

    additional constraints 1 at a time. Every time we add a constraint,
    \nwe consider if it changes the solution. It’s only when the old solution
    \nv<\/mi><\/mrow>\u2032<\/mi><\/mrow><\/msup \n><\/math> is outside
    \nthe added constraint that we have to do any work, namely solving a simple 1D LP, which
    \nis trivially O<\/mi>(<\/mo>m<\/mi><\/mrow>)<\/mo><\/mrow><\/math>
    \ntime for m<\/mi><\/math>
    \nconstraints.\n<\/p>\n

    <\/p>\n

    If we had to solve the 1D LP subproblem at every
    \nstep the algorithm would have quadratic running time
    \n(<\/mo>\u2211<\/mo>\n <\/mrow>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi><\/mrow><\/msubsup \n>i<\/mi> =<\/mo> O<\/mi>(<\/mo>n<\/mi><\/mrow>2<\/mn><\/mrow><\/msup \n><\/mrow>)<\/mo><\/mrow><\/math>). We avoid this because
    \nwe pick the constraint B<\/mi><\/math>
    \nto recurse on at each step randomly. Clearly we only have to solve that 1D LP if the
    \nrandomly chosen constraint B forms part of the new solution to the problem (ignoring
    \ndegenerate solutions), and since a solution is the intersection of 2 constraints, there is
    \nonly a 2<\/mn><\/math> in
    \n|<\/mo>H<\/mi>|<\/mo><\/math>
    \nchance that we randomly pick such a constraint.\n<\/p>\n

    <\/p>\n

    It follows that the cost of each recursion in expectation is
    \n|<\/mo>H<\/mi>|<\/mo><\/math> times
    \n2<\/mn>\u2215<\/mo>|<\/mo>H<\/mi>|<\/mo><\/math> which is just 2,
    \nand we recurse n<\/mi><\/math>
    \ntimes, giving us a O<\/mi>(<\/mo>n<\/mi><\/mrow>)<\/mo><\/mrow><\/math>
    \nrunning time in expectation.\n<\/p>\n

    <\/p>\n

    In the original presentation by Seidel, the algorithm is given in
    \na general form, usable in higher dimensions as well. The di\ufb03culty
    \nis that the running time quickly gets out of hand as the dimension
    \nd<\/mi><\/math>
    \nincreases. The main obstacle is step 4 above, you essentially need to solve a
    \nd<\/mi> \u2212<\/mo> 1<\/mn><\/math>
    \ndimensional LP, which is only slightly easier than your original LP in higher
    \ndimensions.\n<\/p>\n

    <\/p>\n

    On a side note, there is an interesting discussion of this algorithm and related
    \nones in the Wikipedia page for LP-type problems<\/a>.\n<\/p>\n

    <\/a>References<\/h5>\n

    <\/p>\n

    Seidel, Raimund (1991), "Small-dimensional linear programming and convex
    \nhulls made easy", Discrete and Computational Geometry, 6 (5): 423\u2013434<\/p>\n","protected":false},"excerpt":{"rendered":"

    I recently came across this remarkable randomized algorithm due to Seidel (1991) for linear programming in 2 dimensions that takes only time O(n) for n constraints (in expectation). It’s de\ufb01nitely worth a close inspection, so I thought I would write a short article about it. Note that my presentation of this algorithm assumes that there … Continue reading Everything is Easy in Low Dimensions (Part 1): Linear Programming<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/94"}],"collection":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=94"}],"version-history":[{"count":2,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/94\/revisions"}],"predecessor-version":[{"id":96,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=\/wp\/v2\/posts\/94\/revisions\/96"}],"wp:attachment":[{"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=94"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=94"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aarondefazio.com\/tangentially\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=94"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}