parameter dependent socp

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%20A%20parameter-dependent%20second-order%20cone%20problem%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%201.%20The%20bilevel%20model%0A%0A%20%20%20%20The%20upper%20problem%20chooses%20a%20scalar%20%24x%24%20in%20the%20interval%20%24%5B0.5%2C2%5D%24.%20For%0A%20%20%20%20this%20fixed%20value%2C%20the%20lower%20problem%20selects%20%24y%5Cin%5Cmathbf%7BR%7D%5E2%24%20and%20an%0A%20%20%20%20epigraph%20variable%20%24t%5Cin%5Cmathbf%7BR%7D%24%20by%20solving%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%5Cunderset%7By%2Ct%7D%7B%5Coperatorname%7Bminimize%7D%7D%0A%20%20%20%20%20%20%20%20%26%20t%20%5C%5C%0A%20%20%20%20%5Coperatorname%7Bsubject%5C%20to%7D%0A%20%20%20%20%20%20%20%20%26%20%5ClVert%20y%5CrVert_2%20%5Cleq%20t%2C%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20x%20y_1%2By_2%5Cgeq%201.%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20The%20upper%20problem%20anticipates%20this%20response%20and%20solves%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%5Cunderset%7B0.5%5Cleq%20x%5Cleq2%7D%7B%5Coperatorname%7Bminimize%7D%7D%0A%20%20%20%20%20%20%20%5Cquad%20(x-1.25)%5E2%2B0.1t%5E%5Cstar(x).%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Thus%2C%20%24x%24%20is%20the%20upper%20variable%2C%20while%20%24y%24%20and%20%24t%24%20are%20the%20lower%0A%20%20%20%20variables.%20The%20first%20upper-objective%20term%20prefers%20%24x%3D1.25%24%3B%20the%20second%0A%20%20%20%20penalizes%20the%20minimum%20norm%20attained%20by%20the%20lower%20problem.%0A%0A%20%20%20%20In%20%60LowerProblem%60%2C%20%60parameters%3D%5Bx%5D%60%20means%20that%20%24x%24%20is%20held%20fixed%20when%0A%20%20%20%20checking%20and%20solving%20the%20lower%20problem.%20For%20every%20fixed%20%24x%24%2C%20this%20is%0A%20%20%20%20a%20convex%20SOCP%2C%20even%20though%20%24xy_1%24%20would%20be%20bilinear%20if%20%24x%24%20and%20%24y%24%20were%0A%20%20%20%20optimized%20jointly%20in%20an%20ordinary%20CVXPY%20problem.%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%202.%20Geometric%20interpretation%20of%20the%20lower%20problem%0A%0A%20%20%20%20Define%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20a(x)%3D%5Cbegin%7Bbmatrix%7Dx%5C%5C1%5Cend%7Bbmatrix%7D.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20The%20moving-halfspace%20constraint%20is%20%24a(x)%5ETy%5Cgeq1%24.%20Since%20minimizing%20%24t%24%0A%20%20%20%20subject%20to%20%24%5ClVert%20y%5CrVert_2%5Cleq%20t%24%20is%20equivalent%20to%20minimizing%0A%20%20%20%20%24%5ClVert%20y%5CrVert_2%24%2C%20the%20lower%20problem%20finds%20the%20minimum-norm%20point%20in%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%5C%7By%20%5Cmid%20a(x)%5ETy%5Cgeq1%5C%7D.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20The%20optimum%20lies%20on%20the%20boundary%20%24a(x)%5ETy%3D1%24.%20Cauchy--Schwarz%20gives%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%201%3Da(x)%5ETy%5Cleq%5ClVert%20a(x)%5CrVert_2%5ClVert%20y%5CrVert_2%2C%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20so%20%24%5ClVert%20y%5CrVert_2%5Cgeq1%2F%5ClVert%20a(x)%5CrVert_2%24.%20Equality%20holds%20when%0A%20%20%20%20%24y%24%20is%20parallel%20to%20%24a(x)%24.%20Therefore%2C%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20y%5E%5Cstar(x)%0A%20%20%20%20%20%20%3D%5Cfrac%7Ba(x)%7D%7B%5ClVert%20a(x)%5CrVert_2%5E2%7D%0A%20%20%20%20%20%20%3D%5Cfrac%7B1%7D%7Bx%5E2%2B1%7D%5Cbegin%7Bbmatrix%7Dx%5C%5C1%5Cend%7Bbmatrix%7D%2C%0A%20%20%20%20%20%20%5Cqquad%0A%20%20%20%20%20%20t%5E%5Cstar(x)%3D%5Cfrac%7B1%7D%7B%5Csqrt%7Bx%5E2%2B1%7D%7D.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20The%20notebook%20later%20uses%20these%20formulas%20as%20an%20independent%20numerical%20check%0A%20%20%20%20of%20BLVPY's%20returned%20lower-level%20solution.%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%203.%20The%20analytically%20reduced%20upper%20problem%0A%0A%20%20%20%20Substituting%20the%20exact%20lower%20response%20reduces%20the%20bilevel%20problem%20to%0A%20%20%20%20the%20one-dimensional%20problem%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%5Cunderset%7B0.5%5Cleq%20x%5Cleq2%7D%7B%5Coperatorname%7Bminimize%7D%7D%0A%20%20%20%20%20%20%5Cquad%0A%20%20%20%20%20%20%5Cphi(x)%3D(x-1.25)%5E2%2B%5Cfrac%7B0.1%7D%7B%5Csqrt%7Bx%5E2%2B1%7D%7D.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20At%20an%20interior%20solution%2C%20the%20first-order%20condition%20is%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%5Cphi'(x)%0A%20%20%20%20%20%20%3D2(x-1.25)-%5Cfrac%7B0.1x%7D%7B(x%5E2%2B1)%5E%7B3%2F2%7D%7D%3D0.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Solving%20this%20scalar%20equation%20gives%20the%20reference%20values%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%20%20x%5E%5Cstar%20%26%5Capprox%201.265084%2C%5C%5C%0A%20%20%20%20%20%20y%5E%5Cstar%20%26%5Capprox%20(0.486489%2C%5C%200.384551)%2C%5C%5C%0A%20%20%20%20%20%20t%5E%5Cstar%20%26%5Capprox%200.620121%2C%5C%5C%0A%20%20%20%20%20%20%5Cphi(x%5E%5Cstar)%20%26%5Capprox%200.062240.%0A%20%20%20%20%5Cend%7Baligned%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%20inspect%20the%20model%0A%0A%20%20%20%20CVXPY's%20norm%20epigraph%20becomes%20a%20second-order%20cone%20block.%20BLVPY%20extracts%0A%20%20%20%20affine%20maps%20for%20the%20complete%20canonical%20data%2C%20so%20those%20data%20can%20be%0A%20%20%20%20evaluated%20at%20different%20upper%20points%20without%20re-canonicalizing%20the%20model.%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(2%2C%20name%3D%22y%22)%0A%20%20%20%20t%20%3D%20cp.Variable(name%3D%22t%22)%0A%0A%20%20%20%20lower%20%3D%20LowerProblem(%0A%20%20%20%20%20%20%20%20cp.Minimize(t)%2C%0A%20%20%20%20%20%20%20%20%5Bcp.norm(y%2C%202)%20%3C%3D%20t%2C%20x%20*%20y%5B0%5D%20%2B%20y%5B1%5D%20%3E%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-%201.25)%20%2B%200.1%20*%20t)%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.5%2C%20x%20%3C%3D%202.0%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%20problem%2C%20t%2C%20x%2C%20y%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20problem%2C%20x)%3A%0A%20%20%20%20%23%20Canonicalize%20once.%20The%20returned%20metadata%20stores%20affine%20maps%20for%20the%0A%20%20%20%20%23%20conic%20data%2C%20so%20changing%20x%20only%20reevaluates%20those%20maps%3B%20it%20does%20not%20run%0A%20%20%20%20%23%20CVXPY's%20canonicalization%20chain%20again.%0A%20%20%20%20canonical%20%3D%20problem.canonicalize()%0A%0A%20%20%20%20%23%20Evaluate%20the%20canonical%20constraint%20matrix%20at%20two%20upper-variable%20values.%0A%20%20%20%20x.value%20%3D%200.75%0A%20%20%20%20data_at_low_x%20%3D%20canonical.apply_numeric()%0A%20%20%20%20x.value%20%3D%201.50%0A%20%20%20%20data_at_high_x%20%3D%20canonical.apply_numeric()%0A%0A%20%20%20%20%23%20Clear%20the%20inspection%20value%20so%20BLVPY%20applies%20its%20normal%20initialization%0A%20%20%20%20%23%20policy%20when%20the%20bilevel%20problem%20is%20solved%20below.%0A%20%20%20%20x.value%20%3D%20None%0A%0A%20%20%20%20%23%20These%20checks%20confirm%20both%20features%20illustrated%20by%20the%20example%3A%20the%0A%20%20%20%20%23%20lower%20canonicalization%20contains%20an%20SOC%20block%2C%20and%20A%20changes%20with%20x.%0A%20%20%20%20canonical_matrix_change%20%3D%20np.linalg.norm(data_at_high_x.A.toarray()%20-%20data_at_low_x.A.toarray())%0A%20%20%20%20assert%20canonical.cone_layout.second_order%2C%20%22Expected%20the%20lower%20problem%20to%20contain%20an%20SOC%20block.%22%0A%20%20%20%20assert%20canonical_matrix_change%20%3E%200.1%2C%20%22Expected%20the%20canonical%20constraint%20matrix%20to%20depend%20on%20x.%22%0A%20%20%20%20return%20(canonical_matrix_change%2C)%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20problem%2C%20t%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%2C%20verbose%3DTrue)%0A%20%20%20%20diagnostics%20%3D%20problem.gap_diagnostics(result)%0A%0A%20%20%20%20reference_x%20%3D%201.265084110259083%0A%20%20%20%20reference_direction%20%3D%20np.array(%5Breference_x%2C%201.0%5D)%0A%20%20%20%20reference_y%20%3D%20reference_direction%20%2F%20(reference_direction%20%40%20reference_direction)%0A%20%20%20%20reference_t%20%3D%201.0%20%2F%20np.linalg.norm(reference_direction)%0A%20%20%20%20reference_objective%20%3D%20(reference_x%20-%201.25)%20**%202%20%2B%200.1%20*%20reference_t%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%20*np.asarray(y.value)%2C%20float(np.asarray(t.value))%5D%2C%0A%20%20%20%20%20%20%20%20%5Breference_x%2C%20*reference_y%2C%20reference_t%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-%20reference_objective)%20%3C%3D%205e-3%2C%20%22Upper%20objective%20does%20not%20match%20the%20reference%20value.%22%0A%20%20%20%20return%20diagnostics%2C%20epsilon_target%2C%20result%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20canonical_matrix_change%2C%0A%20%20%20%20diagnostics%2C%0A%20%20%20%20epsilon_target%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20result%2C%0A%20%20%20%20t%2C%0A%20%20%20%20x%2C%0A%20%20%20%20y%2C%0A)%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%20vector%3A%20%24y%3D(%7By.value%5B0%5D%3A.6f%7D%2C%20%7By.value%5B1%5D%3A.6f%7D)%24%0A%20%20%20%20-%20Lower%20epigraph%20variable%3A%20%24t%3D%7Bfloat(t.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-%20Change%20in%20canonical%20%24A%24%20between%20two%20inspected%20points%3A%0A%20%20%20%20%20%20%24%7Bcanonical_matrix_change%3A.3e%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%20returned%20lower%20point%20agrees%20with%20the%20projection%20formula%20above.%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