A Faster Algorithm for Linear Programming and the Maximum Flow Problem
A comprehensive overview of a new algorithm for linear programming and the maximum flow problem developed by Yin Tat Lee and Aaron Sidford from MIT and Simons. The algorithm aims to improve efficiency by reducing the number of iterations required to reach the optimal solution. It discusses the history of linear programming algorithms, previous results in the field, and outlines the approach taken by Lee and Sidford. The presentation highlights the significance of efficient algorithms that do not rely on standard linear programming solvers.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A Faster Algorithm for Linear Programming and the Maximum Flow Problem I Yin Tat Lee (MIT, Simons) Joint work with Aaron Sidford
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,? =
Previous Results ? = # of constraints ? = # of variables All of them are iterative methods. Start with some initial point ?. While ? is not optimal Improve ? We call it efficient if Polynomial time Doesn t use LP solver Time = (#????) (???? ??? ????) This talk focus on #iter.
Previous Results (Selected) ? = # of constraints ? = # of variables (log(? 1)) is omitted) Year 1947 1979 1984 1986 1989 Author Dantzig Khachiyan Karmarkar Renegar Vaidya Nesterov, Nemirovskii # of iter 2? ?2 Cost per iter Pivot Update the Ellipsoid Solve linear systems Solve linear systems Matrix inverse Efficient steps Yes Yes Yes Yes Yes ? ? ??1/4 1994 Compute volume No ? ?( ?) Solve Linear Systems Yes 2013 Lee, Sidford Solve Linear Systems Yes ?( ????) 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 1947 1979 1984 1986 1989 Author Dantzig Khachiyan Karmarkar Renegar Vaidya Nesterov, Nemirovskii # of iter 2? ?2 Cost per iter Pivot Update the Ellipsoid Solve linear systems Solve linear systems Matrix inverse Efficient steps Yes Yes Yes Yes Yes ? ? ??1/4 1994 Compute volume No ? ?( ?) Solve Linear Systems Yes 2013 Lee, Sidford Solve Linear Systems Yes ?( ????) Remark: In 2013, M dry shows how to obtain ?3/7 iters for certain LPs!
A general framework We can solve linear program by maintaining center. Put the cost constraint there and move it. Somehow, get a center first 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. Put the cost constraint there and move it. Somehow, get a center first Why center? Say we can move ? portion closer each time After ?(? 1) steps, we are done.
What if we dont try to maintain a center? It is just like simplex method. Still good. It is good now. .. Oh, it touches. What to do?
What if we dont try to maintain a center? It is just like simplex method. Still good. It is good now. Avoid bad decision by using global information! .. Oh, it touches. What to do?
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: ???+? ??,? 022014? + ??? min
A general way to define a center Let ? be a smooth convex function on such that ? ? + as ? ? . Barrier Function For example, Standard log barrier: psx = ln ??? ?? = ln(??) Center = argmin ? ?
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. Bad rounding. ? is not smooth enough
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 x steps. ? (?) < 0.5, we can find the center in ?(1)
Why ? iterations? Let ? be the old center. Using the smoothness, we have ???? ? ???? ??? 1 ????? min 2. ? ??? x
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 ??? ?? = ln ?? . ?=1 ?=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 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 2logdet?2??(?) +? ???(?) where ??? = ?ln??. Why it is volumetric? For example: It is a ??1/2 barrier. Volumetric Barrier Log Barrier
Why Volumetric is good? ??? =1 2logdet?2??(?) +? ???(?) Around ?, we have 1? +? ??? ~ ???? log??(?) ? ? where ?? ??? 1???. ??? = ?? 1 3 0 0 0 2 . Then, ??? =12+ 32 0 22. ?1= 1 10, ?2= 9 Example: ? = 10, ?3= 1. 0 In general, ??= ?, 0 ?? 1, if the ?? row is repeated, ?? is decreased by 2. For [0,1] interval with 0 repeated ? times: ?1/3 1 1 1 ? 1? = ? 1? =
Repeated Volumetric Barrier Function ?(1)? =1 2logdet?2??(?) +? ???(?) How about ?(?+1)? =1 ? ??(?)(?)? 2logdet?2?(?) (?) + (?) log??, around ?, we have 1? +? What is that? Suppose ?(?)? = ??? ?(?+1)? ~ ?(?)?? ?? log??? . ? ? So, we have (?+1)= ?? (?). 1? + ?? ?(?)?? ?? (?)log?? where ?? (?) = ?? satisfies We call ?( )? = ?? 1? . ?( )?? ??
What is that weight? 1 2?)/??. Let ??= ??(? (?) = ?? 1? . ?( )?? ?? If ?? 1 for all ?, the ellipsoid is inside. ( ) represents John 1? 1} The ?? ellipsoid of { ?? Our Condition (John Ellipsoid): ??= 1 if ?? 0.
Repeated Volumetric Barrier Function Recall ?( )? ~lndet ?2? ? 1?( )?? 1? ~ lndet ??? We get ?( )~ ln vol ?? ?????????? (2x ) . Find John Ellipsoid Symmetrize
The barrier function is not perfect! The path is piecewise smooth because it may not touch every constraint. ?( )= ?=?,? 0lndet(??? 1?? 1?) max
Our Barrier Function Standard Log Barrier: ??? = ???? Volumetric Barrier: ??? =1 2logdet?2??(?) +? ???(?) John Ellipsoid Barrier: ? (?) = ?=?,? 0lndet(??? 1?? 1?) max Regularized John Ellipsoid Barrier (1): ? 0lndet(??? 1?1 log 1(? Regularized John Ellipsoid Barrier (2): ? 0lndet??? 1?? 1? ? ?)? 1?) +? max ? ???? ?? ? ??ln?? ? max ? ln??
?? Lewis Weight ? 0lndet(??? 1?1 log 1(? ?)? 1?). max We call ? is ?? Lewis weight for ? if 1 2 1 ??) ??= ??(? Thanks to Cohen and Peng, we know Let ? be ?(?max 1,? 2) rows sample of ? accordingly to ??, ???~ ??? ?. ? = ???1 2 ?? is the maximizer of ???det? ??????? ?? ????? 1??? i.e, the maximum ellipsoid such that it insides the polytopes. For ? = , {???? 1} is the John ellipsoid for {|??| 1}. ? 1
Computing ?? Lewis Weight Cohen and Peng showed how to compute it when ? < 4. (1)= ?/?, The repeated volumetric barrier: ?? ?? (?+1)= ?? ?. ?(?)? + ?? (log(?))gives ? Lewis weight: 1 2?). After renormalization, ?? ??? ~??(? Cohen, L., Peng, Sidford shows that in fact a similar algorithm find constant approximate ?? Lewis weight for ? > 2 in ?(1).
Our Barrier ? = # of constraints ? = # of variables Given any polytope {Ax ?}, let ? 0lndet??? 1?? 1? ? Theorem: The barrier function ? gives ?( ?log ? 1) iterations algorithm for LP of the form min ? ??ln?? ? ? ? = max ? ln??. ?? ????. Algorithm: While Move the cost constraint Maintain the regularized John ellipsoid
However ? = # of constraints ? = # of variables My goal is to design general LP algo fast enough to beat the best maxflow algorithm! We obtained ?? ???? Compute ????? 1 min ? ?log ? 1
