Report

A Faster Algorithm for Linear Programming and the Maximum Flow Problem I Yin Tat Lee (MIT, Simons) Joint work with Aaron Sidford THE PROBLEM Linear Programming Consider the linear program (LP) min ≥ where is a × matrix. • is the number of constraints. • is the number of variables. = 2, = 6 = 2, = ∞ = # of constraints = # of variables Previous Results • All of them are iterative methods. • Start with some initial point . • While is not optimal – Improve • Time = (#) × ( ) • This talk focus on #iter. We call it efficient if • Polynomial time • Doesn’t use LP solver = # of constraints Previous = # of variables (log( −1 )) is omitted) Results (Selected) Year Author # of iter Cost per iter Efficient steps 1947 Dantzig 2 Pivot Yes 1979 Khachiyan 2 Update the Ellipsoid Yes 1984 Karmarkar Solve linear systems Yes 1986 Renegar Solve linear systems Yes 1989 Vaidya Matrix inverse Yes 1994 Nesterov, Nemirovskii Compute volume No ( ) Solve Linear Systems Yes ( ) Solve Linear Systems Yes 2013 Lee, Sidford 1/4 Remark: In 2013, Mądry shows how to obtain 3/7 iters for certain LPs! Outline = # of constraints = # of variables (log( −1 )) is omitted) Year Author # of iter Cost per iter Efficient steps 1947 Dantzig 2 Pivot Yes 1979 Khachiyan 2 Update the Ellipsoid Yes 1984 Karmarkar Solve linear systems Yes 1986 Renegar Solve linear systems Yes 1989 Vaidya Matrix inverse Yes 1994 Nesterov, Nemirovskii Compute volume No ( ) Solve Linear Systems Yes ( ) Solve Linear Systems Yes 2013 Lee, Sidford 1/4 Remark: In 2013, Mądry shows how to obtain 3/7 iters for certain LPs! LP AND CENTER A general framework We can solve linear program by maintaining center. Somehow, get a “center” first Put the cost constraint there and move it. Say we can move portion closer each time After ( −1 ) steps, we are done. A general framework We can solve linear program by maintaining center. Somehow, get a “center” first Put the cost constraint there and move it. Why center? After ( Say we can move portion closer each time −1 ) steps, we are done. What if we don’t try to maintain a center? • It is just like simplex method. It is good now. Oh, it touches. What to do? Still good. ….. What if we don’t try to maintain a center? • It is just like simplex method. It is good now. Still good. Avoid bad decision by using global ….. Oh, it touches. What to do? information! A general framework Formally, we have (say = 0): • = 22014 . Find the center of ≤ , ≥ • While is large – ← (1 − ) for some fixed > 0 – Update the center of ≤ , ≥ This is called interior point method. The initial point is easy: min +≥ ,≥0 22014 + A general way to define a center Let be a smooth convex function on Ω such that • → +∞ as → Ω. For example, Standard log barrier: ps x = − ln − = − ln( ) Center = argmin Barrier Function QUALITY OF A CENTER Rounding • Assume center is induced by some barrier function . • Look at the ellipsoid induced by at the center . • Call is rounding if ⊂ Ω ⊂ for some . Self concordant barrier • is a -self concordant barrier function for Ω if – is smooth. – gives rounding. is not smooth enough Bad rounding. Rounding Algorithm For general barrier function : • Repeat – Tighten the cost constraint – Maintain the rounding ellipsoid induced by . Why iterations? Why iterations? Think = − ln . • Newton Method (Using smoothness) Given − min () < 0.5, we can find the center in (1) steps. x Why iterations? Let be the old center. Using the smoothness, we have − 1 − min ≤ ≤ . x − 2 Why iterations? So, we need − 1 ≤ . − 2 It takes iters. Why iterations? • We can reduce the gap by 1/ . Roughly Speaking: Smoothness + rounding gives log( −1 ) iterations LP solvers. Quality of analytic center is arbitrary bad in ! • Recall the standard log barrier function = − ln − = − =1 ln . =1 • The center = argmin is called analytic center. Is it tight? • In practice, it takes ≤ 60 steps. • Mizuno, Todd, Ye showed it is “usually” correct on first step. • In 2014, Mut and Terlaky showed an example really takes Ω log −1 iterations where is exponential in . UNIVERSAL BARRIER FUNCTION Universal Barrier Function Theorem [NN94]: For any convex set Ω ∈ , = −log ( Ω − ) is a ()-self concordant barrier function. “Smaller” set has larger polar. Hence, → ∞ as → Ω Note that 2 ~ Ω − . Kannan-Lovasz-Simonovits Lemma: For any convex set Ω, the second moment matrix (Ω) = gives a () rounding of Ω. Ω The cost of Universal Barrier • To get second moment matrix, you need 1 sampling. • To get 1 sampling, you need to do (1) iters of Markov chain. • To do 1 iter of Markov chain, you need to implement separation oracle for Ω − . • If Ω = { ≥ }, one need to solve an LP. Hence, one iteration requires solving (1) many LPs. The problem: Get an efficient () self concordant barrier function. VOLUMETRIC BARRIER FUNCTION Volumetric Barrier Function In 1989, Vaidya showed 1 2 = log det () + () 2 where = − ln . Why it is volumetric? For example: It is a 1/2 barrier. Volumetric Barrier Log Barrier Why Volumetric is good? 1 2 = log det () + () 2 Around , we have −1 + ~ − where = log () −1 . 1 0 2 + 32 1 0 . = 1 , = 9 , = 1. Example: = 3 0 . Then, = 1 10 2 10 3 0 22 0 2 In general, = , 0 ≤ ≤ 1, if the ℎ row is repeated, is decreased by 2. For [0,1] interval with 0 repeated times: 1 −1 = 1 ⋮ 1/3 −1 = 1 ⋮ OUR BARRIER FUNCTION Repeated Volumetric Barrier Function 1 2 = log det () + () 2 1 () 2 () log det () + ()? 2 (1) How about (+1) = Suppose () = − (+1) ~ − So, we have (+1) () log , around , we have −1 () + log . What is that? = We call (∞) = − ∞ ∞ () () −1 + . () log where () = ∞ (∞) −1 . satisfies What is that weight? 1 2 • Let = ( )/ . ∞ () = (∞) −1 . If ≤ 1 for all , the ellipsoid is inside. (∞) The represents John ellipsoid of { −1 ∞ ≤ 1} Our Condition (John Ellipsoid): = 1 if ≠ 0. Repeated Volumetric Barrier Function • Recall (∞) ~ ln det 2 We get ∞ ~ − ln det −1 (∞) −1 (∞) ~ − ln vol ℎ Ω ∩ (2x − Ω) . Symmetrize Find John Ellipsoid The barrier function is not perfect! • The path is piecewise smooth because it may not touch every constraint. • (∞) = max =,≥0 lndet( −1 −1 ) Our Barrier Function • Standard Log Barrier: = − • Volumetric Barrier: 1 2 = log det () + () 2 • John Ellipsoid Barrier: ∞ () = max lndet( −1 −1 ) =,≥0 • Regularized John Ellipsoid Barrier (1): −1 () 1−log −1 ) max lndet( −1 ≥0 + − • Regularized John Ellipsoid Barrier (2): −1 −1 max ln det − ln − ln ≥0 Lewis Weight We call is −1 Lewis weight for if max lndet( ≥0 1−log−1 ( ) −1 ) . 1 1 − 2 ( ) = Thanks to Cohen and Peng, we know • Let be max 1, 2 ( ) rows sample of accordingly to , ~ ∀. 2 1− • = is the maximizer of − det ≤1 ≤1 i.e, the maximum ellipsoid such that it “insides” the polytopes. • For = ∞, { ≤ 1} is the John ellipsoid for {|| ≤ 1}. Computing Lewis Weight • Cohen and Peng showed how to compute it when < 4. • The repeated (1) volumetric barrier: = /, (+1) = () + . (log()) After renormalization, gives “∞ “Lewis” weight: 1 ~ ( 2 ). • Cohen, L., Peng, Sidford shows that in fact a similar algorithm find constant “approximate” Lewis weight for > 2 in (1). CONCLUSION = # of constraints = # of variables Our Barrier Given any polytope {Ax ≥ }, let = − ln − ln . Theorem: The barrier function gives ( log −1 ) iterations algorithm for LP of the form min . max ln det −1 −1 ≥0 ≥ Algorithm: • While – Move the cost constraint – Maintain the regularized John ellipsoid = # of constraints = # of variables However… • My goal is to design general LP algo fast enough to beat the best maxflow algorithm! • We obtained min ≥ Compute log −1 −1