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%20An%20analytic%20quadratic%20bilevel%20problem%0A%0A%20%20%20%20This%20small%20example%20introduces%20BLVPY%20with%20a%20problem%20whose%20exact%20bilevel%0A%20%20%20%20solution%20can%20be%20derived%20by%20hand.%20The%20upper%20variable%20is%20%24x%24%20and%20the%20lower%0A%20%20%20%20decision%20is%20%24y%24.%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%20cvxpy%20as%20cp%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20from%20blvpy%20import%20BilevelProblem%2C%20LowerProblem%0A%0A%20%20%20%20return%20BilevelProblem%2C%20LowerProblem%2C%20cp%2C%20mo%2C%20np%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-1)%5E2%20%2B%20(y%2B1)%5E2%20%5C%5C%0A%20%20%20%20%5Cmathop%7B%5Crm%20subject%5C%20to%7D%20%26%0A%20%20%20%20%20%20y%20%5Cin%20%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%20For%20every%20fixed%20%24x%24%2C%20the%20unique%20lower%20solution%20is%20%24y%3Dx%24.%20Substitution%0A%20%20%20%20gives%20%242x%5E2%2B2%24%2C%20so%20the%20exact%20bilevel%20solution%20is%20%24x%3Dy%3D0%24%20with%20objective%0A%20%20%20%20value%20%242%24.%0A%0A%20%20%20%20BLVPY%20solves%20an%20%24%5Cepsilon%24-relaxed%20primal-dual%20reformulation.%20At%20a%20nonzero%0A%20%20%20%20%24%5Cepsilon%3E0%24%20the%20returned%20point%20can%20differ%20slightly%20from%20the%20exact%20solution%2C%0A%20%20%20%20and%20the%20difference%20vanishes%20as%20%24%5Cepsilon%20%5Cto%200%24.%20In%20this%20example%20the%0A%20%20%20%20relaxed%20solution%20is%20available%20analytically%3A%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20x_%5Cepsilon%3D%5Cfrac%7B%5Csqrt%7B%5Cepsilon%7D%7D%7B2%7D%2C%5Cqquad%0A%20%20%20%20%20%20y_%5Cepsilon%3D-%5Cfrac%7B%5Csqrt%7B%5Cepsilon%7D%7D%7B2%7D.%0A%20%20%20%20%5C%5D%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%20and%20solve%20the%20model%0A%0A%20%20%20%20%60LowerProblem(parameters%3D%5Bx%5D)%60%20declares%20that%20the%20lower-level%20optimizer%0A%20%20%20%20treats%20the%20upper%20variable%20%24x%24%20as%20fixed%20data.%20The%20original%20lower%20variable%0A%20%20%20%20%24y%24%20is%20shared%20with%20the%20upper%20objective%2C%20which%20gives%20optimistic%20semantics.%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(x%20-%201.0)%20%2B%20cp.square(y%20%2B%201.0))%2C%0A%20%20%20%20%20%20%20%20lower%2C%0A%20%20%20%20)%0A%20%20%20%20return%20problem%2C%20x%2C%20y%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20epsilon_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20steps%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%201e-12%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-11%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-9%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-3%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%201e-1%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20value%3D1e-5%2C%0A%20%20%20%20%20%20%20%20debounce%3DTrue%2C%0A%20%20%20%20%20%20%20%20show_value%3DTrue%2C%0A%20%20%20%20%20%20%20%20label%3Dr%22Target%20relaxation%20%24%5Cepsilon_%7B%5Cmathrm%7Btarget%7D%7D%24%22%2C%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%23%20Explore%20the%20relaxation%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20published%20documentation%20shows%20a%20non-interactive%20snapshot%20at%0A%20%20%20%20%20%20%20%20%20%20%20%20the%20default%20value%20%24%5Cepsilon_%7B%5Cmathrm%7Btarget%7D%7D%3D10%5E%7B-5%7D%24.%20In%20a%20live%0A%20%20%20%20%20%20%20%20%20%20%20%20Marimo%20session%2C%20drag%20the%20slider%20and%20release%20it%20to%20solve%20again.%20Its%0A%20%20%20%20%20%20%20%20%20%20%20%20logarithmically%20spaced%20values%20show%20how%20the%20relaxed%20point%20approaches%0A%20%20%20%20%20%20%20%20%20%20%20%20the%20exact%20bilevel%20solution%20as%20%24%5Cepsilon_%7B%5Cmathrm%7Btarget%7D%7D%24%20decreases.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20smallest%20targets%20also%20probe%20numerical%20precision%3A%20once%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20analytic%20displacement%20falls%20below%20the%20nonlinear%20solver's%20practical%0A%20%20%20%20%20%20%20%20%20%20%20%20accuracy%2C%20the%20returned%20point%20may%20no%20longer%20track%20the%20square-root%0A%20%20%20%20%20%20%20%20%20%20%20%20formula%20digit%20for%20digit.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20epsilon_slider%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%20(epsilon_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(epsilon_slider%2C%20np%2C%20problem%2C%20x%2C%20y)%3A%0A%20%20%20%20epsilon_target%20%3D%20float(epsilon_slider.value)%0A%20%20%20%20result%20%3D%20problem.solve(epsilon_target%3Depsilon_target%2C%20verbose%3DFalse)%0A%20%20%20%20diagnostics%20%3D%20problem.gap_diagnostics(result)%0A%20%20%20%20relaxed_shift%20%3D%20np.sqrt(epsilon_target)%20%2F%202.0%0A%20%20%20%20expected_objective%20%3D%202.0%20*%20(1.0%20-%20relaxed_shift)%20**%202%0A%0A%20%20%20%20assert%20result.succeeded%2C%20result.message%0A%20%20%20%20np.testing.assert_allclose(%0A%20%20%20%20%20%20%20%20%5Bfloat(np.asarray(x.value))%2C%20float(np.asarray(y.value))%5D%2C%0A%20%20%20%20%20%20%20%20%5Brelaxed_shift%2C%20-relaxed_shift%5D%2C%0A%20%20%20%20%20%20%20%20atol%3D3e-3%2C%0A%20%20%20%20%20%20%20%20rtol%3D0.0%2C%0A%20%20%20%20)%0A%20%20%20%20assert%20abs(result.objective%20-%20expected_objective)%20%3C%3D%205e-3%2C%20%22Upper%20objective%20does%20not%20match%20the%20analytic%20value.%22%0A%20%20%20%20return%20diagnostics%2C%20epsilon_target%2C%20relaxed_shift%2C%20result%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(diagnostics%2C%20epsilon_target%2C%20mo%2C%20relaxed_shift%2C%20result%2C%20x%2C%20y)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%23%23%20Result%20and%20interpretation%0A%0A%20%20%20%20-%20Status%3A%20%60%7Bresult.status%7D%60%0A%20%20%20%20-%20Target%20relaxation%3A%20%24%5Cepsilon_%7B%7B%5Cmathrm%7B%7Btarget%7D%7D%7D%7D%3D%7Bepsilon_target%3A.1e%7D%24%0A%20%20%20%20-%20Final%20epsilon%3A%20%24%7Bresult.final_epsilon%3A.1e%7D%24%0A%20%20%20%20-%20Upper%20variable%3A%20%24x%3D%7Bfloat(x.value)%3A.6f%7D%24%0A%20%20%20%20-%20Lower%20response%3A%20%24y%3D%7Bfloat(y.value)%3A.6f%7D%24%0A%20%20%20%20-%20Analytic%20relaxed%20point%3A%0A%20%20%20%20%20%20%24(x_%5Cepsilon%2Cy_%5Cepsilon)%3D(%7Brelaxed_shift%3A.6f%7D%2C%7B-relaxed_shift%3A.6f%7D)%24%0A%20%20%20%20-%20Upper%20objective%3A%20%24%7Bresult.objective%3A.6f%7D%24%0A%20%20%20%20-%20Maximum%20lifted%20violation%3A%20%24%7Bresult.residuals.max_violation%3A.3e%7D%24%0A%20%20%20%20-%20Complementarity%3A%20%24%7Bresult.complementarity%3A.3e%7D%24%0A%20%20%20%20-%20Independently%20evaluated%20lower%20source%20gap%3A%20%24%7Bdiagnostics.source_gap%3A.3e%7D%24%0A%0A%20%20%20%20The%20numerical%20point%20agrees%20with%20the%20analytic%20relaxed%20solution.%20In%20a%20live%0A%20%20%20%20Marimo%20session%2C%20move%20the%20slider%20toward%20smaller%20values%20to%20see%20it%20converge%20to%0A%20%20%20%20the%20exact%20bilevel%20point%20%24(0%2C0)%24%20and%20objective%20value%20%242%24.%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
5001f1b8aeaf178f78b10844e680e861