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%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20scipy.sparse%20import%20csr_matrix%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.portfolio%20import%20(%0A%20%20%20%20%20%20%20%20admm_step%2C%0A%20%20%20%20%20%20%20%20make_portfolio_data%2C%0A%20%20%20%20)%0A%0A%20%20%20%20np.set_printoptions(precision%3D5)%0A%20%20%20%20np.set_printoptions(suppress%3DTrue)%0A%20%20%20%20return%20admm_step%2C%20csr_matrix%2C%20make_portfolio_data%2C%20mo%2C%20np%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%20Portfolio%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%20an%20ADMM%20method%20for%20a%20mean-variance%20portfolio%20optimization%20problem.%20Given%20a%20covariance%20matrix%20%24%5CSigma%20%5Csucceq%200%24%2C%20expected%20return%20vector%20%24%5Cmu%24%2C%20and%20position%20limit%20%24u_%7B%5Cmax%7D%24%2C%20we%20solve%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(1%2F2)z%5ET%5CSigma%20z%20-%20%5Cmu%5ET%20z%20%5C%5C%0A%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%20%26%200%20%5Cle%20z_i%20%5Cle%20(u_%7B%5Cmax%7D)_i%2C%5Cquad%20i%3D1%2C%5Cldots%2Cn%2C%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%5Cmathbf%7B1%7D%5ET%20z%20%3D%201.%0A%20%20%20%20%5Cend%7Barray%7D%0A%0A%20%20%20%20The%20decision%20variable%20%24z%20%5Cin%20%5Cmathbf%7BR%7D%5En%24%20is%20the%20portfolio%20allocation%20(%60x%60%20in%20the%20code).%20The%20verification%20problem%20searches%20over%20the%20initial%20dual%20iterate%20of%20ADMM%20while%20keeping%20the%20problem%20data%20fixed.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(make_portfolio_data%2C%20np)%3A%0A%20%20%20%20n%20%3D%204%0A%20%20%20%20Sigma%2C%20mu%2C%20A_mat%2C%20l_val%2C%20u_val%20%3D%20make_portfolio_data(%0A%20%20%20%20%20%20%20%20n%3Dn%2C%20seed%3D0%2C%20position_limit%3D0.6%0A%20%20%20%20)%0A%0A%20%20%20%20x0_val%20%3D%20np.zeros(n)%0A%20%20%20%20v0_lb%20%3D%20np.zeros(n%20%2B%201)%0A%20%20%20%20v0_ub%20%3D%20np.ones(n%20%2B%201)%0A%20%20%20%20return%20A_mat%2C%20Sigma%2C%20l_val%2C%20mu%2C%20n%2C%20u_val%2C%20v0_lb%2C%20v0_ub%2C%20x0_val%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%20OSQP-style%20ADMM%0A%0A%20%20%20%20We%20write%20the%20constraints%20as%20%24l%20%5Cle%20Az%20%5Cle%20u%24%2C%20with%0A%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20A%20%3D%20%5Cbegin%7Bbmatrix%7D%20I%20%5C%5C%20%5Cmathbf%7B1%7D%5ET%20%5Cend%7Bbmatrix%7D%2C%5Cquad%0A%20%20%20%20%20%20%20%20l%20%3D%20%5Cbegin%7Bbmatrix%7D%200%20%5C%5C%201%20%5Cend%7Bbmatrix%7D%2C%5Cquad%0A%20%20%20%20%20%20%20%20u%20%3D%20%5Cbegin%7Bbmatrix%7D%20u_%7B%5Cmax%7D%20%5C%5C1%20%5Cend%7Bbmatrix%7D.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20The%20ADMM%20recurrence%20is%0A%0A%20%20%20%20%5Cbegin%7Barray%7D%7Brcl%7D%0A%20%20%20%20%20%20%20%20w%5E%7Bk%2B1%7D%20%26%3D%26%20%5CPi_%7B%5Bl%2Cu%5D%7D(v%5Ek)%2C%20%5C%5C%0A%20%20%20%20%20%20%20%20z%5E%7Bk%2B1%7D%20%26%3D%26%20(%5CSigma%20%2B%20%5Csigma%20I%20%2B%20%5Crho%20A%5ETA)%5E%7B-1%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cleft(%5Csigma%20z%5Ek%20%2B%20%5Cmu%20%2B%20%5Crho%20A%5ET(2w%5E%7Bk%2B1%7D-v%5Ek)%5Cright)%2C%20%5C%5C%0A%20%20%20%20%20%20%20%20v%5E%7Bk%2B1%7D%20%26%3D%26%20v%5Ek%20%2B%20Az%5E%7Bk%2B1%7D%20-%20w%5E%7Bk%2B1%7D%2C%0A%20%20%20%20%5Cend%7Barray%7D%0A%0A%20%20%20%20which%20is%20a%20fixed-point%20iteration%20in%20the%20pair%20%24(z%5Ek%2C%20v%5Ek)%24.%0A%0A%20%20%20%20We%20measure%20performance%20by%20the%20infinity%20norm%20of%20the%20combined%20fixed-point%20residual%20%24r%5Ek%20%3D%20(z%5E%7Bk%2B1%7D-z%5Ek%2C%5C%3B%20v%5E%7Bk%2B1%7D-v%5Ek)%24.%0A%20%20%20%20As%20in%20%5BExact%20Verification%20of%20First-Order%20Methods%20via%20Mixed-Integer%20Linear%20Programming%5D(https%3A%2F%2Farxiv.org%2Fabs%2F2412.11330)%2C%20the%20infinity%20norm%20keeps%20the%20verification%20problem%20a%20mixed-integer%20*linear*%20program.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A_mat%2C%20Sigma%2C%20csr_matrix%2C%20n%2C%20np)%3A%0A%20%20%20%20sigma%20%3D%201e-4%0A%20%20%20%20rho%20%3D%201.0%0A%20%20%20%20lhs_mat%20%3D%20csr_matrix(Sigma%20%2B%20sigma%20*%20np.eye(n)%20%2B%20rho%20*%20A_mat.T%20%40%20A_mat)%0A%20%20%20%20return%20lhs_mat%2C%20rho%2C%20sigma%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%0A%20%20%20%20*same*%20%60admm_step%60%20recurrence%20and%20residual%3B%20only%20the%0A%20%20%20%20%60Verifier%60%20backend%20and%20whether%20%24v%5E0%24%20is%20a%20sampled%20instance%20or%20a%20bounded%0A%20%20%20%20search%20variable%20change.%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%20compare%20simulator%20statistics%20and%20exact%20MIP%20verification%20for%20the%20portfolio%20ADMM%20recurrence%2C%20up%20to%20%24K%24%20iterations.%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%2045%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%20ADMM%20from%20randomly%20sampled%20initial%20dual%20iterates%20%24v%5E0%20%5Cin%20%5B0%2C1%5D%5E%7Bn%2B1%7D%24.%20The%20samples%20are%20drawn%20once%20below%20and%20reused%20by%20every%20simulation%20cell.%20Running%20%60_vp.solve()%60%20returns%20a%20residual%20history%20for%20each%20sampled%20initialization.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(n%2C%20np%2C%20v0_lb%2C%20v0_ub)%3A%0A%20%20%20%20n_samples%20%3D%2010000%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(0)%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%20%2B%201))%0A%20%20%20%20return%20(v0_samples%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%20simulation%20is%20run%20through%20the%20following%20function.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(A_mat%2C%20admm_step%2C%20l_val%2C%20lhs_mat%2C%20mu%2C%20n%2C%20np%2C%20rho%2C%20sigma%2C%20u_val%2C%20x0_val)%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%20admm_simulation(v0_samples%2C%20K%2C%20ord%3Dnp.inf)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Simulate%20ADMM%20on%20sampled%20dual%20iterates.%0A%0A%20%20%20%20%20%20%20%20Builds%20a%20simulator-mode%20%3Aclass%3A%60Verifier%60%2C%20registers%20the%20initial%20dual%0A%20%20%20%20%20%20%20%20iterate%20%60%60v0%60%60%20as%20a%20sampled%20parameter%20(fixing%20%24x%5E0%20%3D%200%24)%2C%20rolls%20out%20the%0A%20%20%20%20%20%20%20%20recurrence%20with%20%60%60admm_step%60%60%2C%20and%20simulates%20via%20%60%60vp.solve()%60%60.%0A%20%20%20%20%20%20%20%20%60%60v0_samples%60%60%20has%20shape%20%60%60(n_samples%2C%20n%2B1)%60%60%20(a%20single-row%20array%0A%20%20%20%20%20%20%20%20replays%20one%20instance)%2C%20and%20the%20returned%20%60%60residuals%60%60%20has%20shape%0A%20%20%20%20%20%20%20%20%60%60(n_samples%2C%20K)%60%60.%20Summary%20statistics%20(%60%60mean%60%60%2C%20%60%60min%60%60%2C%20%60%60max%60%60%2C%20...)%0A%20%20%20%20%20%20%20%20are%20available%20on%20the%20returned%20instance%20%60%60vp%60%60%20via%20%60%60vp%5B...%5D%60%60.%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%22simulator%22%2C%20obbt_solver%3DNone)%0A%20%20%20%20%20%20%20%20x%20%3D%20x0_val%0A%20%20%20%20%20%20%20%20v%20%3D%20vp.parameter(n%20%2B%201%2C%20samples%3Dv0_samples)%0A%0A%20%20%20%20%20%20%20%20lhs_mat_dense%20%3D%20lhs_mat.toarray()%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(K)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20x%2C%20v%2C%20residual%20%3D%20admm_step(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vp%2C%20A_mat%2C%20l_val%2C%20u_val%2C%20mu%2C%20rho%2C%20sigma%2C%20x%2C%20v%2C%20lhs_mat_dense%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%20admm_simulation%2C%20ft%2C%20maximize_residual%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20admm_simulation%2C%20np%2C%20v0_samples)%3A%0A%20%20%20%20_vp%2C%20_residuals%20%3D%20admm_simulation(v0_samples%2C%20K%2C%20ord%3Dnp.inf)%0A%0A%20%20%20%20print(%0A%20%20%20%20%20%20%20%20f%22Summary%20statistics%20(at%20K%3D%7BK%7D)%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_admm%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_admm%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_admm%2C%20simulation_residuals_admm%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%20We%20now%20obtain%20worst-case%20guarantees%20by%20solving%20the%20verification%20problem%0A%20%20%20%20with%20a%20MIP%20formulation%2C%20which%20gives%20the%20exact%20worst%20case.%20The%20following%0A%20%20%20%20function%20rolls%20out%20the%20same%20%60admm_step%60%20recurrence%20over%20the%20horizon%20%24K%24%0A%20%20%20%20and%20maximizes%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24%20over%20the%20bounded%20initial%20dual%20iterate%20%24v%5E0%24%0A%20%20%20%20at%20each%20iteration.%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_mat%2C%0A%20%20%20%20admm_step%2C%0A%20%20%20%20ft%2C%0A%20%20%20%20l_val%2C%0A%20%20%20%20lhs_mat%2C%0A%20%20%20%20maximize_residual%2C%0A%20%20%20%20mu%2C%0A%20%20%20%20n%2C%0A%20%20%20%20np%2C%0A%20%20%20%20rho%2C%0A%20%20%20%20sigma%2C%0A%20%20%20%20u_val%2C%0A%20%20%20%20v0_lb%2C%0A%20%20%20%20v0_ub%2C%0A%20%20%20%20x0_val%2C%0A)%3A%0A%20%20%20%20def%20admm_verification(K%2C%20method%2C%20ord%3Dnp.inf%2C%20**verifier_kwargs)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Solve%20the%20portfolio%20ADMM%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%20initial%20dual%0A%20%20%20%20%20%20%20%20iterate%20box%20%60%60%5Bv0_lb%2C%20v0_ub%5D%60%60%20(fixing%20%24x%5E0%20%3D%200%24)%2C%20rolls%20out%0A%20%20%20%20%20%20%20%20%60%60admm_step%60%60%20over%20the%20horizon%20%60%60K%60%60%2C%20and%20returns%20%60%60(vp%2C%20residuals)%60%60%0A%20%20%20%20%20%20%20%20with%20one%20worst-case%20residual%20per%20iteration.%20Extra%20%60%60verifier_kwargs%60%60%0A%20%20%20%20%20%20%20%20(%60%60solver%60%60%2C%20%60%60obbt_solver%60%60%2C%20%60%60params%60%60%2C%20...)%20are%20forwarded%20to%20the%0A%20%20%20%20%20%20%20%20%60%60Verifier%60%60%20constructor.%0A%0A%20%20%20%20%20%20%20%20%60%60ord%60%60%20defaults%20to%20%60%60inf%60%60%2C%20which%20keeps%20the%20MIP%20a%20MILP.%20A%202-norm%0A%20%20%20%20%20%20%20%20objective%20is%20squared%2C%20so%20its%20value%20is%20square-rooted%20on%20return.%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%20%3D%20vp.iterate_trajectory(K%20%2B%201%2C%20collapse_expr%3D%22auto%22)%0A%20%20%20%20%20%20%20%20v%20%3D%20vp.iterate_trajectory(K%20%2B%201%2C%20collapse_expr%3D%22auto%22)%0A%20%20%20%20%20%20%20%20x%5B0%5D%20%3D%20vp.iterate(n%2C%20lb%3Dx0_val%2C%20ub%3Dx0_val)%0A%20%20%20%20%20%20%20%20v%5B0%5D%20%3D%20vp.iterate(n%20%2B%201%2C%20lb%3Dv0_lb%2C%20ub%3Dv0_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%20x%2C%20v%2C%20residual%20%3D%20admm_step(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vp%2C%20A_mat%2C%20l_val%2C%20u_val%2C%20mu%2C%20rho%2C%20sigma%2C%20x%2C%20v%2C%20lhs_mat%2C%20k%3Dk%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(admm_verification%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%20MIP-VP%0A%0A%20%20%20%20We%20solve%20the%20exact%20MIP%20verification%20problem.%20The%20MIP%20maximizes%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24%20over%20the%20bounded%20initial%20dual%20iterate%20%24v%5E0%24%20for%20each%20horizon.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(K%2C%20admm_verification%2C%20np)%3A%0A%20%20%20%20_%2C%20all_residuals%20%3D%20admm_verification(%0A%20%20%20%20%20%20%20%20K%2C%20%22mip%22%2C%20ord%3Dnp.inf%2C%20solver%3D%22gurobi%22%2C%20obbt_solver%3D%22highs%22%2C%0A%20%20%20%20)%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%20%23%23%20Numerical%20Result%0A%0A%20%20%20%20Now%20we%20plot%20the%20verification%20results%20against%20the%20in-sample%20simulation%0A%20%20%20%20statistics%2C%20including%20the%20sample%20worst-case%20instance.%20Every%20curve%20reports%0A%20%20%20%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24%2C%20but%20they%20answer%20different%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%2C%20from%20%2410%5E4%24%0A%20%20%20%20%20%20draws%20uniform%20over%20the%20same%20box%20%24v%5E0%20%5Cin%20%5B0%2C1%5D%5E%7Bn%2B1%7D%24%20the%20verifiers%20search.%0A%20%20%20%20-%20**MIP-VP**%20%E2%80%94%20the%20*exact*%20worst%20case%20over%20that%20box%2C%20for%20this%20instance.%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.**%20Earlier%20versions%20of%20this%20notebook%20plotted%0A%20%20%20%20one%2C%20but%20it%20was%20not%20a%20bound%20on%20this%20algorithm%3A%20PEPit's%20%60admm_residuals%60%0A%20%20%20%20template%20is%20textbook%20Douglas%E2%80%93Rachford%20with%20unit%20proximal%20steps%2C%20in%20which%0A%20%20%20%20%24%5Csigma%24%2C%20%24%5Crho%24%20and%20%24A%24%20do%20not%20appear%20at%20all%2C%20whereas%20the%20recurrence%20above%0A%20%20%20%20is%20OSQP-form%20ADMM%20with%20%24%5Csigma%20%3D%2010%5E%7B-4%7D%24%2C%20%24%5Crho%20%3D%201%24%20and%0A%20%20%20%20%24A%20%3D%20%5BI%3B%5C%20%5Cmathbf%7B1%7D%5ET%5D%24%20%E2%80%94%20a%20different%20operator%20with%20a%20different%20contraction%0A%20%20%20%20factor.%20Its%20radius%20was%20additionally%20calibrated%20so%20that%20the%20PEPit%20value%0A%20%20%20%20matched%20the%20MIP%20value%20at%20%24K%3D1%24%2C%20which%20is%20why%20the%20curve%20used%20to%20fall%20*below*%0A%20%20%20%20the%20exact%20MIP%20worst%20case%20at%20later%20%24K%24.%20Restoring%20it%20would%20require%20a%20PEP%0A%20%20%20%20template%20for%20OSQP-ADMM%20with%20%24A%20%5Cne%20I%24%3B%20the%20%60_osqp_admm_residual%60%20template%0A%20%20%20%20used%20by%20the%20optimal-control%20tutorial%20models%20%24%5Csigma%24%20and%20%24%5Crho%24%20correctly%20but%0A%20%20%20%20assumes%20%24A%20%3D%20I%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%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_admm%2C%0A%20%20%20%20simulation_residuals_admm%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%20%20%20%20plt.plot(_ks%2C%20all_residuals%2C%20label%3D%22ADMM%20(MIP%20worst-case)%22)%0A%20%20%20%20_avg_line%2C%20%3D%20plt.plot(_ks%2C%20simulation_residuals_admm%2C%20%22--%22%2C%20label%3D%22ADMM%20(in-sample%20avg)%22)%0A%20%20%20%20plt.fill_between(%0A%20%20%20%20%20%20%20%20_ks%2C%0A%20%20%20%20%20%20%20%20simulation_residual_quantiles_admm%5B2%5D%2C%0A%20%20%20%20%20%20%20%20simulation_residual_quantiles_admm%5B0%5D%2C%0A%20%20%20%20%20%20%20%20alpha%3D.18%2C%0A%20%20%20%20%20%20%20%20label%3D%22ADMM%20sample%2010%25-90%25%20band%22%2C%0A%20%20%20%20)%0A%20%20%20%20plt.plot(_ks%2C%20simulation_residual_quantiles_admm%5B3%5D%2C%20%22%3A%22%2C%20color%3D_avg_line.get_color()%2C%20label%3D%22ADMM%20sample%20worst-case%22)%0A%20%20%20%20plt.yscale(%22log%22)%0A%20%20%20%20plt.ylabel(r%22Worst-case%20fixed-point%20residual%20%24%5C%7Cr%5Ek%5C%7C_%5Cinfty%24%22)%0A%20%20%20%20plt.xlabel(r%22%24K%24%22)%0A%20%20%20%20plt.suptitle(%22portfolio%20optimization%20ADMM%20example%22)%0A%20%20%20%20plt.legend()%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
c95b0f4f2a456d1cfad9e2482371aa04