import%20marimo%0A%0A__generated_with%20%3D%20%220.23.16%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%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%20Best-of%20search%20for%20local%20bilevel%20solutions%0A%0A%20%20%20%20BLVPY%20solves%20a%20nonlinear%20single-level%20reformulation%20locally.%20A%20single%0A%20%20%20%20solve%20can%20therefore%20converge%20to%20different%20solutions%20from%20different%0A%20%20%20%20initial%20points.%20This%20example%20compares%20a%20deliberately%20chosen%20deterministic%0A%20%20%20%20start%20with%20BLVPY's%20randomized%20%60best_of%60%20search.%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%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%20from%20blvpy%20import%20BilevelProblem%2C%20LowerProblem%0A%0A%20%20%20%20figure_directory%20%3D%20Path(__file__).resolve().parent%20%2F%20%22figures%22%0A%20%20%20%20figure_directory.mkdir(parents%3DTrue%2C%20exist_ok%3DTrue)%0A%20%20%20%20plt.style.use(Path(__file__).resolve().parents%5B1%5D%20%2F%20%22_shared%22%20%2F%20%22zhlatex.mplstyle%22)%0A%20%20%20%20return%20BilevelProblem%2C%20LowerProblem%2C%20cp%2C%20figure_directory%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%23%20Problem%20formulation%0A%0A%20%20%20%20We%20solve%20the%20optimistic%20bilevel%20problem%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%5Cmathop%7B%5Crm%20minimize%7D_%7Bx%2Cy%7D%20%26%20(x%5E2-1)%5E2%2B0.2x%20%5C%5C%0A%20%20%20%20%5Cmathop%7B%5Crm%20subject%5C%20to%7D%20%26%0A%20%20%20%20%20%20y%5Cin%5Cmathop%7B%5Crm%20argmin%7D_%7Bz%7D%5C%20(z-x)%5E2.%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Here%20%24x%24%20is%20the%20upper%20variable%20and%20%24y%24%20is%20the%20lower%20variable.%20For%20every%0A%20%20%20%20fixed%20%24x%24%2C%20the%20lower%20problem%20has%20the%20unique%20solution%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20y%5E%5Cstar(x)%3Dx.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Substituting%20this%20response%20into%20the%20upper%20problem%20gives%20the%20tilted%0A%20%20%20%20double-well%20function%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%5Cphi(x)%3D(x%5E2-1)%5E2%2B0.2x.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Its%20stationary%20points%20satisfy%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%5Cphi'(x)%3D4x(x%5E2-1)%2B0.2%3D0.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Two%20of%20these%20points%20are%20local%20minima%3A%20a%20worse%20positive%20solution%20near%0A%20%20%20%20%24x%3D0.973994%24%20with%20objective%20%240.197434%24%2C%20and%20a%20better%20negative%20solution%0A%20%20%20%20near%20%24x%3D-1.024120%24%20with%20objective%20%24-0.202440%24.%20This%20known%20landscape%20lets%0A%20%20%20%20us%20identify%20which%20local%20solution%20each%20numerical%20run%20reaches.%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%23%20Specify%20the%20model%0A%0A%20%20%20%20%60LowerProblem(parameters%3D%5Bx%5D)%60%20declares%20that%20the%20lower%20problem%20treats%20the%0A%20%20%20%20upper%20variable%20%24x%24%20as%20fixed%20data.%20The%20lower%20variable%20%24y%24%20is%20retained%20in%0A%20%20%20%20the%20bilevel%20model%2C%20while%20the%20upper%20objective%20creates%20the%20nonconvex%0A%20%20%20%20double-well%20landscape%20used%20to%20demonstrate%20local%20solving.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(BilevelProblem%2C%20LowerProblem%2C%20cp)%3A%0A%20%20%20%20x%20%3D%20cp.Variable(name%3D%22x%22)%0A%20%20%20%20y%20%3D%20cp.Variable(name%3D%22y%22)%0A%0A%20%20%20%20lower%20%3D%20LowerProblem(%0A%20%20%20%20%20%20%20%20cp.Minimize(cp.square(y%20-%20x))%2C%0A%20%20%20%20%20%20%20%20parameters%3D%5Bx%5D%2C%0A%20%20%20%20)%0A%20%20%20%20problem%20%3D%20BilevelProblem(%0A%20%20%20%20%20%20%20%20cp.Minimize(cp.square(cp.square(x)%20-%201.0)%20%2B%200.2%20*%20x%20%2B%200.0%20*%20y)%2C%0A%20%20%20%20%20%20%20%20lower%2C%0A%20%20%20%20)%0A%20%20%20%20return%20problem%2C%20x%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%20Deterministic%20solve%20and%20randomized%20best-of%20search%0A%0A%20%20%20%20The%20ordinary%20solve%20preserves%20an%20explicit%20%60x.value%60%2C%20so%20setting%20it%20to%0A%20%20%20%20%241%24%20starts%20the%20local%20solver%20in%20the%20positive%20well.%20We%20then%20attach%0A%20%20%20%20%60sample_bounds%3D(-2%2C%202)%60%20and%20request%20five%20randomized%20runs.%20Sampling%20bounds%0A%20%20%20%20only%20describe%20where%20initial%20points%20may%20be%20drawn%3B%20they%20do%20not%20constrain%0A%20%20%20%20the%20mathematical%20variable.%0A%0A%20%20%20%20Every%20viable%20best-of%20run%20performs%20its%20own%20complete%20epsilon%20continuation.%0A%20%20%20%20BLVPY%20compares%20their%20final%20target-epsilon%20objectives%20and%20returns%20the%20best%0A%20%20%20%20acceptable%20run.%20Consequently%2C%20cost%20grows%20approximately%20linearly%20with%0A%20%20%20%20%60best_of%60.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20problem%2C%20x)%3A%0A%20%20%20%20epsilon_initial%20%3D%201e-2%0A%20%20%20%20epsilon_target%20%3D%201e-5%0A%0A%20%20%20%20x.value%20%3D%201.0%0A%20%20%20%20deterministic_result%20%3D%20problem.solve(%0A%20%20%20%20%20%20%20%20epsilon_initial%3Depsilon_initial%2C%0A%20%20%20%20%20%20%20%20epsilon_target%3Depsilon_target%2C%0A%20%20%20%20%20%20%20%20verbose%3DFalse%2C%0A%20%20%20%20)%0A%20%20%20%20deterministic_diagnostics%20%3D%20problem.gap_diagnostics(deterministic_result)%0A%20%20%20%20deterministic_x%20%3D%20float(np.asarray(deterministic_result.variable_values%5Bx%5D))%0A%0A%20%20%20%20x.sample_bounds%20%3D%20(-2.0%2C%202.0)%0A%20%20%20%20best_result%20%3D%20problem.solve(%0A%20%20%20%20%20%20%20%20epsilon_initial%3Depsilon_initial%2C%0A%20%20%20%20%20%20%20%20epsilon_target%3Depsilon_target%2C%0A%20%20%20%20%20%20%20%20best_of%3D5%2C%0A%20%20%20%20%20%20%20%20seed%3D42%2C%0A%20%20%20%20%20%20%20%20verbose%3DFalse%2C%0A%20%20%20%20)%0A%20%20%20%20best_diagnostics%20%3D%20problem.gap_diagnostics(best_result)%0A%20%20%20%20best_x%20%3D%20float(np.asarray(best_result.variable_values%5Bx%5D))%0A%0A%20%20%20%20initial_x%20%3D%20np.array(%5Bfloat(np.asarray(run.initial_values%5Bx%5D))%20for%20run%20in%20best_result.runs%5D)%0A%20%20%20%20run_objectives%20%3D%20np.array(%5Brun.objective%20for%20run%20in%20best_result.runs%5D%2C%20dtype%3Dfloat)%0A%0A%20%20%20%20assert%20deterministic_result.succeeded%2C%20deterministic_result.message%0A%20%20%20%20assert%20best_result.succeeded%2C%20best_result.message%0A%20%20%20%20assert%20len(best_result.runs)%20%3D%3D%205%20and%20all(run.succeeded%20for%20run%20in%20best_result.runs)%2C%20(%0A%20%20%20%20%20%20%20%20%22Expected%20five%20viable%20best-of%20runs.%22%0A%20%20%20%20)%0A%20%20%20%20assert%20np.any(initial_x%20%3C%200.0)%20and%20np.any(initial_x%20%3E%200.0)%2C%20%22Expected%20sampled%20starts%20in%20both%20local%20basins.%22%0A%20%20%20%20assert%20abs(deterministic_x%20-%200.973994)%20%3C%3D%203e-3%2C%20%22The%20deterministic%20solve%20missed%20the%20positive%20minimum.%22%0A%20%20%20%20assert%20abs(best_x%20-%20(-1.024120))%20%3C%3D%203e-3%2C%20%22Best-of%20did%20not%20select%20the%20negative%20minimum.%22%0A%20%20%20%20assert%20best_result.objective%20%3C%3D%20deterministic_result.objective%20-%200.3%2C%20(%0A%20%20%20%20%20%20%20%20%22Best-of%20did%20not%20materially%20improve%20on%20the%20deterministic%20local%20solution.%22%0A%20%20%20%20)%0A%20%20%20%20assert%20np.isclose(best_result.objective%2C%20np.min(run_objectives)%2C%20atol%3D1e-8)%2C%20(%0A%20%20%20%20%20%20%20%20%22The%20selected%20result%20is%20not%20the%20best%20terminal%20run%20objective.%22%0A%20%20%20%20)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20best_diagnostics%2C%0A%20%20%20%20%20%20%20%20best_result%2C%0A%20%20%20%20%20%20%20%20best_x%2C%0A%20%20%20%20%20%20%20%20deterministic_diagnostics%2C%0A%20%20%20%20%20%20%20%20deterministic_result%2C%0A%20%20%20%20%20%20%20%20deterministic_x%2C%0A%20%20%20%20%20%20%20%20initial_x%2C%0A%20%20%20%20%20%20%20%20run_objectives%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%20%23%23%20Visualizing%20local%20outcomes%0A%0A%20%20%20%20The%20left%20panel%20shows%20where%20the%20two%20top-level%20solves%20finish%20on%20the%20known%0A%20%20%20%20reduced%20objective.%20The%20right%20panel%20relates%20every%20randomized%20initial%20point%0A%20%20%20%20to%20its%20terminal%20objective.%20Runs%20ending%20in%20the%20same%20well%20have%20nearly%20equal%0A%20%20%20%20objectives%20even%20though%20their%20initial%20points%20differ.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20best_result%2C%0A%20%20%20%20best_x%2C%0A%20%20%20%20deterministic_result%2C%0A%20%20%20%20deterministic_x%2C%0A%20%20%20%20figure_directory%2C%0A%20%20%20%20initial_x%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20run_objectives%2C%0A)%3A%0A%20%20%20%20figure%2C%20axes%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(10%2C%204.2))%0A%0A%20%20%20%20_grid%20%3D%20np.linspace(-1.6%2C%201.6%2C%20500)%0A%20%20%20%20_landscape%20%3D%20(_grid**2%20-%201.0)%20**%202%20%2B%200.2%20*%20_grid%0A%20%20%20%20axes%5B0%5D.plot(_grid%2C%20_landscape%2C%20color%3D%220.25%22%2C%20linewidth%3D2)%0A%20%20%20%20axes%5B0%5D.scatter(%0A%20%20%20%20%20%20%20%20deterministic_x%2C%0A%20%20%20%20%20%20%20%20deterministic_result.objective%2C%0A%20%20%20%20%20%20%20%20color%3D%22tab%3Aorange%22%2C%0A%20%20%20%20%20%20%20%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20s%3D75%2C%0A%20%20%20%20%20%20%20%20label%3D%22Deterministic%22%2C%0A%20%20%20%20%20%20%20%20zorder%3D3%2C%0A%20%20%20%20)%0A%20%20%20%20axes%5B0%5D.scatter(%0A%20%20%20%20%20%20%20%20best_x%2C%0A%20%20%20%20%20%20%20%20best_result.objective%2C%0A%20%20%20%20%20%20%20%20color%3D%22tab%3Ared%22%2C%0A%20%20%20%20%20%20%20%20marker%3D%22*%22%2C%0A%20%20%20%20%20%20%20%20s%3D150%2C%0A%20%20%20%20%20%20%20%20label%3D%22Best-of%20selected%22%2C%0A%20%20%20%20%20%20%20%20zorder%3D3%2C%0A%20%20%20%20)%0A%20%20%20%20axes%5B0%5D.set_xlabel(%22%24x%24%22)%0A%20%20%20%20axes%5B0%5D.set_ylabel(r%22%24%5Cphi(x)%20%3D%20(x%5E2-1)%5E2%2B0.2x%24%22)%0A%20%20%20%20axes%5B0%5D.legend(fontsize%3D12%2C%20frameon%3DFalse)%0A%0A%20%20%20%20for%20_run%2C%20_initial%2C%20_objective%20in%20zip(best_result.runs%2C%20initial_x%2C%20run_objectives)%3A%0A%20%20%20%20%20%20%20%20_selected%20%3D%20_run.index%20%3D%3D%20best_result.selected_run_index%0A%20%20%20%20%20%20%20%20axes%5B1%5D.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_initial%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20_objective%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22tab%3Ared%22%20if%20_selected%20else%20%22tab%3Ablue%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3D%22*%22%20if%20_selected%20else%20%22o%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20s%3D120%20if%20_selected%20else%2050%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D3%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20axes%5B1%5D.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22run%20%7B_run.index%20%2B%201%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(_initial%2C%20_objective)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(2%2C%206)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20axes%5B1%5D.set_xlabel(%22Sampled%20initial%20%24x%24%22)%0A%20%20%20%20axes%5B1%5D.set_ylabel(%22Terminal%20upper%20objective%22)%0A%20%20%20%20axes%5B1%5D.set_ylim(-0.25%2C%200.25)%0A%20%20%20%20axes%5B1%5D.set_xlim(-1.8%2C%201.8)%0A%0A%20%20%20%20figure.tight_layout()%0A%20%20%20%20figure_path%20%3D%20figure_directory%20%2F%20%22best_of_local_optima.pdf%22%0A%20%20%20%20figure.savefig(figure_path%2C%20bbox_inches%3D%22tight%22)%0A%20%20%20%20plt.show()%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20best_diagnostics%2C%0A%20%20%20%20best_result%2C%0A%20%20%20%20best_x%2C%0A%20%20%20%20deterministic_diagnostics%2C%0A%20%20%20%20deterministic_result%2C%0A%20%20%20%20deterministic_x%2C%0A%20%20%20%20mo%2C%0A)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Result%20and%20interpretation%0A%0A%20%20%20%20**Deterministic%20solve**%0A%0A%20%20%20%20-%20Status%3A%20%60%7Bdeterministic_result.status%7D%60%0A%20%20%20%20-%20Solution%3A%20%24x%3D%7Bdeterministic_x%3A.6f%7D%24%0A%20%20%20%20-%20Objective%3A%20%24%7Bdeterministic_result.objective%3A.6f%7D%24%0A%20%20%20%20-%20Final%20epsilon%3A%20%24%7Bdeterministic_result.final_epsilon%3A.3e%7D%24%0A%20%20%20%20-%20Maximum%20lifted%20violation%3A%20%24%7Bdeterministic_result.residuals.max_violation%3A.3e%7D%24%0A%20%20%20%20-%20Complementarity%3A%20%24%7Bdeterministic_result.complementarity%3A.3e%7D%24%0A%20%20%20%20-%20Lower%20source%20gap%3A%20%24%7Bdeterministic_diagnostics.source_gap%3A.3e%7D%24%0A%0A%20%20%20%20**Best-of%20solve**%0A%0A%20%20%20%20-%20Status%3A%20%60%7Bbest_result.status%7D%60%0A%20%20%20%20-%20Selected%20run%3A%20%7Bbest_result.selected_run_index%20%2B%201%7D%20of%20%7Blen(best_result.runs)%7D%0A%20%20%20%20-%20Solution%3A%20%24x%3D%7Bbest_x%3A.6f%7D%24%0A%20%20%20%20-%20Objective%3A%20%24%7Bbest_result.objective%3A.6f%7D%24%0A%20%20%20%20-%20Final%20epsilon%3A%20%24%7Bbest_result.final_epsilon%3A.3e%7D%24%0A%20%20%20%20-%20Maximum%20lifted%20violation%3A%20%24%7Bbest_result.residuals.max_violation%3A.3e%7D%24%0A%20%20%20%20-%20Complementarity%3A%20%24%7Bbest_result.complementarity%3A.3e%7D%24%0A%20%20%20%20-%20Lower%20source%20gap%3A%20%24%7Bbest_diagnostics.source_gap%3A.3e%7D%24%0A%0A%20%20%20%20The%20deterministic%20start%20reaches%20the%20worse%20positive%20local%20minimum.%20The%0A%20%20%20%20sampled%20runs%20explore%20both%20basins%2C%20allowing%20%60best_of%60%20to%20return%20the%20better%0A%20%20%20%20negative%20solution.%0A%20%20%20%20%22%22%22)%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
56bce358f3e82c9ac3e02459c58f2d9e