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%20Optimistic%20selection%20from%20a%20lower%20linear%20program%0A%0A%20%20%20%20This%20example%20shows%20what%20*optimistic*%20bilevel%20semantics%20means%20when%20the%0A%20%20%20%20lower-level%20problem%20has%20many%20optimal%20points.%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%20Consider%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%20x%5E2%20%2B%20(y-1)%5E2%20%5C%5C%0A%20%20%20%20%5Cmathop%7B%5Crm%20subject%5C%20to%7D%20%26%200%20%5Cleq%20x%20%5Cleq%201%2C%20%5C%5C%0A%20%20%20%20%20%20%26%20y%20%5Cin%20%5Cmathop%7B%5Crm%20argmin%7D_%7Bz%7D%5C%200%20%5C%5C%0A%20%20%20%20%20%20%26%20%5Cqquad%5Cmathop%7B%5Crm%20subject%5C%20to%7D%5Cquad%20x%20%5Cleq%20z%20%5Cleq%201.%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Every%20%24z%5Cin%5Bx%2C1%5D%24%20is%20lower-optimal.%20Under%20optimistic%20semantics%20the%20upper%0A%20%20%20%20level%20may%20select%2C%20among%20those%20tied%20lower%20optima%2C%20the%20value%20it%20prefers.%0A%20%20%20%20It%20therefore%20chooses%20%24y%3D1%24%2C%20while%20%24x%5E2%24%20selects%20%24x%3D0%24.%20The%20exact%20upper%0A%20%20%20%20objective%20is%20zero.%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%20The%20same%20CVXPY%20variable%20%60y%60%20appears%20in%20the%20lower%20constraints%20and%20upper%0A%20%20%20%20objective.%20BLVPY%20preserves%20that%20shared%20variable%20when%20it%20constructs%20the%0A%20%20%20%20single-level%20reformulation.%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(0.0%20*%20y)%2C%0A%20%20%20%20%20%20%20%20%5By%20%3E%3D%20x%2C%20y%20%3C%3D%201.0%5D%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%2B%20cp.square(y%20-%201.0))%2C%0A%20%20%20%20%20%20%20%20lower%2C%0A%20%20%20%20%20%20%20%20upper_constraints%3D%5Bx%20%3E%3D%200.0%2C%20x%20%3C%3D%201.0%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%20problem%2C%20x%2C%20y%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20problem%2C%20x%2C%20y)%3A%0A%20%20%20%20epsilon_target%20%3D%201e-5%0A%20%20%20%20result%20%3D%20problem.solve(epsilon_target%3Depsilon_target)%0A%20%20%20%20diagnostics%20%3D%20problem.gap_diagnostics(result)%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))%2C%20result.objective%5D%2C%0A%20%20%20%20%20%20%20%20%5B0.0%2C%201.0%2C%200.0%5D%2C%0A%20%20%20%20%20%20%20%20atol%3D5e-3%2C%0A%20%20%20%20%20%20%20%20rtol%3D0.0%2C%0A%20%20%20%20)%0A%20%20%20%20return%20diagnostics%2C%20result%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(diagnostics%2C%20mo%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-%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-%20Optimistically%20selected%20lower%20solution%3A%20%24y%3D%7Bfloat(y.value)%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%20lower%20source%20gap%20is%20essentially%20zero%20for%20every%20feasible%20%24y%24%20in%0A%20%20%20%20this%20example.%20The%20value%20%24y%5Capprox1%24%20is%20selected%20because%20it%20is%20the%0A%20%20%20%20lower%20optimizer%20preferred%20by%20the%20upper%20objective.%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
615fa2463e6a339e38e0fa22fff6e82e