import%20marimo%0A%0A__generated_with%20%3D%20%220.25.2%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20sys%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20start%20%3D%20Path(__file__).resolve().parent%20if%20%22__file__%22%20in%20globals()%20else%20Path.cwd().resolve()%0A%20%20%20%20for%20candidate%20in%20(start%2C%20*start.parents)%3A%0A%20%20%20%20%20%20%20%20if%20(candidate%20%2F%20%22fomtools%22).is_dir()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20repo_root%20%3D%20candidate%0A%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20repo_root%20%3D%20start%0A%0A%20%20%20%20if%20str(repo_root)%20not%20in%20sys.path%3A%0A%20%20%20%20%20%20%20%20sys.path.insert(0%2C%20str(repo_root))%0A%0A%20%20%20%20from%20docs.tutorials.helper_functions.network%20import%20(%0A%20%20%20%20%20%20%20%20make_network_data%2C%0A%20%20%20%20%20%20%20%20pdhg_step%2C%0A%20%20%20%20)%0A%0A%20%20%20%20np.set_printoptions(precision%3D5)%20%20%23%20Print%20few%20decimal%20places%0A%20%20%20%20np.set_printoptions(suppress%3DTrue)%20%20%23%20Suppress%20scientific%20notation%0A%20%20%20%20return%20cp%2C%20make_network_data%2C%20mo%2C%20np%2C%20pdhg_step%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Problem%20setup%3A%20Network%20flow%20optimization%0A%0A%20%20%20%20%5BBack%20to%20the%20verification%20tutorials%5D(.%2F)%0A%0A%20%20%20%20In%20this%20tutorial%2C%20we%20verify%20first-order%20methods%20for%20the%20minimum-cost%20network%20flow%20example%20from%20Section%204.2%20of%20%5BExact%20Verification%20of%20First-Order%20Methods%20via%20Mixed-Integer%20Linear%20Programming%5D(https%3A%2F%2Farxiv.org%2Fabs%2F2412.11330).%0A%0A%20%20%20%20Suppose%20that%20we%20are%20given%20a%20set%20of%20%24n_s%24%20supply%20nodes%20and%20%24n_d%24%20demand%20nodes%2C%20which%20constructs%20a%20bipartite%20graph%20with%20capacitated%20directed%20edges%20from%20supply%20nodes%20to%20demand%20nodes.%0A%20%20%20%20Let%20%24A_s%24%20and%20%24A_d%24%20be%20submatrices%20corresponding%20to%20supply%20nodes%20and%20demand%20nodes%2C%20respectively.%0A%20%20%20%20For%20each%20edge%20%24i%24%2C%20let%20%24c_i%24%20be%20the%20flow%20capacity%2C%20%24%5Cmu_i%24%20be%20the%20cost%20of%20sending%20a%20unit%20of%20flow%2C%20and%20%24z_i%24%20be%20the%20variable%20representing%20the%20amount%20of%20flow%20sent.%0A%20%20%20%20Finally%2C%20let%20%24b_s%20%5Cge%200%24%20be%20the%20vector%20of%20supply%20amounts%20available%20at%20each%20supply%20node%20and%20%24x%20%5Cle%200%24%20be%20the%20vector%20of%20requested%20demand%20amount%20for%20each%20demand%20node.%0A%0A%20%20%20%20Consider%20the%20following%20minimum%20cost%20network%20flow%20problem%3A%0A%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%26%20%5Cmu%5ET%20z%20%5C%5C%0A%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%0A%20%20%20%20%20%20%20%20%26%20A_s%20z%20%5Cle%20b_s%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20A_d%20z%20%3D%20x%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%200%20%5Cle%20z%20%5Cle%20c.%0A%20%20%20%20%5Cend%7Barray%7D%0A%0A%20%20%20%20The%20demand%20vector%20%24x%24%20is%20treated%20as%20the%20problem%20parameter.%20The%20verification%20problem%20will%20search%20over%20%24x%20%5Cin%20%5Cmathcal%7BX%7D%24%20and%20over%20bounded%20initial%20primal-dual%20iterates.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(make_network_data%2C%20np)%3A%0A%20%20%20%20%23%20Generate%20bipartite%20graph%20with%20n_s%20supply%20nodes%20and%20n_d%20demand%20nodes%2C%0A%20%20%20%20%23%20whose%20edges%20are%20added%20with%20probability%20p%20%3D%200.5.%0A%20%20%20%20n_s%20%3D%206%0A%20%20%20%20n_d%20%3D%203%0A%20%20%20%20p%20%3D%200.5%0A%0A%20%20%20%20A_s%2C%20A_d%2C%20b_s%2C%20c%2C%20mu%20%3D%20make_network_data(%0A%20%20%20%20%20%20%20%20n_supply%3Dn_s%2C%0A%20%20%20%20%20%20%20%20n_demand%3Dn_d%2C%0A%20%20%20%20%20%20%20%20edge_probability%3Dp%2C%0A%20%20%20%20%20%20%20%20graph_seed%3D1%2C%0A%20%20%20%20%20%20%20%20data_seed%3D2%2C%0A%20%20%20%20)%0A%20%20%20%20n_e%20%3D%20A_s.shape%5B1%5D%0A%0A%20%20%20%20d_lb%2C%20d_ub%20%3D%20-7.%2C%20-6.%20%20%23%20demand%0A%20%20%20%20c_lb%2C%20c_ub%20%3D%20%205.%2C%20%205.%20%20%23%20capacity%0A%0A%20%20%20%20%23%20Parameter%20set%20X%20%3D%20%5Bx_lb%2C%20x_ub%5D%20of%20demands%0A%20%20%20%20x_lb%20%3D%20d_lb%20*%20np.ones(n_d)%0A%20%20%20%20x_ub%20%3D%20d_ub%20*%20np.ones(n_d)%0A%20%20%20%20z0_lb%2C%20z0_ub%20%3D%20np.zeros(n_e)%2C%20c.copy()%0A%20%20%20%20v0_lb%2C%20v0_ub%20%3D%20np.zeros(n_s)%2C%20np.ones(n_s)%0A%20%20%20%20w0_lb%2C%20w0_ub%20%3D%20-np.ones(n_d)%2C%20np.ones(n_d)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20A_d%2C%0A%20%20%20%20%20%20%20%20A_s%2C%0A%20%20%20%20%20%20%20%20b_s%2C%0A%20%20%20%20%20%20%20%20c%2C%0A%20%20%20%20%20%20%20%20c_lb%2C%0A%20%20%20%20%20%20%20%20c_ub%2C%0A%20%20%20%20%20%20%20%20mu%2C%0A%20%20%20%20%20%20%20%20n_d%2C%0A%20%20%20%20%20%20%20%20n_e%2C%0A%20%20%20%20%20%20%20%20n_s%2C%0A%20%20%20%20%20%20%20%20v0_lb%2C%0A%20%20%20%20%20%20%20%20v0_ub%2C%0A%20%20%20%20%20%20%20%20w0_lb%2C%0A%20%20%20%20%20%20%20%20w0_ub%2C%0A%20%20%20%20%20%20%20%20x_lb%2C%0A%20%20%20%20%20%20%20%20x_ub%2C%0A%20%20%20%20%20%20%20%20z0_lb%2C%0A%20%20%20%20%20%20%20%20z0_ub%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20make%20sure%20that%20the%20optimization%20problem%20with%20randomly%20generated%20data%20has%20a%20solution.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A_d%2C%20A_s%2C%20b_s%2C%20c%2C%20cp%2C%20mu%2C%20n_e%2C%20x_ub)%3A%0A%20%20%20%20%23%20Check%20the%20feasibility%20of%20the%20generated%20min%20cost%20flow%20problem%0A%20%20%20%20f%20%3D%20cp.Variable(n_e)%0A%0A%20%20%20%20constraints_check%20%3D%20%5B%0A%20%20%20%20%20%20%20%20A_s%20%40%20f%20%3C%3D%20b_s%2C%0A%20%20%20%20%20%20%20%20A_d%20%40%20f%20%3D%3D%20x_ub%2C%0A%20%20%20%20%20%20%20%200%20%3C%3D%20f%2C%20f%20%3C%3D%20c%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20problem_check%20%3D%20cp.Problem(objective%3Dcp.Minimize(mu.T%40f)%2C%20constraints%3Dconstraints_check)%0A%20%20%20%20problem_check.solve(solver%3Dcp.SCS)%0A%0A%20%20%20%20print(f%22The%20problem%20is%20%7Bproblem_check.status%7D.%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20First-order%20method%3A%20PDHG%0A%0A%20%20%20%20We%20solve%20this%20problem%20using%20the%20standard%20Chambolle-Pock%20method%2C%20or%20Primal-dual%20Hybrid%20Gradient%20(PDHG)%3A%0A%0A%20%20%20%20%5Cbegin%7Barray%7D%7Brcl%7D%0A%20%20%20%20%20%20%20%20z%5E%7Bk%2B1%7D%20%26%3D%26%20%5CPi_%7B%5B0%2C%20c%5D%7D%20%5Cbig(%20z%5Ek%20-%20%5Ceta%20(%5Cmu%20%2B%20A_s%5ET%20v%5Ek%20-%20A_d%5ET%20w%5Ek)%20%5Cbig)%20%5C%5C%0A%20%20%20%20%20%20%20%20v%5E%7Bk%2B1%7D%20%26%3D%26%20%5CPi_%7B%5Cmathbf%7BR%7D_%2B%7D%20%5Cbig(%20v%5Ek%20%2B%20%5Ceta%20%5Cbig(%20-%20b_s%20%2B%20A_s%20(2%20z%5E%7Bk%2B1%7D%20-%20z%5Ek)%20%5Cbig)%20%5Cbig)%20%5C%5C%0A%20%20%20%20%20%20%20%20w%5E%7Bk%2B1%7D%20%26%3D%26%20w%5Ek%20%2B%20%5Ceta%20%5Cbig(%20x%20-%20A_d%20(2%20z%5E%7Bk%2B1%7D%20-%20z%5Ek)%20%5Cbig).%0A%20%20%20%20%5Cend%7Barray%7D%0A%0A%20%20%20%20Here%20%24%5CPi_%7B%5B0%2C%20c%5D%7D%24%20is%20projection%20onto%20the%20flow-capacity%20box%20(the%20%60satlin%60%20step)%20and%20%24%5CPi_%7B%5Cmathbf%7BR%7D_%2B%7D%24%20is%20projection%20onto%20the%20nonnegative%20orthant%20(the%20%60relu%60%20step).%0A%20%20%20%20We%20choose%20%24%5Ceta%20%3D%200.5%20%2F%20L%24%2C%20where%20%24L%20%3D%20%5C%7C%20%5Cbegin%7Bbmatrix%7D%20-%20A_s%5ET%20%26%20A_d%5ET%20%5Cend%7Bbmatrix%7D%20%5C%7C_2%24.%0A%0A%20%20%20%20The%20performance%20metric%20is%20the%20infinity%20norm%20of%20the%20scaled%20KKT%20fixed-point%20residual%20induced%20by%20the%20PDHG%20update.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A_d%2C%20A_s%2C%20np)%3A%0A%20%20%20%20%23%20Step%20size%20choice%0A%20%20%20%20L%20%3D%20np.linalg.norm(np.hstack(%5B-%20A_s.T%2C%20A_d.T%5D)%2C%202)%0A%20%20%20%20eta%20%3D%200.5%20%2F%20L%0A%20%20%20%20return%20(eta%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Every%20verification%20mode%20below%20(simulator%20and%20MIP-VP)%20drives%20this%20*same*%20recurrence%20and%20residual.%20In%20the%20current%20experiment%2C%20capacity%2C%20cost%2C%20and%20supply%20have%20zero-width%20bounds%2C%20so%20the%20MIP%20represents%20them%20as%20fixed%20symbolic%20parameters%20at%20their%20nominal%20values.%0A%20%20%20%20Each%20cell%20rolls%20out%20the%20recurrence%20directly%20by%20iterating%20%60pdhg_step%60%20from%20the%20initial%20iterates%20%24(z%5E0%2C%20v%5E0%2C%20w%5E0)%24%20over%20the%20horizon%20%24K%24%2C%20registering%20the%20scaled%20KKT%20residual%20at%20each%20step%20as%20an%20objective%20along%20the%20way.%0A%20%20%20%20Setting%20%60momentum%3DTrue%60%20applies%20the%20extrapolation%20%24%5Ctilde%20z%5Ek%20%3D%20z%5Ek%20%2B%20%5Cbeta_k(z%5Ek%20-%20z%5E%7Bk-1%7D)%24%0A%20%20%20%20(see%20below)%20before%20the%20dual%20updates.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Verification%20Problem%0A%0A%20%20%20%20We%20verify%20the%20performance%20of%20PDHG%20and%20its%20momentum%20variant%20up%20to%20a%20fixed%20iteration%20budget%20%24K%3E0%24.%20As%20in%20the%20NNLS%20tutorial%2C%20we%20compare%20randomly%20sampled%20simulations%20with%20exact%20MIP%20verification.%20Unlike%20NNLS%2C%20there%20is%20no%20PEPit%20comparison%20here%3B%20the%20reason%20is%20explained%20alongside%20the%20figures%20below.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20K%20%3D%2022%20%20%23%20Maximum%20iteration%20number%0A%20%20%20%20return%20(K%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Simulator%20class%0A%0A%20%20%20%20We%20first%20simulate%20the%20PDHG%20algorithm%20on%20given%20problem%20instances%20by%20randomly%20sampling%20the%20parameter%20%24x%24%20(demand%20vector)%20over%20the%20parameter%20set%20%24%5Cmathcal%7BX%7D%24%20and%20the%20initial%20iterates%20%24(z%5E0%2C%20v%5E0%2C%20w%5E0)%24%20over%20their%20prescribed%20boxes.%20The%20samples%20are%20drawn%20once%20below%20and%20reused%20by%20every%20simulation%20cell%20so%20that%20all%20comparisons%20share%20the%20same%20instances.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(n_d%2C%20n_s%2C%20np%2C%20v0_lb%2C%20v0_ub%2C%20w0_lb%2C%20w0_ub%2C%20x_lb%2C%20x_ub%2C%20z0_lb%2C%20z0_ub)%3A%0A%20%20%20%20_n_samples%20%3D%2010000%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(0)%0A%20%20%20%20x_samples%20%3D%20_rng.uniform(low%3Dx_lb%2C%20high%3Dx_ub%2C%20size%3D(_n_samples%2C%20n_d))%0A%20%20%20%20z0_samples%20%3D%20_rng.uniform(low%3Dz0_lb%2C%20high%3Dz0_ub%2C%20size%3D(_n_samples%2C%20len(z0_lb)))%0A%20%20%20%20v0_samples%20%3D%20_rng.uniform(low%3Dv0_lb%2C%20high%3Dv0_ub%2C%20size%3D(_n_samples%2C%20n_s))%0A%20%20%20%20w0_samples%20%3D%20_rng.uniform(low%3Dw0_lb%2C%20high%3Dw0_ub%2C%20size%3D(_n_samples%2C%20n_d))%0A%20%20%20%20return%20v0_samples%2C%20w0_samples%2C%20x_samples%2C%20z0_samples%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Meanwhile%2C%20the%20simulation%20will%20be%20run%20through%20following%20function.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A_d%2C%20A_s%2C%20b_s%2C%20c%2C%20eta%2C%20mu%2C%20n_d%2C%20n_e%2C%20n_s%2C%20np%2C%20pdhg_step)%3A%0A%20%20%20%20import%20fomtools%20as%20ft%0A%0A%20%20%20%20def%20maximize_residual(vp%2C%20residual%2C%20ord)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Maximize%20%60%60%7C%7Cresidual%7C%7C_ord%60%60%2C%20squared%20for%20%60%60ord%3D2%60%60%20(%60%60ft.sum_squares%60%60).%22%22%22%0A%20%20%20%20%20%20%20%20vp.maximize(ft.sum_squares(residual)%20if%20ord%20%3D%3D%202%20else%20ft.norm(residual%2C%20ord))%0A%0A%20%20%20%20def%20pdhg_simulation(%0A%20%20%20%20%20%20%20%20x_samples%2C%20z0_samples%2C%20v0_samples%2C%20w0_samples%2C%20K%2C%0A%20%20%20%20%20%20%20%20momentum%3DFalse%2C%20ord%3Dnp.inf%2C%0A%20%20%20%20)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Simulate%20PDHG%20on%20sampled%20instances.%0A%0A%20%20%20%20%20%20%20%20Builds%20a%20simulator-mode%20%3Aclass%3A%60Verifier%60%2C%20registers%20the%20demand%0A%20%20%20%20%20%20%20%20parameter%20and%20the%20initial%20iterates%20%60%60(z0%2C%20v0%2C%20w0)%60%60%20as%20sampled%0A%20%20%20%20%20%20%20%20parameters%2C%20rolls%20out%20the%20PDHG%20recurrence%20with%20%60%60pdhg_step%60%60%2C%0A%20%20%20%20%20%20%20%20and%20simulates%20via%20%60%60vp.solve()%60%60.%20Each%20of%20the%20four%20%60%60*_samples%60%60%20arrays%20has%20shape%0A%20%20%20%20%20%20%20%20%60%60(n_samples%2C%20dim)%60%60%20(a%20single-row%20array%20replays%20one%20instance)%2C%20and%20the%0A%20%20%20%20%20%20%20%20returned%20%60%60residuals%60%60%20has%20shape%20%60%60(n_samples%2C%20K)%60%60.%20Summary%20statistics%0A%20%20%20%20%20%20%20%20(%60%60mean%60%60%2C%20%60%60min%60%60%2C%20%60%60max%60%60%2C%20%60%60final_residuals%60%60%2C%20...)%20are%20available%20on%0A%20%20%20%20%20%20%20%20the%20returned%20instance%20%60%60vp%60%60%20via%20%60%60vp%5B...%5D%60%60.%0A%0A%20%20%20%20%20%20%20%20%60%60ord%60%60%20defaults%20to%20%60%60inf%60%60%2C%20matching%20%3Afunc%3A%60pdhg_verification%60%3B%20see%0A%20%20%20%20%20%20%20%20the%20note%20there%20on%20why%20this%20example%20is%20plotted%20in%20the%20infinity%20norm%0A%20%20%20%20%20%20%20%20rather%20than%20the%202-norm.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20vp%20%3D%20ft.Verifier(method%3D'simulator'%2C%20obbt_solver%3DNone)%0A%20%20%20%20%20%20%20%20x_param%20%3D%20vp.parameter(ndim%3Dn_d%2C%20samples%3Dx_samples)%0A%20%20%20%20%20%20%20%20z0%20%3D%20vp.parameter(ndim%3Dn_e%2C%20samples%3Dz0_samples)%0A%20%20%20%20%20%20%20%20v0%20%3D%20vp.parameter(ndim%3Dn_s%2C%20samples%3Dv0_samples)%0A%20%20%20%20%20%20%20%20w0%20%3D%20vp.parameter(ndim%3Dn_d%2C%20samples%3Dw0_samples)%0A%0A%20%20%20%20%20%20%20%20z%2C%20v%2C%20w%20%3D%20z0%2C%20v0%2C%20w0%0A%20%20%20%20%20%20%20%20for%20k%20in%20range(1%2C%20K%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20z%2C%20v%2C%20w%2C%20residual%20%3D%20pdhg_step(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vp%2C%20A_s%2C%20A_d%2C%20eta%2C%20z%2C%20v%2C%20w%2C%20x_param%2C%20c%2C%20mu%2C%20b_s%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20k%3Dk%2C%20momentum%3Dmomentum%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20maximize_residual(vp%2C%20residual%2C%20ord)%0A%0A%20%20%20%20%20%20%20%20residuals%20%3D%20vp.solve()%0A%20%20%20%20%20%20%20%20return%20vp%2C%20residuals%0A%0A%20%20%20%20return%20ft%2C%20maximize_residual%2C%20pdhg_simulation%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Running%20%60_vp.solve()%60%20returns%20one%20residual%20history%20per%20sampled%20instance%2C%20which%20we%20summarize%20by%20averages%20and%20empirical%20quantiles.%20After%20calling%20%60solve()%60%2C%20summary%20statistics%20are%20also%20available%20directly%20on%20%60_vp%60%2C%20including%20%60mean%60%2C%20%60std%60%2C%20%60min%60%2C%20%60max%60%2C%20%60median%60%2C%20%60empirical_risk%60%2C%20%60risk_bound%60%2C%20%60n_samples%60%2C%20%60n_iterations%60%2C%20%60runtime%60%2C%20%60time_per_sample%60%2C%20and%20%60throughput%60.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20np%2C%20pdhg_simulation%2C%20v0_samples%2C%20w0_samples%2C%20x_samples%2C%20z0_samples)%3A%0A%20%20%20%20_vp%2C%20_residuals%20%3D%20pdhg_simulation(%0A%20%20%20%20%20%20%20%20x_samples%2C%20z0_samples%2C%20v0_samples%2C%20w0_samples%2C%20K%2C%0A%20%20%20%20%20%20%20%20momentum%3DFalse%2C%20ord%3Dnp.inf%2C%0A%20%20%20%20)%0A%0A%20%20%20%20print(%0A%20%20%20%20%20%20%20%20f%22Summary%20statistics%3A%5Cn%22%0A%20%20%20%20%20%20%20%20f%22mean%3A%20%7B_vp%5B'mean'%5D%3A.6e%7D%5Cn%22%0A%20%20%20%20%20%20%20%20f%22min%3A%20%7B_vp%5B'min'%5D%3A.6e%7D%5Cn%22%0A%20%20%20%20%20%20%20%20f%22max%3A%20%7B_vp%5B'max'%5D%3A.6e%7D%5Cn%22%0A%20%20%20%20%20%20%20%20f%22median%3A%20%7B_vp%5B'median'%5D%3A.6e%7D%5Cn%22%0A%20%20%20%20)%0A%0A%20%20%20%20simulation_residuals_pdhg%20%3D%20np.mean(_residuals%2C%20axis%3D0)%0A%20%20%20%20%23%20Quantile%201.0%20gives%20the%20in-sample%20worst%20case%3B%20indices%20are%20%5B90%25%2C%2050%25%2C%2010%25%2C%20max%5D.%0A%20%20%20%20simulation_residual_quantiles_pdhg%20%3D%20np.quantile(_residuals%2C%20%5B0.90%2C%200.50%2C%200.10%2C%201.0%5D%2C%20axis%3D0)%0A%20%20%20%20return%20simulation_residual_quantiles_pdhg%2C%20simulation_residuals_pdhg%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Momentum%20PDHG%20simulation%0A%0A%20%20%20%20We%20also%20consider%20a%20momentum%20variant%20of%20PDHG.%20After%20the%20primal%20update%2C%0A%20%20%20%20the%20method%20extrapolates%20the%20flow%20iterate%20as%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Ctilde%20z%5E%7Bk%7D%20%3D%20z%5E%7Bk%7D%20%2B%20%5Cbeta_k(z%5E%7Bk%7D%20-%20z%5E%7Bk-1%7D)%2C%0A%20%20%20%20%24%24%0A%0A%20%20%20%20with%20%24%5Cbeta_k%20%3D%20(k-1)%2F(k%2B2)%24%20as%20in%20the%20NNLS%20tutorial%2C%20and%20uses%20%24%5Ctilde%20z%5Ek%24%20in%20the%20dual%20updates.%20This%20reuses%20the%20same%0A%20%20%20%20%60pdhg_simulation%60%20helper%20and%20the%20samples%20drawn%20above%2C%20with%20%60momentum%3DTrue%60.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20np%2C%20pdhg_simulation%2C%20v0_samples%2C%20w0_samples%2C%20x_samples%2C%20z0_samples)%3A%0A%20%20%20%20_%2C%20_residuals%20%3D%20pdhg_simulation(%0A%20%20%20%20%20%20%20%20x_samples%2C%20z0_samples%2C%20v0_samples%2C%20w0_samples%2C%20K%2C%0A%20%20%20%20%20%20%20%20momentum%3DTrue%2C%20ord%3Dnp.inf%2C%0A%20%20%20%20)%0A%20%20%20%20simulation_residuals_pdhg_mom%20%3D%20np.mean(_residuals%2C%20axis%3D0)%0A%20%20%20%20%23%20Quantile%201.0%20gives%20the%20in-sample%20worst%20case%3B%20indices%20are%20%5B90%25%2C%2050%25%2C%2010%25%2C%20max%5D.%0A%20%20%20%20simulation_residual_quantiles_pdhg_mom%20%3D%20np.quantile(_residuals%2C%20%5B0.90%2C%200.50%2C%200.10%2C%201.0%5D%2C%20axis%3D0)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20simulation_residual_quantiles_pdhg_mom%2C%0A%20%20%20%20%20%20%20%20simulation_residuals_pdhg_mom%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20plot%20the%20in-sample%20mean%20and%2010%25-90%25%20empirical%20quantile%20band%20of%20the%20residual%20against%20the%20horizon%20%24K%24%2C%20together%20with%20the%20sample%20worst-case%20instance%2C%20for%20PDHG%20and%20its%20momentum%20variant%20together.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20K%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg_mom%2C%0A%20%20%20%20simulation_residuals_pdhg%2C%0A%20%20%20%20simulation_residuals_pdhg_mom%2C%0A)%3A%0A%20%20%20%20plt.figure()%0A%20%20%20%20_ks%20%3D%20range(1%2C%20K%20%2B%201)%0A%0A%20%20%20%20plt.plot(_ks%2C%20simulation_residuals_pdhg%2C%20label%3D'PDHG%20(in-sample%20avg)')%0A%20%20%20%20plt.fill_between(%0A%20%20%20%20%20%20%20%20_ks%2C%20simulation_residual_quantiles_pdhg%5B2%5D%2C%20simulation_residual_quantiles_pdhg%5B0%5D%2C%0A%20%20%20%20%20%20%20%20alpha%3D.18%2C%20label%3D'PDHG%20sample%2010%25-90%25%20band'%2C%0A%20%20%20%20)%0A%20%20%20%20plt.plot(%0A%20%20%20%20%20%20%20%20_ks%2C%20simulation_residual_quantiles_pdhg%5B3%5D%2C%20'%3A'%2C%20color%3D'C0'%2C%20linewidth%3D.7%2C%0A%20%20%20%20%20%20%20%20label%3D'PDHG%20sample%20worst-case'%2C%0A%20%20%20%20)%0A%0A%20%20%20%20plt.plot(_ks%2C%20simulation_residuals_pdhg_mom%2C%20label%3D'momentum%20PDHG%20(in-sample%20avg)')%0A%20%20%20%20plt.fill_between(%0A%20%20%20%20%20%20%20%20_ks%2C%20simulation_residual_quantiles_pdhg_mom%5B2%5D%2C%20simulation_residual_quantiles_pdhg_mom%5B0%5D%2C%0A%20%20%20%20%20%20%20%20alpha%3D.18%2C%20label%3D'momentum%20PDHG%20sample%2010%25-90%25%20band'%2C%0A%20%20%20%20)%0A%20%20%20%20plt.plot(%0A%20%20%20%20%20%20%20%20_ks%2C%20simulation_residual_quantiles_pdhg_mom%5B3%5D%2C%20'%3A'%2C%20color%3D'C1'%2C%20linewidth%3D.7%2C%0A%20%20%20%20%20%20%20%20label%3D'momentum%20PDHG%20sample%20worst-case'%2C%0A%20%20%20%20)%0A%0A%20%20%20%20plt.yscale('log')%0A%20%20%20%20plt.xlabel(r'%24K%24')%0A%20%20%20%20plt.ylabel(r'In-sample%20KKT%20residual%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24')%0A%20%20%20%20plt.legend()%0A%20%20%20%20plt.suptitle('PDHG%20vs.%20momentum%20PDHG%20in-sample%20residual%20statistics')%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Algorithm%20verification%20through%20verification%20problem%20(VP)%0A%0A%20%20%20%20%23%23%23%20MIP-VP%0A%20%20%20%20We%20now%20obtain%20worst-case%20guarantees%20by%20solving%20the%20corresponding%20verification%20problem%20with%20a%20MIP%20formulation.%20The%20demand%20vector%20and%20initial%20iterates%20vary%20over%20their%20prescribed%20bounds.%20Capacities%2C%20costs%2C%20and%20supplies%20are%20represented%20as%20parameters%20too%2C%20but%20their%20lower%20and%20upper%20bounds%20coincide%20in%20this%20experiment%2C%20so%20they%20remain%20fixed%20at%20their%20nominal%20values.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20A_d%2C%0A%20%20%20%20A_s%2C%0A%20%20%20%20b_s%2C%0A%20%20%20%20c_lb%2C%0A%20%20%20%20c_ub%2C%0A%20%20%20%20eta%2C%0A%20%20%20%20ft%2C%0A%20%20%20%20maximize_residual%2C%0A%20%20%20%20mu%2C%0A%20%20%20%20n_d%2C%0A%20%20%20%20n_e%2C%0A%20%20%20%20n_s%2C%0A%20%20%20%20np%2C%0A%20%20%20%20pdhg_step%2C%0A%20%20%20%20v0_lb%2C%0A%20%20%20%20v0_ub%2C%0A%20%20%20%20w0_lb%2C%0A%20%20%20%20w0_ub%2C%0A%20%20%20%20x_lb%2C%0A%20%20%20%20x_ub%2C%0A%20%20%20%20z0_lb%2C%0A%20%20%20%20z0_ub%2C%0A)%3A%0A%20%20%20%20def%20pdhg_verification(K%2C%20method%2C%20momentum%3DFalse%2C%20ord%3Dnp.inf%2C%20**verifier_kwargs)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Solve%20the%20PDHG%20verification%20problem%20for%20one%20backend.%0A%0A%20%20%20%20%20%20%20%20Builds%20a%20%60%60Verifier%60%60%20in%20%60%60method%60%60%20mode%2C%20registers%20the%20demand%20parameter%2C%0A%20%20%20%20%20%20%20%20the%20capacity%2C%20cost%2C%20and%20supply%20parameters%2C%20and%20the%20%60%60(z0%2C%20v0%2C%20w0)%60%60%0A%20%20%20%20%20%20%20%20iterate%20boxes%2C%20rolls%20out%20%60%60pdhg_step%60%60%20over%20the%20horizon%20%60%60K%60%60%2C%20and%0A%20%20%20%20%20%20%20%20returns%20%60%60(vp%2C%20residuals)%60%60%20with%20one%20worst-case%20residual%20per%20iteration.%0A%0A%20%20%20%20%20%20%20%20Every%20curve%20in%20this%20notebook%20reports%20%24%5C%5C%7Cr%5Ek%5C%5C%7C_%5C%5Cinfty%24%2C%20so%20%60%60ord%60%60%0A%20%20%20%20%20%20%20%20defaults%20to%20%60%60inf%60%60%3B%20the%20resulting%20MIP%20is%20a%20MILP%20and%20solves%20in%20well%20under%0A%20%20%20%20%20%20%20%20a%20second.%20A%202-norm%20objective%20is%20squared%2C%20so%20its%20value%20is%20square-rooted%20on%0A%20%20%20%20%20%20%20%20return.%20Extra%20%60%60verifier_kwargs%60%60%20(%60%60solver%60%60%2C%20%60%60obbt_solver%60%60%2C%0A%20%20%20%20%20%20%20%20%60%60params%60%60%2C%20...)%20are%20forwarded%20to%20the%20%60%60Verifier%60%60%20constructor.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20vp%20%3D%20ft.Verifier(method%3Dmethod%2C%20**verifier_kwargs)%0A%20%20%20%20%20%20%20%20x_param%20%3D%20vp.parameter(n_d%2C%20lb%3Dx_lb%2C%20ub%3Dx_ub)%0A%20%20%20%20%20%20%20%20capacity%20%3D%20vp.parameter(n_e%2C%20lb%3Dc_lb%20*%20np.ones(n_e)%2C%20ub%3Dc_ub%20*%20np.ones(n_e))%0A%20%20%20%20%20%20%20%20supply%20%3D%20vp.parameter(n_s%2C%20lb%3Db_s%2C%20ub%3Db_s)%0A%20%20%20%20%20%20%20%20cost%20%3D%20vp.parameter(n_e%2C%20lb%3Dmu%2C%20ub%3Dmu)%0A%0A%20%20%20%20%20%20%20%20z%20%3D%20vp.iterate_trajectory(K%20%2B%201%2C%20collapse_expr%3D'auto')%0A%20%20%20%20%20%20%20%20v%20%3D%20vp.iterate_trajectory(K%20%2B%201%2C%20collapse_expr%3D'auto')%0A%20%20%20%20%20%20%20%20w%20%3D%20vp.iterate_trajectory(K%20%2B%201%2C%20collapse_expr%3D'auto')%0A%20%20%20%20%20%20%20%20z%5B0%5D%20%3D%20vp.iterate(n_e%2C%20lb%3Dz0_lb%2C%20ub%3Dz0_ub)%0A%20%20%20%20%20%20%20%20v%5B0%5D%20%3D%20vp.iterate(n_s%2C%20lb%3Dv0_lb%2C%20ub%3Dv0_ub)%0A%20%20%20%20%20%20%20%20w%5B0%5D%20%3D%20vp.iterate(n_d%2C%20lb%3Dw0_lb%2C%20ub%3Dw0_ub)%0A%0A%20%20%20%20%20%20%20%20residuals%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20k%20in%20range(1%2C%20K%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20z%2C%20v%2C%20w%2C%20residual%20%3D%20pdhg_step(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vp%2C%20A_s%2C%20A_d%2C%20eta%2C%20z%2C%20v%2C%20w%2C%20x_param%2C%20capacity%2C%20cost%2C%20supply%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20k%3Dk%2C%20momentum%3Dmomentum%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20maximize_residual(vp%2C%20residual%2C%20ord)%0A%20%20%20%20%20%20%20%20%20%20%20%20val%20%3D%20vp.solve()%0A%20%20%20%20%20%20%20%20%20%20%20%20residuals.append(np.sqrt(val)%20if%20ord%20%3D%3D%202%20else%20val)%0A%20%20%20%20%20%20%20%20return%20vp%2C%20residuals%0A%0A%20%20%20%20return%20(pdhg_verification%2C)%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20pdhg_verification)%3A%0A%20%20%20%20_%2C%20all_residuals%20%3D%20pdhg_verification(%0A%20%20%20%20%20%20%20%20K%2C%20'mip'%2C%20solver%3D'gurobi'%2C%0A%20%20%20%20)%0A%20%20%20%20print(all_residuals)%0A%20%20%20%20return%20(all_residuals%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20same%20MIP%20verification%20procedure%20is%20then%20applied%20to%20the%20momentum%20PDHG%20recurrence%2C%20using%20the%20residual%20expression%20induced%20by%20the%20extrapolated%20primal%20iterate.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20pdhg_verification)%3A%0A%20%20%20%20%23%20Solve%20verification%20problem%20for%20momentum%20PDHG%0A%20%20%20%20_%2C%20all_residuals_momentum%20%3D%20pdhg_verification(%0A%20%20%20%20%20%20%20%20K%2C%20'mip'%2C%20momentum%3DTrue%2C%20solver%3D'gurobi'%2C%0A%20%20%20%20)%0A%20%20%20%20print(all_residuals_momentum)%0A%20%20%20%20return%20(all_residuals_momentum%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Now%20we%20plot%20the%20verification%20results%20against%20the%20in-sample%20simulation%0A%20%20%20%20statistics.%20Every%20curve%20bounds%20the%20same%20scalar%2C%0A%20%20%20%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24%20of%20the%20scaled%20KKT%20residual%2C%20but%20they%20answer%20different%0A%20%20%20%20questions%3A%0A%0A%20%20%20%20-%20**sample%20worst-case**%20%E2%80%94%20a%20*lower*%20bound%20on%20the%20true%20worst%20case.%20The%20samples%0A%20%20%20%20%20%20are%20uniform%20over%20the%20same%20boxes%20the%20verifiers%20search%2C%20but%20uniform%20sampling%0A%20%20%20%20%20%20in%20%2422%24%20dimensions%20concentrates%20away%20from%20the%20vertices%20and%20faces%20where%20the%0A%20%20%20%20%20%20maximizer%20sits%2C%20so%20this%20curve%20is%20loose%20by%20construction.%0A%20%20%20%20-%20**MIP-VP**%20%E2%80%94%20the%20*exact*%20worst%20case%20over%20the%20boxes%2C%20for%20this%20instance.%0A%20%20%20%20%20%20It%20uses%20the%20infinity-norm%20objective%2C%20which%20is%20a%20MILP%20and%20solves%20in%20under%0A%20%20%20%20%20%20a%20second%3B%20its%202-norm%20counterpart%20is%20a%20nonconvex%20MIQP%20that%20does%20not%20finish%0A%20%20%20%20%20%20here%2C%20and%20switching%20it%20would%20cost%20the%20*exactness*%20that%20makes%20the%20MIP%0A%20%20%20%20%20%20curve%20worth%20plotting.%0A%0A%20%20%20%20So%20the%20expected%20ordering%20at%20every%20%24K%24%20is%0A%20%20%20%20%24%5Ctext%7Bsample%20worst-case%7D%20%5Cle%20%5Ctext%7BMIP-VP%7D%24.%0A%0A%20%20%20%20**There%20is%20no%20PEPit%20curve%20here**%2C%20unlike%20the%20NNLS%20tutorial.%20Two%20things%20would%0A%20%20%20%20have%20to%20be%20built%20first.%20PEPit's%20PDHG%20template%20measures%20the%20plain%20iterate%0A%20%20%20%20difference%20%24%5C%7Cz%5Ek-z%5E%7Bk-1%7D%5C%7C_2%5E2%20%2B%20%5C%7C(v%5Ek%2C%20w%5Ek)-(v%5E%7Bk-1%7D%2C%20w%5E%7Bk-1%7D)%5C%7C_2%5E2%24%2C%20whereas%20%60pdhg_step%60%0A%20%20%20%20measures%20the%20scaled%20KKT%20residual%2C%20which%20premultiplies%20those%20differences%20by%0A%20%20%20%20the%20PDHG%20metric%20matrix%20(%241%2F%5Ceta%24%20on%20the%20diagonal%2C%20%24A_s%5ET%24%20and%20%24A_d%5ET%24%20off%0A%20%20%20%20it)%3B%20with%20%24%5Ceta%20%3D%200.5%2FL%24%20the%20%241%2F%5Ceta%24%20factor%20alone%20is%20%242L%24%2C%20so%20the%20two%0A%20%20%20%20numbers%20are%20not%20comparable.%20More%20fundamentally%2C%20PEPit%20needs%20a%20radius%20%24R%24%0A%20%20%20%20covering%20the%20whole%20initial-condition%20box%2C%20and%20the%20objective%20%24%5Cmu%5ET%20f%24%20here%0A%20%20%20%20is%20*linear*%3A%20the%20primal-dual%20solution%20map%20of%20an%20LP%20is%20piecewise%20constant%20and%0A%20%20%20%20can%20jump%20across%20the%20parameter%20box%2C%20and%20under%20dual%20degeneracy%20the%20saddle%20point%0A%20%20%20%20need%20not%20even%20be%20unique%2C%20so%20there%20is%20no%20Lipschitz%20argument%20to%20turn%20the%20box%0A%20%20%20%20into%20a%20certified%20%24R%24.%20Plotting%20a%20bound%20built%20from%20a%20radius%20measured%20on%20the%0A%20%20%20%20samples%20would%20not%20be%20a%20guarantee%20for%20the%20set%20the%20verifiers%20search.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20K%2C%0A%20%20%20%20all_residuals%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg%2C%0A%20%20%20%20simulation_residuals_pdhg%2C%0A)%3A%0A%20%20%20%20plt.figure()%0A%20%20%20%20_ks%20%3D%20range(1%2C%20K%2B1)%0A%20%20%20%20plt.plot(_ks%2C%20all_residuals%2C%20label%3D'MIP-VP')%0A%20%20%20%20_avg_line%2C%20%3D%20plt.plot(_ks%2C%20simulation_residuals_pdhg%2C%20'--'%2C%20label%3D'sample%20average')%0A%20%20%20%20plt.fill_between(_ks%2C%20simulation_residual_quantiles_pdhg%5B2%5D%2C%20simulation_residual_quantiles_pdhg%5B0%5D%2C%20alpha%3D.18%2C%20label%3D'sample%2010%25-90%25%20band')%0A%20%20%20%20plt.plot(_ks%2C%20simulation_residual_quantiles_pdhg%5B3%5D%2C%20'%3A'%2C%20color%3D_avg_line.get_color()%2C%20label%3D'sample%20worst-case')%0A%20%20%20%20plt.yscale('log')%0A%20%20%20%20plt.xlabel(r'%24K%24')%0A%20%20%20%20plt.ylabel(r'Worst-case%20KKT%20residual%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24')%0A%20%20%20%20plt.legend()%0A%20%20%20%20plt.suptitle('network%20optimization%20example')%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20also%20plot%20the%20verification%20results%20for%20momentum%20PDHG.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20K%2C%0A%20%20%20%20all_residuals_momentum%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg_mom%2C%0A%20%20%20%20simulation_residuals_pdhg_mom%2C%0A)%3A%0A%20%20%20%20plt.figure()%0A%20%20%20%20_ks%20%3D%20range(1%2C%20K%2B1)%0A%20%20%20%20plt.plot(_ks%2C%20all_residuals_momentum%2C%20label%3D'MIP-VP')%0A%20%20%20%20_avg_line%2C%20%3D%20plt.plot(_ks%2C%20simulation_residuals_pdhg_mom%2C%20'--'%2C%20label%3D'sample%20average')%0A%20%20%20%20plt.fill_between(_ks%2C%20simulation_residual_quantiles_pdhg_mom%5B2%5D%2C%20simulation_residual_quantiles_pdhg_mom%5B0%5D%2C%20alpha%3D.18%2C%20label%3D'sample%2010%25-90%25%20band')%0A%20%20%20%20plt.plot(_ks%2C%20simulation_residual_quantiles_pdhg_mom%5B3%5D%2C%20'%3A'%2C%20color%3D_avg_line.get_color()%2C%20label%3D'sample%20worst-case')%0A%20%20%20%20plt.yscale('log')%0A%20%20%20%20plt.xlabel(r'%24K%24')%0A%20%20%20%20plt.ylabel(r'Worst-case%20KKT%20residual%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24')%0A%20%20%20%20plt.legend()%0A%20%20%20%20plt.suptitle('network%20optimization%20momentum%20PDHG%20example')%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Finally%2C%20we%20overlay%20PDHG%20and%20momentum%20PDHG%20to%20compare%20the%20two%20methods%0A%20%20%20%20directly.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20K%2C%0A%20%20%20%20all_residuals%2C%0A%20%20%20%20all_residuals_momentum%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg%2C%0A%20%20%20%20simulation_residual_quantiles_pdhg_mom%2C%0A%20%20%20%20simulation_residuals_pdhg%2C%0A%20%20%20%20simulation_residuals_pdhg_mom%2C%0A)%3A%0A%20%20%20%20from%20matplotlib.lines%20import%20Line2D%0A%0A%20%20%20%20plt.figure()%0A%20%20%20%20_ks%20%3D%20range(1%2C%20K%2B1)%0A%0A%20%20%20%20_methods%20%3D%20%5B%0A%20%20%20%20%20%20%20%20('PDHG'%2C%20'C0'%2C%20all_residuals%2C%0A%20%20%20%20%20%20%20%20%20simulation_residuals_pdhg%2C%20simulation_residual_quantiles_pdhg)%2C%0A%20%20%20%20%20%20%20%20('momentum%20PDHG'%2C%20'C1'%2C%20all_residuals_momentum%2C%0A%20%20%20%20%20%20%20%20%20simulation_residuals_pdhg_mom%2C%20simulation_residual_quantiles_pdhg_mom)%2C%0A%20%20%20%20%5D%0A%20%20%20%20for%20_%2C%20_color%2C%20_mip%2C%20_avg%2C%20_quant%20in%20_methods%3A%0A%20%20%20%20%20%20%20%20plt.plot(_ks%2C%20_mip%2C%20'--'%2C%20color%3D_color)%0A%20%20%20%20%20%20%20%20plt.plot(_ks%2C%20_avg%2C%20'%3A'%2C%20color%3D_color)%0A%20%20%20%20%20%20%20%20plt.fill_between(_ks%2C%20_quant%5B2%5D%2C%20_quant%5B0%5D%2C%20color%3D_color%2C%20alpha%3D.18)%0A%0A%20%20%20%20_method_handles%20%3D%20%5B%0A%20%20%20%20%20%20%20%20Line2D(%5B%5D%2C%20%5B%5D%2C%20color%3D_color%2C%20label%3D_name)%0A%20%20%20%20%20%20%20%20for%20_name%2C%20_color%2C%20*_%20in%20_methods%0A%20%20%20%20%5D%0A%20%20%20%20_style_handles%20%3D%20%5B%0A%20%20%20%20%20%20%20%20Line2D(%5B%5D%2C%20%5B%5D%2C%20color%3D'gray'%2C%20linestyle%3D'--'%2C%20label%3D'MIP-VP')%2C%0A%20%20%20%20%20%20%20%20Line2D(%5B%5D%2C%20%5B%5D%2C%20color%3D'gray'%2C%20linestyle%3D'%3A'%2C%20label%3D'sample%20average')%2C%0A%20%20%20%20%5D%0A%0A%20%20%20%20plt.yscale('log')%0A%20%20%20%20plt.xlabel(r'%24K%24')%0A%20%20%20%20plt.ylabel(r'Worst-case%20KKT%20residual%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24')%0A%20%20%20%20_leg%20%3D%20plt.legend(handles%3D_method_handles%2C%20loc%3D'upper%20right')%0A%20%20%20%20plt.gca().add_artist(_leg)%0A%20%20%20%20plt.legend(handles%3D_style_handles%2C%20loc%3D'lower%20left')%0A%20%20%20%20plt.suptitle('network%20optimization%3A%20PDHG%20vs.%20momentum%20PDHG')%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
5d5835944499f8dbbb235984e8cafdc8