04 mprgp vs active set

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%3D%3D0.23.13%22%2C%0A%23%20%20%20%20%20%22numpy%3E%3D2.0.0%22%2C%0A%23%20%20%20%20%20%22matplotlib%22%2C%0A%23%20%20%20%20%20%22cvx-linalg%3E%3D0.9.6%22%2C%0A%23%20%20%20%20%20%22nncg%22%2C%0A%23%20%5D%0A%23%0A%23%20%5Btool.uv.sources%5D%0A%23%20nncg%20%3D%20%7B%20path%20%3D%20%22..%2F..%2F..%22%2C%20editable%20%3D%20true%20%7D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Active-set%20vs%20MPRGP%0A%0A%20%20%20%20%60nncg%60%20ships%20**two**%20solvers%20for%20the%20same%20strictly%20convex%20non-negative%0A%20%20%20%20quadratic%20program%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmin_%7Bx%20%5Cge%200%7D%5C%20%5Ctfrac12%5C%2C%20x%5E%5Ctop%20A%20x%20-%20b%5E%5Ctop%20x%2C%0A%20%20%20%20%5Cqquad%20A%20%3D%20A%5E%5Ctop%20%5Csucc%200%20.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20-%20**%60solve_nnqp%60**%20%E2%80%94%20the%20primal-dual%20**active-set**%20loop%20(block%20principal%0A%20%20%20%20%20%20pivoting%20with%20a%20Bland%20fallback).%20It%20*guesses%20the%20optimal%20free%20set*%2C%20solves%0A%20%20%20%20%20%20an%20unconstrained%20reduced%20system%20%24A_%7BFF%7Dx_F%3Db_F%24%20on%20it%20by%20CG%2C%20and%20corrects%0A%20%20%20%20%20%20the%20guess.%20See%20the%20%5Bactive-set%20notebook%5D(01_active_set_methods.html).%0A%20%20%20%20-%20**%60solve_nnqp_mprgp%60**%20%E2%80%94%20**MPRGP**%20(Dost%C3%A1l%20%26%20Sch%C3%B6berl)%2C%20a%20matrix-free%0A%20%20%20%20%20%20*projection*%20method%20that%20interleaves%20conjugate-gradient%2C%20**expansion**%20and%0A%20%20%20%20%20%20**proportioning**%20steps%20under%20a%20proportioning%20test%2C%20never%20solving%20a%20face%0A%20%20%20%20%20%20exactly.%0A%0A%20%20%20%20They%20target%20the%20same%20minimiser%20with%20very%20different%20machinery.%20This%20notebook%0A%20%20%20%20puts%20them%20head%20to%20head%3A%20do%20they%20agree%2C%20how%20do%20they%20*scale*%2C%20and%20**when%20is%0A%20%20%20%20each%20faster**.%20The%20short%20version%20%E2%80%94%20measured%20below%20%E2%80%94%20is%20that%20on%20these%20dense%0A%20%20%20%20SPD%20problems%20the%20active-set%20loop%20is%20the%20stronger%20default%2C%20and%20MPRGP%20is%20the%0A%20%20%20%20complementary%20tool%20for%20the%20regimes%20active-set%20methods%20find%20hard.%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%20import%20time%0A%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20cvx.linalg%20import%20DenseOperator%2C%20power_iteration%0A%0A%20%20%20%20from%20nncg%20import%20kkt_violation%2C%20solve_nnqp%2C%20solve_nnqp_mprgp%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20DenseOperator%2C%0A%20%20%20%20%20%20%20%20kkt_violation%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20power_iteration%2C%0A%20%20%20%20%20%20%20%20solve_nnqp%2C%0A%20%20%20%20%20%20%20%20solve_nnqp_mprgp%2C%0A%20%20%20%20%20%20%20%20time%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%201.%20The%20two%20algorithms%20in%20one%20paragraph%20each%0A%0A%20%20%20%20**Active%20set%20%2F%20block%20principal%20pivoting.**%20Maintain%20a%20candidate%20free%20set%0A%20%20%20%20%24F%24.%20Solve%20the%20reduced%20SPD%20system%20%24A_%7BFF%7Dx_F%3Db_F%24%20(matrix-free%20CG)%2C%20set%0A%20%20%20%20%24x_%7BF%5Ec%7D%3D0%24%2C%20and%20read%20the%20reduced%20gradient%20%24s%3DAx-b%24.%20*Primal%20violators*%0A%20%20%20%20(free%20but%20negative)%20are%20dropped%20to%20the%20bound%3B%20*dual%20violators*%20(bound%20but%0A%20%20%20%20%24s_i%3C0%24)%20are%20added%20to%20%24F%24.%20A%20whole%20block%20is%20swapped%20per%20step%2C%20so%20the%20optimal%0A%20%20%20%20support%20is%20usually%20found%20in%20a%20**handful%20of%20outer%20steps**%2C%20each%20an%20exact-ish%0A%20%20%20%20inner%20solve.%20A%20patience%20counter%20plus%20a%20least-index%20Bland%20pivot%20guarantees%0A%20%20%20%20finite%20termination%20with%20no%20non-degeneracy%20assumption.%0A%0A%20%20%20%20**MPRGP.**%20Stay%20feasible%20(%24x%5Cge%200%24)%20throughout.%20Split%20the%20gradient%20into%20the%0A%20%20%20%20*free*%20gradient%20%24%5Cvarphi%24%20(on%20%24%5C%7Bx_i%3E0%5C%7D%24)%20and%20the%20*chopped*%20gradient%0A%20%20%20%20%24%5Cbeta%24%20(the%20releasing%20part%20on%20%24%5C%7Bx_i%3D0%5C%7D%24).%20The%20**proportioning%20test**%0A%20%20%20%20%24%5ClVert%5Cbeta%5CrVert%5E2%20%5Cle%20%5CGamma%5E2%5C%2C%5Ctilde%5Cvarphi%5E%5Ctop%5Cvarphi%24%20decides%20the%0A%20%20%20%20move%3A%0A%0A%20%20%20%20-%20proportional%20%E2%86%92%20a%20**CG%20step**%20minimising%20within%20the%20current%20face%2C%20or%2C%20if%20it%0A%20%20%20%20%20%20would%20leave%20the%20feasible%20box%2C%20an%20**expansion%20step**%20(walk%20to%20the%20bound%20%2B%0A%20%20%20%20%20%20one%20fixed-step%20projected%20gradient%2C%20*adding*%20constraints)%3B%0A%20%20%20%20-%20disproportional%20%E2%86%92%20a%20**proportioning%20step**%20along%20%24%5Cbeta%24%2C%20*releasing*%0A%20%20%20%20%20%20constraints.%0A%0A%20%20%20%20The%20fixed%20step%20%24%5Cbar%5Calpha%20%5Cin%20(0%2C%202%2F%5ClVert%20A%5CrVert%5D%24%20is%20the%20only%20tuning%3B%20it%0A%20%20%20%20is%20estimated%20matrix-free%20by%20power%20iteration.%20MPRGP%20identifies%20the%20active%20set%0A%20%20%20%20in%20finitely%20many%20steps%20and%20then%20*is*%20CG%20on%20the%20optimal%20face%20%E2%80%94%20so%20it%0A%20%20%20%20terminates%20finitely%20too%2C%20with%20an%20%24R%24-linear%20rate%20bound%20along%20the%20way.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20%23%20Planted-optimum%20generator%20(same%20construction%20as%20tests%2Fproblems.make_problem)%3A%0A%20%20%20%20%23%20a%20known%20minimiser%20x*%20with%20a%20chosen%20support%2C%20so%20we%20can%20measure%20recovery%20error.%0A%20%20%20%20def%20make_problem(n%2C%20kappa%2C%20support_frac%2C%20seed)%3A%0A%20%20%20%20%20%20%20%20rng%20%3D%20np.random.default_rng(seed)%0A%20%20%20%20%20%20%20%20eig%20%3D%20np.geomspace(1.0%2C%20kappa%2C%20n)%0A%20%20%20%20%20%20%20%20q%2C%20_%20%3D%20np.linalg.qr(rng.standard_normal((n%2C%20n)))%0A%20%20%20%20%20%20%20%20mat%20%3D%200.5%20*%20((q%20*%20eig)%20%40%20q.T%20%2B%20((q%20*%20eig)%20%40%20q.T).T)%0A%20%20%20%20%20%20%20%20k%20%3D%20max(1%2C%20round(support_frac%20*%20n))%0A%20%20%20%20%20%20%20%20perm%20%3D%20rng.permutation(n)%0A%20%20%20%20%20%20%20%20x_star%20%3D%20np.zeros(n)%0A%20%20%20%20%20%20%20%20x_star%5Bperm%5B%3Ak%5D%5D%20%3D%20rng.uniform(0.5%2C%201.5%2C%20size%3Dk)%0A%20%20%20%20%20%20%20%20s_star%20%3D%20np.zeros(n)%0A%20%20%20%20%20%20%20%20s_star%5Bperm%5Bk%3A%5D%5D%20%3D%20rng.uniform(0.5%2C%201.5%2C%20size%3Dn%20-%20k)%0A%20%20%20%20%20%20%20%20return%20mat%2C%20mat%20%40%20x_star%20-%20s_star%2C%20x_star%0A%0A%20%20%20%20return%20(make_problem%2C)%0A%0A%0A%40app.cell%0Adef%20_(time)%3A%0A%20%20%20%20%23%20Best-of-%60reps%60%20wall-clock%20timing%3B%20returns%20(seconds%2C%20last_result).%20Best-of%0A%20%20%20%20%23%20rather%20than%20mean%20rejects%20scheduler%2FGC%20noise%2C%20the%20usual%20microbenchmark%20hygiene.%0A%20%20%20%20def%20bench(fn%2C%20reps%3D5)%3A%0A%20%20%20%20%20%20%20%20best%20%3D%20float(%22inf%22)%0A%20%20%20%20%20%20%20%20result%20%3D%20None%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(reps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_t%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20fn()%0A%20%20%20%20%20%20%20%20%20%20%20%20best%20%3D%20min(best%2C%20time.perf_counter()%20-%20_t)%0A%20%20%20%20%20%20%20%20return%20best%2C%20result%0A%0A%20%20%20%20return%20(bench%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%202.%20They%20find%20the%20same%20optimum%0A%0A%20%20%20%20First%2C%20a%20sanity%20check%20on%20a%20single%20problem%3A%20both%20solvers%20should%20land%20on%20the%0A%20%20%20%20same%20point%20and%20certify%20it%20with%20a%20near-zero%20KKT%20violation.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20DenseOperator%2C%0A%20%20%20%20kkt_violation%2C%0A%20%20%20%20make_problem%2C%0A%20%20%20%20np%2C%0A%20%20%20%20solve_nnqp%2C%0A%20%20%20%20solve_nnqp_mprgp%2C%0A)%3A%0A%20%20%20%20_a%2C%20_b%2C%20_x_star%20%3D%20make_problem(120%2C%201e4%2C%20support_frac%3D0.5%2C%20seed%3D0)%0A%20%20%20%20_op%20%3D%20DenseOperator(_a)%0A%0A%20%20%20%20demo_as%20%3D%20solve_nnqp(_op%2C%20_b)%0A%20%20%20%20%23%20tol%20tightened%3A%20MPRGP%20is%20first-order%2C%20so%20matching%20the%20active-set%20loop's%0A%20%20%20%20%23%20near-exact%20iterate%20at%20kappa%3D1e4%20needs%20a%20tighter%20projected-gradient%20tolerance.%0A%20%20%20%20demo_mp%20%3D%20solve_nnqp_mprgp(_op%2C%20_b%2C%20tol%3D1e-11)%0A%0A%20%20%20%20demo_agree%20%3D%20float(np.max(np.abs(demo_as.x%20-%20demo_mp.x)))%0A%20%20%20%20demo_kkt_as%20%3D%20kkt_violation(_op%2C%20_b%2C%20demo_as.x)%0A%20%20%20%20demo_kkt_mp%20%3D%20kkt_violation(_op%2C%20_b%2C%20demo_mp.x)%0A%20%20%20%20return%20demo_agree%2C%20demo_as%2C%20demo_kkt_as%2C%20demo_kkt_mp%2C%20demo_mp%0A%0A%0A%40app.cell%0Adef%20_(demo_agree%2C%20demo_as%2C%20demo_kkt_as%2C%20demo_kkt_mp%2C%20demo_mp%2C%20mo)%3A%0A%20%20%20%20_as_steps%20%3D%20f%22%7Bdemo_as.outer%7D%20outer%20%2F%20%7Bdemo_as.inner%7D%20inner%20CG%22%0A%20%20%20%20_mp_steps%20%3D%20(%0A%20%20%20%20%20%20%20%20f%22%7Bdemo_mp.iterations%7D%20(%7Bdemo_mp.cg_steps%7D%20cg%2C%20%22%0A%20%20%20%20%20%20%20%20f%22%7Bdemo_mp.expansion_steps%7D%20exp%2C%20%7Bdemo_mp.proportioning_steps%7D%20prop)%22%0A%20%20%20%20)%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20rf%22%22%22%0A%20%20%20%20%20%20%20%20%7C%20quantity%20%7C%20active%20set%20%7C%20MPRGP%20%7C%0A%20%20%20%20%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%20%20%20%20%7C%20converged%20%7C%20%7Bdemo_as.converged%7D%20%7C%20%7Bdemo_mp.converged%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20KKT%20violation%20%7C%20%7Bdemo_kkt_as%3A.2e%7D%20%7C%20%7Bdemo_kkt_mp%3A.2e%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20steps%20%7C%20%7B_as_steps%7D%20%7C%20%7B_mp_steps%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20Hessian%20products%20%7C%20%7Bdemo_as.inner%7D%20*(free-block)*%20%7C%20%7Bdemo_mp.hessian_products%7D%20*(full-size)*%20%7C%0A%0A%20%20%20%20%20%20%20%20**Agreement**%20%24%5ClVert%20x_%7B%7B%5Ctext%7B%7BAS%7D%7D%7D%7D%20-%20x_%7B%7B%5Ctext%7B%7BMPRGP%7D%7D%7D%7D%5CrVert_%5Cinfty%0A%20%20%20%20%20%20%20%20%3D%20%7Bdemo_agree%3A.2e%7D%24%20%E2%80%94%20the%20same%20minimiser.%0A%0A%20%20%20%20%20%20%20%20The%20step%20vocabularies%20differ%20completely%3A%20the%20active-set%20loop%20takes%20a%20few%0A%20%20%20%20%20%20%20%20**outer**%20steps%20(each%20an%20inner%20CG%20solve%20on%20the%20free%20block)%2C%20while%20MPRGP%20takes%0A%20%20%20%20%20%20%20%20many%20small%20feasible%20steps.%20Note%20the%20Hessian-product%20counts%20are%20*not*%0A%20%20%20%20%20%20%20%20directly%20comparable%20%E2%80%94%20the%20active-set%20loop's%20products%20act%20on%20the%20**reduced**%0A%20%20%20%20%20%20%20%20block%20%24A_%7B%7BFF%7D%7D%24%20(cheaper)%2C%20MPRGP's%20on%20the%20**full**%20operator.%20Wall-clock%20is%0A%20%20%20%20%20%20%20%20the%20fair%20yardstick%2C%20so%20that%20is%20what%20the%20scaling%20study%20below%20uses.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%203.%20Live%20comparison%0A%0A%20%20%20%20Turn%20the%20knobs.%20We%20build%20a%20planted%20problem%2C%20solve%20it%20with%20both%20methods%20at%0A%20%20%20%20**matched%20accuracy**%20(MPRGP's%20tolerance%20is%20tightened%20until%20its%20recovery%0A%20%20%20%20error%20is%20within%20%243%5Ctimes%24%20the%20active-set%20loop's)%2C%20and%20time%20each%20best-of-5.%0A%20%20%20%20MPRGP's%20%24%5Cbar%5Calpha%24%20is%20precomputed%20once%20by%20power%20iteration%20so%20the%20estimate%0A%20%20%20%20is%20not%20re-charged%20to%20every%20solve.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_slider%20%3D%20mo.ui.slider(50%2C%20600%2C%20value%3D200%2C%20step%3D50%2C%20label%3D%22dimension%20%24n%24%22)%0A%20%20%20%20kappa_slider%20%3D%20mo.ui.slider(1%2C%206%2C%20value%3D4%2C%20step%3D1%2C%20label%3D%22condition%20number%20%24%5C%5Clog_%7B10%7D%5C%5Ckappa%24%22)%0A%20%20%20%20supp_slider%20%3D%20mo.ui.slider(0.1%2C%200.9%2C%20value%3D0.5%2C%20step%3D0.05%2C%20label%3D%22support%20fraction%22)%0A%20%20%20%20seed_slider%20%3D%20mo.ui.slider(0%2C%2020%2C%20value%3D0%2C%20step%3D1%2C%20label%3D%22seed%22)%0A%20%20%20%20mo.vstack(%5Bn_slider%2C%20kappa_slider%2C%20supp_slider%2C%20seed_slider%5D)%0A%20%20%20%20return%20kappa_slider%2C%20n_slider%2C%20seed_slider%2C%20supp_slider%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20DenseOperator%2C%0A%20%20%20%20bench%2C%0A%20%20%20%20kappa_slider%2C%0A%20%20%20%20make_problem%2C%0A%20%20%20%20n_slider%2C%0A%20%20%20%20np%2C%0A%20%20%20%20power_iteration%2C%0A%20%20%20%20seed_slider%2C%0A%20%20%20%20solve_nnqp%2C%0A%20%20%20%20solve_nnqp_mprgp%2C%0A%20%20%20%20supp_slider%2C%0A)%3A%0A%20%20%20%20def%20matched_mprgp(op%2C%20b%2C%20x_star%2C%20target_err%2C%20alpha_bar)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Tighten%20MPRGP's%20tol%20until%20recovery%20error%20is%20within%203x%20the%20target.%22%22%22%0A%20%20%20%20%20%20%20%20tol%20%3D%201e-8%0A%20%20%20%20%20%20%20%20res%20%3D%20solve_nnqp_mprgp(op%2C%20b%2C%20tol%3Dtol%2C%20alpha_bar%3Dalpha_bar)%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(8)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.max(np.abs(res.x%20-%20x_star))%20%3C%3D%20max(target_err%2C%201e-9)%20*%203%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20tol%20*%3D%200.1%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20solve_nnqp_mprgp(op%2C%20b%2C%20tol%3Dtol%2C%20alpha_bar%3Dalpha_bar)%0A%20%20%20%20%20%20%20%20return%20tol%2C%20res%0A%0A%20%20%20%20live_n%20%3D%20n_slider.value%0A%20%20%20%20live_kappa%20%3D%2010.0**kappa_slider.value%0A%20%20%20%20_a%2C%20_b%2C%20live_x_star%20%3D%20make_problem(live_n%2C%20live_kappa%2C%20supp_slider.value%2C%20seed_slider.value)%0A%20%20%20%20live_op%20%3D%20DenseOperator(_a)%0A%0A%20%20%20%20live_alpha_bar%20%3D%201.0%20%2F%20float(power_iteration(live_op%2C%20seed%3D0)%5B0%5D)%0A%0A%20%20%20%20live_t_as%2C%20live_as%20%3D%20bench(lambda%3A%20solve_nnqp(live_op%2C%20_b))%0A%20%20%20%20live_err_as%20%3D%20float(np.max(np.abs(live_as.x%20-%20live_x_star)))%0A%20%20%20%20live_tol%2C%20_%20%3D%20matched_mprgp(live_op%2C%20_b%2C%20live_x_star%2C%20live_err_as%2C%20live_alpha_bar)%0A%20%20%20%20live_t_mp%2C%20live_mp%20%3D%20bench(lambda%3A%20solve_nnqp_mprgp(live_op%2C%20_b%2C%20tol%3Dlive_tol%2C%20alpha_bar%3Dlive_alpha_bar))%0A%20%20%20%20live_err_mp%20%3D%20float(np.max(np.abs(live_mp.x%20-%20live_x_star)))%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20live_as%2C%0A%20%20%20%20%20%20%20%20live_err_as%2C%0A%20%20%20%20%20%20%20%20live_err_mp%2C%0A%20%20%20%20%20%20%20%20live_kappa%2C%0A%20%20%20%20%20%20%20%20live_mp%2C%0A%20%20%20%20%20%20%20%20live_n%2C%0A%20%20%20%20%20%20%20%20live_t_as%2C%0A%20%20%20%20%20%20%20%20live_t_mp%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20live_as%2C%0A%20%20%20%20live_err_as%2C%0A%20%20%20%20live_err_mp%2C%0A%20%20%20%20live_kappa%2C%0A%20%20%20%20live_mp%2C%0A%20%20%20%20live_n%2C%0A%20%20%20%20live_t_as%2C%0A%20%20%20%20live_t_mp%2C%0A%20%20%20%20mo%2C%0A)%3A%0A%20%20%20%20_speedup%20%3D%20live_t_as%20%2F%20live_t_mp%0A%20%20%20%20_winner%20%3D%20%22MPRGP%22%20if%20_speedup%20%3E%201%20else%20%22active%20set%22%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20rf%22%22%22%0A%20%20%20%20%20%20%20%20%7C%20metric%20%7C%20active%20set%20%7C%20MPRGP%20%7C%0A%20%20%20%20%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%20%20%20%20%7C%20dimension%20%24n%24%20%7C%20%7Blive_n%7D%20%7C%20%7Blive_n%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20condition%20number%20%24%5Ckappa%24%20%7C%20%7Blive_kappa%3A.0e%7D%20%7C%20%7Blive_kappa%3A.0e%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20wall-clock%20(best%20of%205)%20%7C%20**%7Blive_t_as%20*%201e3%3A.2f%7D%20ms**%20%7C%20**%7Blive_t_mp%20*%201e3%3A.2f%7D%20ms**%20%7C%0A%20%20%20%20%20%20%20%20%7C%20recovery%20error%20%24%5ClVert%20x-x%5E%5Cstar%5CrVert_%5Cinfty%24%20%7C%20%7Blive_err_as%3A.1e%7D%20%7C%20%7Blive_err_mp%3A.1e%7D%20%7C%0A%20%20%20%20%20%20%20%20%7C%20steps%20%7C%20%7Blive_as.outer%7D%20outer%20%2F%20%7Blive_as.inner%7D%20inner%20%7C%20%7Blive_mp.iterations%7D%20iters%20%7C%0A%0A%20%20%20%20%20%20%20%20At%20these%20settings%20the%20faster%20solver%20is%20**%7B_winner%7D**%0A%20%20%20%20%20%20%20%20(%24%7B_speedup%3A.2f%7D%5Ctimes%24%20active-set%20%2F%20MPRGP).%20Sweep%20%24%5Ckappa%24%20up%20with%20the%0A%20%20%20%20%20%20%20%20slider%20and%20watch%20MPRGP%20fall%20behind%3A%20its%20iteration%20count%20grows%20like%0A%20%20%20%20%20%20%20%20%24%5Csqrt%5Ckappa%24%20while%20the%20active-set%20loop%20keeps%20taking%20only%20a%20few%20outer%20steps.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%204.%20Scaling%20with%20the%20condition%20number%0A%0A%20%20%20%20The%20decisive%20axis%20is%20conditioning.%20We%20fix%20%24n%24%20and%20a%20seed%20and%20sweep%0A%20%20%20%20%24%5Ckappa%24%20from%20%2410%24%20to%20%2410%5E6%24%2C%20timing%20both%20solvers%20at%20matched%20accuracy.%20This%0A%20%20%20%20is%20the%20plot%20that%20answers%20%22*is%20MPRGP%20faster%3F*%22.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20DenseOperator%2C%0A%20%20%20%20bench%2C%0A%20%20%20%20make_problem%2C%0A%20%20%20%20np%2C%0A%20%20%20%20power_iteration%2C%0A%20%20%20%20solve_nnqp%2C%0A%20%20%20%20solve_nnqp_mprgp%2C%0A)%3A%0A%20%20%20%20sweep_kappa%20%3D%20np.array(%5B1e1%2C%201e2%2C%201e3%2C%201e4%2C%201e5%2C%201e6%5D)%0A%20%20%20%20sweep_n%20%3D%20250%0A%20%20%20%20sweep_seed%20%3D%201%0A%0A%20%20%20%20sweep_t_as%2C%20sweep_t_mp%20%3D%20%5B%5D%2C%20%5B%5D%0A%20%20%20%20sweep_prod_as%2C%20sweep_prod_mp%20%3D%20%5B%5D%2C%20%5B%5D%0A%20%20%20%20for%20_kappa%20in%20sweep_kappa%3A%0A%20%20%20%20%20%20%20%20_a%2C%20_b%2C%20_x_star%20%3D%20make_problem(sweep_n%2C%20float(_kappa)%2C%200.5%2C%20sweep_seed)%0A%20%20%20%20%20%20%20%20_op%20%3D%20DenseOperator(_a)%0A%20%20%20%20%20%20%20%20_alpha_bar%20%3D%201.0%20%2F%20float(power_iteration(_op%2C%20seed%3D0)%5B0%5D)%0A%0A%20%20%20%20%20%20%20%20_t_as%2C%20_r_as%20%3D%20bench(lambda%20op%3D_op%2C%20b%3D_b%3A%20solve_nnqp(op%2C%20b))%0A%20%20%20%20%20%20%20%20_err_as%20%3D%20np.max(np.abs(_r_as.x%20-%20_x_star))%0A%0A%20%20%20%20%20%20%20%20%23%20match%20accuracy%20by%20tightening%20MPRGP%20tol%0A%20%20%20%20%20%20%20%20_tol%20%3D%201e-8%0A%20%20%20%20%20%20%20%20_r_mp%20%3D%20solve_nnqp_mprgp(_op%2C%20_b%2C%20tol%3D_tol%2C%20alpha_bar%3D_alpha_bar)%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(8)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.max(np.abs(_r_mp.x%20-%20_x_star))%20%3C%3D%20max(_err_as%2C%201e-9)%20*%203%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20_tol%20*%3D%200.1%0A%20%20%20%20%20%20%20%20%20%20%20%20_r_mp%20%3D%20solve_nnqp_mprgp(_op%2C%20_b%2C%20tol%3D_tol%2C%20alpha_bar%3D_alpha_bar)%0A%20%20%20%20%20%20%20%20_t_mp%2C%20_r_mp%20%3D%20bench(lambda%20op%3D_op%2C%20b%3D_b%2C%20t%3D_tol%2C%20ab%3D_alpha_bar%3A%20solve_nnqp_mprgp(op%2C%20b%2C%20tol%3Dt%2C%20alpha_bar%3Dab))%0A%0A%20%20%20%20%20%20%20%20sweep_t_as.append(_t_as%20*%201e3)%0A%20%20%20%20%20%20%20%20sweep_t_mp.append(_t_mp%20*%201e3)%0A%20%20%20%20%20%20%20%20sweep_prod_as.append(_r_as.inner)%0A%20%20%20%20%20%20%20%20sweep_prod_mp.append(_r_mp.hessian_products)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20sweep_kappa%2C%0A%20%20%20%20%20%20%20%20sweep_n%2C%0A%20%20%20%20%20%20%20%20sweep_prod_as%2C%0A%20%20%20%20%20%20%20%20sweep_prod_mp%2C%0A%20%20%20%20%20%20%20%20sweep_t_as%2C%0A%20%20%20%20%20%20%20%20sweep_t_mp%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20plt%2C%0A%20%20%20%20sweep_kappa%2C%0A%20%20%20%20sweep_n%2C%0A%20%20%20%20sweep_prod_as%2C%0A%20%20%20%20sweep_prod_mp%2C%0A%20%20%20%20sweep_t_as%2C%0A%20%20%20%20sweep_t_mp%2C%0A)%3A%0A%20%20%20%20_fig%2C%20(_ax1%2C%20_ax2)%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(11%2C%204))%0A%0A%20%20%20%20_ax1.loglog(sweep_kappa%2C%20sweep_t_as%2C%20%22o-%22%2C%20label%3D%22active%20set%22%2C%20color%3D%22%2311D48E%22)%0A%20%20%20%20_ax1.loglog(sweep_kappa%2C%20sweep_t_mp%2C%20%22s-%22%2C%20label%3D%22MPRGP%22%2C%20color%3D%22%23555%22)%0A%20%20%20%20_ax1.set_xlabel(r%22condition%20number%20%24%5Ckappa%24%22)%0A%20%20%20%20_ax1.set_ylabel(%22wall-clock%20(ms%2C%20best%20of%205)%22)%0A%20%20%20%20_ax1.set_title(f%22Time%20vs%20conditioning%20(%24n%3D%7Bsweep_n%7D%24%2C%20matched%20accuracy)%22)%0A%20%20%20%20_ax1.legend()%0A%20%20%20%20_ax1.grid(True%2C%20which%3D%22both%22%2C%20alpha%3D0.3)%0A%0A%20%20%20%20_ax2.loglog(sweep_kappa%2C%20sweep_prod_as%2C%20%22o-%22%2C%20label%3D%22active%20set%20(reduced-block%20CG)%22%2C%20color%3D%22%2311D48E%22)%0A%20%20%20%20_ax2.loglog(sweep_kappa%2C%20sweep_prod_mp%2C%20%22s-%22%2C%20label%3D%22MPRGP%20(full-size)%22%2C%20color%3D%22%23555%22)%0A%20%20%20%20_ax2.set_xlabel(r%22condition%20number%20%24%5Ckappa%24%22)%0A%20%20%20%20_ax2.set_ylabel(%22Hessian%20products%22)%0A%20%20%20%20_ax2.set_title(%22Matrix-vector%20products%20vs%20conditioning%22)%0A%20%20%20%20_ax2.legend()%0A%20%20%20%20_ax2.grid(True%2C%20which%3D%22both%22%2C%20alpha%3D0.3)%0A%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20sweep_kappa%2C%20sweep_t_as%2C%20sweep_t_mp)%3A%0A%20%20%20%20_ratios%20%3D%20%5Btm%20%2F%20ta%20for%20ta%2C%20tm%20in%20zip(sweep_t_as%2C%20sweep_t_mp%2C%20strict%3DTrue)%5D%0A%20%20%20%20_lo%2C%20_hi%20%3D%20min(_ratios)%2C%20max(_ratios)%0A%20%20%20%20_kexp%20%3D%20round(np.log10(sweep_kappa%5B-1%5D))%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20rf%22%22%22%0A%20%20%20%20%20%20%20%20**Reading%20the%20plots.**%20On%20these%20dense%20SPD%20problems%20the%20active-set%20loop%20is%0A%20%20%20%20%20%20%20%20as%20fast%20or%20faster%20across%20the%20whole%20range%2C%20and%20its%20lead%20*grows*%20with%0A%20%20%20%20%20%20%20%20%24%5Ckappa%24%3A%20MPRGP%20runs%20from%20roughly%20on-par%20at%20low%20conditioning%20to%0A%20%20%20%20%20%20%20%20%24%7B_hi%3A.1f%7D%5Ctimes%24%20slower%20at%20%24%5Ckappa%3D10%5E%7B%7B%7B_kexp%7D%7D%7D%24%0A%20%20%20%20%20%20%20%20(MPRGP%2Factive-set%20time%20ratio%20spans%20%24%7B_lo%3A.2f%7D%24%E2%80%93%24%7B_hi%3A.2f%7D%24).%0A%0A%20%20%20%20%20%20%20%20Two%20forces%20drive%20this%3A%0A%0A%20%20%20%20%20%20%20%20-%20**Outer-step%20economy.**%20The%20active-set%20loop%20reaches%20the%20optimal%20support%20in%0A%20%20%20%20%20%20%20%20%20%20a%20few%20block%20pivots%3B%20each%20inner%20CG%20solve%20is%20on%20the%20*reduced*%20block%20and%20is%0A%20%20%20%20%20%20%20%20%20%20warm-started.%20MPRGP's%20step%20count%20grows%20like%20%24%5Csqrt%5Ckappa%24%20(the%20CG%20rate)%2C%0A%20%20%20%20%20%20%20%20%20%20and%20each%20step%20touches%20the%20*full*%20operator.%0A%20%20%20%20%20%20%20%20-%20**First-order%20accuracy.**%20MPRGP%20never%20solves%20a%20face%20exactly%2C%20so%20its%20iterate%0A%20%20%20%20%20%20%20%20%20%20error%20carries%20a%20factor%20of%20%24%5Ckappa%24%3B%20matching%20the%20active-set%20loop's%0A%20%20%20%20%20%20%20%20%20%20near-exact%20answer%20forces%20a%20tighter%20tolerance%20and%20thus%20*more*%20steps%0A%20%20%20%20%20%20%20%20%20%20precisely%20where%20it%20is%20already%20slower.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%205.%20MPRGP's%20move%20breakdown%0A%0A%20%20%20%20MPRGP's%20cost%20is%20the%20sum%20of%20three%20move%20types.%20Expansion%20and%20proportioning%0A%20%20%20%20steps%20are%20the%20ones%20that%20*change*%20the%20active%20set%3B%20long%20runs%20of%20CG%20steps%20are%0A%20%20%20%20plain%20conjugate%20gradients%20on%20a%20fixed%20face.%20Watch%20the%20CG%20steps%20dominate%20%E2%80%94%20and%0A%20%20%20%20grow%20with%20%24%5Ckappa%24%20%E2%80%94%20while%20the%20constraint-changing%20steps%20stay%20a%20small%2C%0A%20%20%20%20roughly%20constant%20overhead.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(DenseOperator%2C%20make_problem%2C%20np%2C%20power_iteration%2C%20solve_nnqp_mprgp)%3A%0A%20%20%20%20break_kappa%20%3D%20np.array(%5B1e1%2C%201e2%2C%201e3%2C%201e4%2C%201e5%2C%201e6%5D)%0A%20%20%20%20break_cg%2C%20break_exp%2C%20break_prop%20%3D%20%5B%5D%2C%20%5B%5D%2C%20%5B%5D%0A%20%20%20%20for%20_kappa%20in%20break_kappa%3A%0A%20%20%20%20%20%20%20%20_a%2C%20_b%2C%20_x_star%20%3D%20make_problem(250%2C%20float(_kappa)%2C%200.5%2C%201)%0A%20%20%20%20%20%20%20%20_op%20%3D%20DenseOperator(_a)%0A%20%20%20%20%20%20%20%20_ab%20%3D%201.0%20%2F%20float(power_iteration(_op%2C%20seed%3D0)%5B0%5D)%0A%20%20%20%20%20%20%20%20_r%20%3D%20solve_nnqp_mprgp(_op%2C%20_b%2C%20tol%3D1e-10%2C%20alpha_bar%3D_ab)%0A%20%20%20%20%20%20%20%20break_cg.append(_r.cg_steps)%0A%20%20%20%20%20%20%20%20break_exp.append(_r.expansion_steps)%0A%20%20%20%20%20%20%20%20break_prop.append(_r.proportioning_steps)%0A%20%20%20%20return%20break_cg%2C%20break_exp%2C%20break_kappa%2C%20break_prop%0A%0A%0A%40app.cell%0Adef%20_(break_cg%2C%20break_exp%2C%20break_kappa%2C%20break_prop%2C%20np%2C%20plt)%3A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%204.5))%0A%20%20%20%20_x%20%3D%20np.arange(len(break_kappa))%0A%20%20%20%20_ax.bar(_x%2C%20break_cg%2C%20label%3D%22CG%20steps%20(minimise%20in%20face)%22%2C%20color%3D%22%2311D48E%22)%0A%20%20%20%20_ax.bar(_x%2C%20break_exp%2C%20bottom%3Dbreak_cg%2C%20label%3D%22expansion%20(add%20constraints)%22%2C%20color%3D%22%230a8f5f%22)%0A%20%20%20%20_ax.bar(%0A%20%20%20%20%20%20%20%20_x%2C%0A%20%20%20%20%20%20%20%20break_prop%2C%0A%20%20%20%20%20%20%20%20bottom%3D%5Bc%20%2B%20e%20for%20c%2C%20e%20in%20zip(break_cg%2C%20break_exp%2C%20strict%3DTrue)%5D%2C%0A%20%20%20%20%20%20%20%20label%3D%22proportioning%20(release)%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22%23f0a500%22%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_xticks(_x)%0A%20%20%20%20_ax.set_xticklabels(%5Bf%22%2410%5E%7B%7B%7Bround(np.log10(k))%7D%7D%7D%24%22%20for%20k%20in%20break_kappa%5D)%0A%20%20%20%20_ax.set_xlabel(r%22condition%20number%20%24%5Ckappa%24%22)%0A%20%20%20%20_ax.set_ylabel(%22MPRGP%20steps%22)%0A%20%20%20%20_ax.set_title(r%22MPRGP%20move%20breakdown%20(%24n%3D250%24%2C%20tol%20%24%3D10%5E%7B-10%7D%24)%22)%0A%20%20%20%20_ax.legend()%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%206.%20MPRGP%20is%20first-order%3A%20accuracy%20tracks%20the%20tolerance%0A%0A%20%20%20%20The%20active-set%20loop%20returns%20a%20near-exact%20iterate%20regardless%20of%20%60tol%60%20(it%0A%20%20%20%20solves%20each%20face%20by%20CG%20to%20a%20tight%20inner%20tolerance).%20MPRGP's%20recovery%20error%2C%0A%20%20%20%20by%20contrast%2C%20is%20proportional%20to%20its%20projected-gradient%20tolerance%20times%20the%0A%20%20%20%20conditioning%20%E2%80%94%20halve%20the%20tolerance%2C%20roughly%20halve%20the%20error.%20This%20is%20the%0A%20%20%20%20price%20of%20never%20factorising%20a%20face%2C%20and%20the%20reason%20the%20comparisons%20above%0A%20%20%20%20matched%20accuracy%20explicitly.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(DenseOperator%2C%20make_problem%2C%20np%2C%20power_iteration%2C%20solve_nnqp_mprgp)%3A%0A%20%20%20%20tol_grid%20%3D%20np.array(%5B1e-6%2C%201e-8%2C%201e-10%2C%201e-12%5D)%0A%20%20%20%20tol_errs%20%3D%20%7B%7D%0A%20%20%20%20for%20_kappa%20in%20(1e2%2C%201e4%2C%201e6)%3A%0A%20%20%20%20%20%20%20%20_a%2C%20_b%2C%20_x_star%20%3D%20make_problem(200%2C%20float(_kappa)%2C%200.5%2C%200)%0A%20%20%20%20%20%20%20%20_op%20%3D%20DenseOperator(_a)%0A%20%20%20%20%20%20%20%20_ab%20%3D%201.0%20%2F%20float(power_iteration(_op%2C%20seed%3D0)%5B0%5D)%0A%20%20%20%20%20%20%20%20_errs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_tol%20in%20tol_grid%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_r%20%3D%20solve_nnqp_mprgp(_op%2C%20_b%2C%20tol%3Dfloat(_tol)%2C%20alpha_bar%3D_ab%2C%20max_iter%3D200_000)%0A%20%20%20%20%20%20%20%20%20%20%20%20_errs.append(float(np.max(np.abs(_r.x%20-%20_x_star))))%0A%20%20%20%20%20%20%20%20tol_errs%5B_kappa%5D%20%3D%20_errs%0A%20%20%20%20return%20tol_errs%2C%20tol_grid%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20plt%2C%20tol_errs%2C%20tol_grid)%3A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%204.5))%0A%20%20%20%20_colors%20%3D%20%7B1e2%3A%20%22%2311D48E%22%2C%201e4%3A%20%22%230a8f5f%22%2C%201e6%3A%20%22%23f0a500%22%7D%0A%20%20%20%20for%20_kappa%2C%20_errs%20in%20tol_errs.items()%3A%0A%20%20%20%20%20%20%20%20_kexp%20%3D%20round(np.log10(_kappa))%0A%20%20%20%20%20%20%20%20_ax.loglog(tol_grid%2C%20_errs%2C%20%22o-%22%2C%20label%3Drf%22%24%5Ckappa%3D10%5E%7B%7B%7B_kexp%7D%7D%7D%24%22%2C%20color%3D_colors%5B_kappa%5D)%0A%20%20%20%20_ax.set_xlabel(r%22MPRGP%20tolerance%20(relative%20projected%20gradient)%22)%0A%20%20%20%20_ax.set_ylabel(r%22recovery%20error%20%24%5C%7Cx%20-%20x%5E%5Cstar%5C%7C_%5Cinfty%24%22)%0A%20%20%20%20_ax.set_title(%22MPRGP%20accuracy%20is%20proportional%20to%20tolerance%20(and%20to%20%24%5C%5Ckappa%24)%22)%0A%20%20%20%20_ax.legend()%0A%20%20%20%20_ax.grid(True%2C%20which%3D%22both%22%2C%20alpha%3D0.3)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%207.%20So%20%E2%80%94%20is%20MPRGP%20faster%3F%20When%20to%20reach%20for%20each%0A%0A%20%20%20%20**On%20this%20problem%20class%2C%20no.**%20For%20dense%20SPD%20non-negative%20QPs%20the%0A%20%20%20%20**active-set%20loop%20is%20the%20stronger%20default**%3A%20fewer%2C%20cheaper%20effective%0A%20%20%20%20products%2C%20machine-accuracy%20iterates%20for%20free%2C%20and%20a%20lead%20that%20widens%20with%0A%20%20%20%20conditioning.%20MPRGP%20ranges%20from%20roughly%20on-par%20to%20several%20times%20slower%20here.%0A%0A%20%20%20%20That%20is%20not%20a%20knock%20on%20MPRGP%20%E2%80%94%20it%20is%20the%20wrong%20benchmark%20for%20its%20strengths.%0A%20%20%20%20Reach%20for%20**MPRGP**%20when%3A%0A%0A%20%20%20%20-%20**the%20operator%20is%20huge%2C%20sparse%2C%20or%20purely%20matrix-free**%20(e.g.%20FEM%20contact%0A%20%20%20%20%20%20problems)%20%E2%80%94%20MPRGP%20never%20forms%20or%20solves%20a%20face%2C%20so%20it%20sidesteps%20the%0A%20%20%20%20%20%20reduced-solve%20cost%20that%20the%20active-set%20loop%20leans%20on%3B%0A%20%20%20%20-%20the%20active-set%20search%20**thrashes%20combinatorially**%20(many%20bound%20changes%2C%0A%20%20%20%20%20%20the%20cycling%20the%20Bland%20fallback%20exists%20to%20catch)%20%E2%80%94%20MPRGP%20is%20monotone%20with%20a%0A%20%20%20%20%20%20*proven*%20%24R%24-linear%20rate%2C%20no%20worst-case%20blow-up%20in%20the%20number%20of%20faces%3B%0A%20%20%20%20-%20a%20**guaranteed%20convergence-rate%20bound**%20matters%20more%20than%20a%20machine-exact%0A%20%20%20%20%20%20answer%2C%20or%20a%20good%20feasible%20point%20early%20is%20worth%20more%20than%20the%20last%20digits.%0A%0A%20%20%20%20Reach%20for%20the%20**active-set%20loop**%20(%60solve_nnqp%60)%20when%20the%20problem%20is%0A%20%20%20%20moderate%20and%20dense-ish%2C%20high%20accuracy%20is%20wanted%20cheaply%2C%20or%20you%20are%0A%20%20%20%20**warm-starting%20across%20a%20parameter%20sweep**%20%E2%80%94%20a%20support-stable%20step%20converges%0A%20%20%20%20in%20a%20single%20outer%20iteration%2C%20which%20MPRGP%20has%20no%20direct%20analogue%20for.%0A%0A%20%20%20%20The%20two%20are%20complementary%2C%20and%20%60nncg%60%20exposes%20both%20behind%20the%20same%20operator%0A%20%20%20%20interface%20so%20you%20can%20swap%20%60solve_nnqp%60%20%E2%86%94%20%60solve_nnqp_mprgp%60%20on%20the%20identical%0A%20%20%20%20problem%20and%20measure%20%E2%80%94%20exactly%20as%20this%20notebook%20did.%0A%0A%20%20%20%20%23%23%23%20Where%20to%20go%20next%0A%0A%20%20%20%20-%20**%5BActive-set%20methods%5D(01_active_set_methods.html)**%20%E2%80%94%20the%20block-pivot%0A%20%20%20%20%20%20machinery%20and%20the%20Bland-fallback%20termination%20proof.%0A%20%20%20%20-%20**%5BTest%20problems%5D(03_test_problems.html)**%20%E2%80%94%20the%20planted-optimum%0A%20%20%20%20%20%20generators%20used%20throughout%2C%20including%20the%20adversarial%20family.%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%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A