%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.12%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22clarabel%3E%3D0.11.1%22%2C%0A%23%20%20%20%20%20%22cvxpy-base%3E%3D1.8.2%22%2C%0A%23%20%20%20%20%20%22marimo%3E%3D0.25.0%22%2C%0A%23%20%20%20%20%20%22matplotlib%3E%3D3.10.8%22%2C%0A%23%20%20%20%20%20%22numpy%3E%3D2.4.3%22%2C%0A%23%20%5D%0A%23%0A%23%20%5Btool.marimo-studio%5D%0A%23%20default%20%3D%20%22explainer%22%0A%23%20runtimes%20%3D%20%5B%22server%22%2C%20%22zero-python%22%5D%0A%23%20show_cell_logs%20%3D%20false%0A%23%0A%23%20%5Btool.marimo-studio.cells%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.25.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22Quadratic%20Programs%22)%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%0A%40app.cell(hide_code%3DTrue)%0Adef%20introduction(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Quadratic%20programs%0A%0A%20%20%20%20A%20quadratic%20program%20is%20an%20optimization%20problem%20with%20a%20quadratic%20objective%20and%0A%20%20%20%20affine%20equality%20and%20inequality%20constraints.%20This%20notebook%20builds%20the%20geometry%0A%20%20%20%20of%20one%20small%20example.%20The%20objective%20is%20a%20bowl%2C%20the%20constraints%20are%20walls%2C%20and%0A%20%20%20%20the%20solution%20is%20the%20lowest%20point%20of%20the%20bowl%20that%20the%20walls%20allow.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20standard_form(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Standard%20form%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%20%20%26%20(1%2F2)x%5ETPx%20%2B%20q%5ETx%20%5C%5C%0A%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%20%26%20Gx%20%5Cleq%20h%20%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%20Ax%20%3D%20b%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Here%20%24P%20%5Cin%20%5Cmathcal%7BS%7D%5E%7Bn%7D_%2B%24%2C%20%24q%20%5Cin%20%5Cmathcal%7BR%7D%5En%24%2C%0A%20%20%20%20%24G%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bm%20%5Ctimes%20n%7D%24%2C%20%24h%20%5Cin%20%5Cmathcal%7BR%7D%5Em%24%2C%0A%20%20%20%20%24A%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bp%20%5Ctimes%20n%7D%24%2C%20and%20%24b%20%5Cin%20%5Cmathcal%7BR%7D%5Ep%24%20are%20problem%20data%2C%0A%20%20%20%20and%20%24x%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bn%7D%24%20is%20the%20optimization%20variable.%20The%20inequality%0A%20%20%20%20constraint%20%24Gx%20%5Cleq%20h%24%20is%20elementwise.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20why_quadratic(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Why%20quadratic%20programming%3F%0A%0A%20%20%20%20Quadratic%20programs%20are%20convex%20optimization%20problems%20that%20generalize%20both%20least%0A%20%20%20%20squares%20and%20linear%20programming.%20They%20can%20be%20solved%20efficiently%20and%20reliably%2C%0A%20%20%20%20even%20in%20real%20time.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20portfolio_example(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20An%20example%20from%20finance%0A%0A%20%20%20%20Suppose%20we%20have%20%24n%24%20different%20stocks%2C%20an%20estimate%20%24r%20%5Cin%20%5Cmathcal%7BR%7D%5En%24%20of%20the%0A%20%20%20%20expected%20return%20on%20each%20stock%2C%20and%20an%20estimate%20%24%5CSigma%20%5Cin%20%5Cmathcal%7BS%7D%5E%7Bn%7D_%2B%24%0A%20%20%20%20of%20the%20covariance%20of%20the%20returns.%20The%20problem%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%20%20%26%20(1%2F2)x%5ET%5CSigma%20x%20-%20r%5ETx%20%5C%5C%0A%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%20%26%20x%20%5Cgeq%200%20%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%20%5Cmathbf%7B1%7D%5ETx%20%3D%201%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20finds%20a%20nonnegative%20portfolio%20allocation%20%24x%20%5Cin%20%5Cmathcal%7BR%7D%5En_%2B%24%20that%20optimally%0A%20%20%20%20balances%20expected%20return%20and%20variance%20of%20return.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20duality(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Duality%0A%0A%20%20%20%20Solving%20a%20quadratic%20program%20also%20yields%20a%20dual%20solution%20%24%5Clambda%5E%5Cstar%24%2C%20one%0A%20%20%20%20entry%20for%20each%20inequality%20constraint.%20A%20positive%20entry%20%24%5Clambda%5E%5Cstar_i%24%20means%0A%20%20%20%20that%20the%20constraint%20%24g_i%5ETx%20%5Cleq%20h_i%24%20holds%20with%20equality%20at%20the%20solution%0A%20%20%20%20%24x%5E%5Cstar%24.%20Moving%20that%20wall%20would%20change%20the%20optimal%20value%2C%20at%20a%20rate%20of%0A%20%20%20%20%24%5Clambda%5E%5Cstar_i%24%20per%20unit.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20example_context(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20A%20two-dimensional%20example%0A%0A%20%20%20%20We%20solve%20a%20problem%20in%20two%20variables%20with%20CVXPY%2C%20so%20every%20part%20of%20it%20can%20be%0A%20%20%20%20drawn.%20Four%20walls%20%24g_i%5ETx%20%5Cleq%20h_i%24%20enclose%20a%20region%20around%20the%20origin.%20Each%0A%20%20%20%20%24g_i%24%20is%20a%20unit%20vector%2C%20so%20%24h_i%24%20is%20the%20distance%20from%20the%20origin%20to%20wall%20%24i%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%20from%20itertools%20import%20combinations%0A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20return%20combinations%2C%20cp%2C%20np%2C%20plt%0A%0A%0A%40app.cell%0Adef%20problem_data(np)%3A%0A%20%20%20%20wall_angles%20%3D%20np.radians(%5B15%2C%20110%2C%20205%2C%20295%5D)%0A%20%20%20%20G%20%3D%20np.column_stack(%5Bnp.cos(wall_angles)%2C%20np.sin(wall_angles)%5D)%0A%20%20%20%20h%20%3D%20np.array(%5B1.5%2C%201.25%2C%201.75%2C%201.4%5D)%0A%20%20%20%20pull_strength%20%3D%207.0%0A%0A%0A%20%20%20%20def%20pull(direction)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Return%20the%20linear%20term%20q%20pointing%20%60direction%60%20degrees%20from%20the%20x-axis.%22%22%22%0A%20%20%20%20%20%20%20%20radians%20%3D%20np.radians(direction)%0A%20%20%20%20%20%20%20%20return%20pull_strength%20*%20np.array(%5Bnp.cos(radians)%2C%20np.sin(radians)%5D)%0A%0A%20%20%20%20return%20G%2C%20h%2C%20pull%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20objective_context(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20The%20objective%0A%0A%20%20%20%20%24P%24%20sets%20the%20shape%20of%20the%20bowl.%20The%20linear%20term%20%24q%24%20pulls%20the%20bottom%20of%20the%0A%20%20%20%20bowl%20away%20from%20the%20origin%2C%20toward%20and%20sometimes%20past%20the%20walls.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20curvature(mo)%3A%0A%20%20%20%20curvature%20%3D%20mo.ui.radio(%0A%20%20%20%20%20%20%20%20options%3D%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Round%22%3A%20%5B%5B3.0%2C%200.0%5D%2C%20%5B0.0%2C%203.0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Stretched%22%3A%20%5B%5B6.0%2C%200.0%5D%2C%20%5B0.0%2C%201.5%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Tilted%22%3A%20%5B%5B4.0%2C%20-1.4%5D%2C%20%5B-1.4%2C%204.0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Narrow%20valley%22%3A%20%5B%5B5.0%2C%204.5%5D%2C%20%5B4.5%2C%205.0%5D%5D%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20value%3D%22Tilted%22%2C%0A%20%20%20%20%20%20%20%20label%3D%22Shape%20of%20%24P%24%22%2C%0A%20%20%20%20)%0A%20%20%20%20curvature%0A%20%20%20%20return%20(curvature%2C)%0A%0A%0A%40app.cell%0Adef%20objective_matrix(curvature%2C%20np)%3A%0A%20%20%20%20P%20%3D%20np.array(curvature.value)%0A%20%20%20%20return%20(P%2C)%0A%0A%0A%40app.cell%0Adef%20bowl(P%2C%20np)%3A%0A%20%20%20%20eigenvalues%2C%20eigenvectors%20%3D%20np.linalg.eigh(P)%0A%0A%0A%20%20%20%20def%20level_radii(rise)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Semi-axes%20of%20the%20level%20set%20lying%20%60rise%60%20above%20the%20bottom%20of%20the%20bowl.%22%22%22%0A%20%20%20%20%20%20%20%20return%20np.sqrt(2%20*%20max(rise%2C%200.0)%20%2F%20eigenvalues).tolist()%0A%0A%0A%20%20%20%20bowl%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22angle%22%3A%20float(np.degrees(np.arctan2(eigenvectors%5B1%2C%200%5D%2C%20eigenvectors%5B0%2C%200%5D)))%2C%0A%20%20%20%20%20%20%20%20%22levels%22%3A%20%5Blevel_radii(step**2%20%2F%202)%20for%20step%20in%20range(1%2C%207)%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20bowl%2C%20level_radii%0A%0A%0A%40app.cell%0Adef%20pull_direction(mo)%3A%0A%20%20%20%20pull_direction%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%200%2C%0A%20%20%20%20%20%20%20%20330%2C%0A%20%20%20%20%20%20%20%20step%3D30%2C%0A%20%20%20%20%20%20%20%20value%3D210%2C%0A%20%20%20%20%20%20%20%20label%3D%22Direction%20of%20%24q%24%20(degrees)%22%2C%0A%20%20%20%20%20%20%20%20show_value%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20pull_direction%0A%20%20%20%20return%20(pull_direction%2C)%0A%0A%0A%40app.cell%0Adef%20linear_term(pull%2C%20pull_direction)%3A%0A%20%20%20%20q%20%3D%20pull(pull_direction.value)%0A%20%20%20%20return%20(q%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20problem_context(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Next%2C%20we%20specify%20the%20problem.%20Notice%20that%20we%20use%20the%20%60quad_form%60%20function%20from%0A%20%20%20%20CVXPY%20to%20create%20the%20quadratic%20form%20%24x%5ETPx%24.%20The%20problem%20is%20written%20as%20a%20function%0A%20%20%20%20of%20the%20linear%20term%2C%20so%20it%20can%20be%20solved%20for%20any%20%24q%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20solver(G%2C%20P%2C%20cp%2C%20h%2C%20level_radii%2C%20np)%3A%0A%20%20%20%20def%20solve(q)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Solve%20the%20program%20for%20the%20linear%20term%20q%20and%20describe%20the%20solution.%22%22%22%0A%20%20%20%20%20%20%20%20x%20%3D%20cp.Variable(2)%0A%20%20%20%20%20%20%20%20walls%20%3D%20G%20%40%20x%20%3C%3D%20h%0A%20%20%20%20%20%20%20%20problem%20%3D%20cp.Problem(%0A%20%20%20%20%20%20%20%20%20%20%20%20cp.Minimize((1%20%2F%202)%20*%20cp.quad_form(x%2C%20P)%20%2B%20q%20%40%20x)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Bwalls%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20problem.solve(solver%3Dcp.CLARABEL)%0A%20%20%20%20%20%20%20%20center%20%3D%20np.linalg.solve(P%2C%20-q)%0A%20%20%20%20%20%20%20%20bottom%20%3D%20(1%20%2F%202)%20*%20q%20%40%20center%0A%20%20%20%20%20%20%20%20duals%20%3D%20walls.dual_value%0A%20%20%20%20%20%20%20%20return%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22value%22%3A%20float(problem.value)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22optimum%22%3A%20x.value.tolist()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22center%22%3A%20center.tolist()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22contact%22%3A%20level_radii(problem.value%20-%20bottom)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22duals%22%3A%20duals.tolist()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22active%22%3A%20(duals%20%3E%201e-6).tolist()%2C%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20return%20(solve%2C)%0A%0A%0A%40app.cell%0Adef%20solution(q%2C%20solve)%3A%0A%20%20%20%20solution%20%3D%20solve(q)%0A%20%20%20%20return%20(solution%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20solution_summary(mo%2C%20solution)%3A%0A%20%20%20%20_active%20%3D%20%5Bf%22%24g_%7Bi%20%2B%201%7D%24%22%20for%20i%2C%20active%20in%20enumerate(solution%5B%22active%22%5D)%20if%20active%5D%0A%20%20%20%20_held%20%3D%20(%0A%20%20%20%20%20%20%20%20f%22Active%20constraints%3A%20%7B'%2C%20'.join(_active)%7D.%22%0A%20%20%20%20%20%20%20%20if%20_active%0A%20%20%20%20%20%20%20%20else%20%22No%20constraint%20is%20active%2C%20so%20the%20unconstrained%20minimum%20is%20feasible.%22%0A%20%20%20%20)%0A%20%20%20%20_x1%2C%20_x2%20%3D%20solution%5B%22optimum%22%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%20The%20optimal%20value%20is%20**%7Bsolution%5B%22value%22%5D%3A.4f%7D**%20at%0A%20%20%20%20%20%20%20%20%24x%5E%5Cstar%20%3D%20(%7B_x1%3A.3f%7D%2C%20%7B_x2%3A.3f%7D)%24.%20%7B_held%7D%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%20feasible_region(G%2C%20combinations%2C%20h%2C%20np)%3A%0A%20%20%20%20def%20corners_of(G%2C%20h)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Return%20the%20corners%20of%20the%20region%20Gx%20%3C%3D%20h%20in%20counterclockwise%20order.%22%22%22%0A%20%20%20%20%20%20%20%20corners%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20i%2C%20j%20in%20combinations(range(len(h))%2C%202)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20abs(np.linalg.det(G%5B%5Bi%2C%20j%5D%5D))%20%3E%201e-9%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20corner%20%3D%20np.linalg.solve(G%5B%5Bi%2C%20j%5D%5D%2C%20h%5B%5Bi%2C%20j%5D%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20np.all(G%20%40%20corner%20%3C%3D%20h%20%2B%201e-9)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20corners.append(corner)%0A%20%20%20%20%20%20%20%20middle%20%3D%20np.mean(corners%2C%20axis%3D0)%0A%20%20%20%20%20%20%20%20return%20sorted(corners%2C%20key%3Dlambda%20corner%3A%20np.arctan2(*reversed(corner%20-%20middle)))%0A%0A%0A%20%20%20%20region%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22corners%22%3A%20%5Bcorner.tolist()%20for%20corner%20in%20corners_of(G%2C%20h)%5D%2C%0A%20%20%20%20%20%20%20%20%22walls%22%3A%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B(g%20*%20offset%20%2B%20span%20*%20np.array(%5B-g%5B1%5D%2C%20g%5B0%5D%5D)).tolist()%20for%20span%20in%20(-4%2C%204)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20g%2C%20offset%20in%20zip(G%2C%20h)%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(region%2C)%0A%0A%0A%40app.cell%0Adef%20level_curves(bowl%2C%20draw_problem%2C%20region%2C%20solution)%3A%0A%20%20%20%20draw_problem(region%2C%20bowl%2C%20solution)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20plot_reading(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20In%20this%20plot%2C%20the%20shaded%20region%20satisfies%20every%20inequality%2C%20and%20the%20ellipses%20are%0A%20%20%20%20level%20curves%20of%20the%20objective%20around%20the%20bottom%20of%20the%20bowl.%20The%20solution%20is%20the%0A%20%20%20%20point%20where%20the%20smallest%20reachable%20ellipse%20touches%20the%20region.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20exploration_prompt(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**Try%20it.**%20Change%20the%20shape%20of%20%24P%24%20and%20the%20direction%20of%20%24q%24.%20When%20does%20the%0A%20%20%20%20solution%20move%20from%20the%20interior%20to%20a%20constraint%3F%20When%20are%20two%20constraints%0A%20%20%20%20active%20at%20once%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20matrix_summary(P%2C%20mo)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20The%20level%20curves%20above%20were%20generated%20with%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20P%20%3D%20%5Cbegin%7B%7Bbmatrix%7D%7D%0A%20%20%20%20%7BP%5B0%2C%200%5D%3A.01f%7D%20%26%20%7BP%5B0%2C%201%5D%3A.01f%7D%20%5C%5C%0A%20%20%20%20%7BP%5B1%2C%200%5D%3A.01f%7D%20%26%20%7BP%5B1%2C%201%5D%3A.01f%7D%20%5C%5C%0A%20%20%20%20%5Cend%7B%7Bbmatrix%7D%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%20sensitivity_context(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Sensitivity%20to%20the%20direction%20of%20%24q%24%0A%0A%20%20%20%20The%20sweep%20solves%20the%20program%20again%20for%20every%20direction%20of%20the%20linear%20term%2C%0A%20%20%20%20keeping%20%24P%24%20and%20the%20walls%20fixed.%20It%20shows%20how%20the%20optimal%20value%20rises%20as%20%24q%24%0A%20%20%20%20pulls%20the%20bowl%20into%20a%20wall%2C%20and%20which%20walls%20hold%20the%20solution%20along%20the%20way.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sweep(pull%2C%20solve)%3A%0A%20%20%20%20sweep%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%7B%22direction%22%3A%20direction%2C%20**solve(pull(direction))%7D%0A%20%20%20%20%20%20%20%20for%20direction%20in%20range(0%2C%20360%2C%202)%0A%20%20%20%20%5D%0A%20%20%20%20return%20(sweep%2C)%0A%0A%0A%40app.cell%0Adef%20sensitivity_plot(draw_sweep%2C%20pull_direction%2C%20sweep)%3A%0A%20%20%20%20draw_sweep(sweep%2C%20pull_direction.value)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20takeaways(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Key%20ideas%0A%0A%20%20%20%20-%20The%20objective%20is%20a%20bowl%20shaped%20by%20%24P%24%2C%20and%20the%20constraints%20are%20walls.%0A%20%20%20%20-%20The%20solution%20is%20where%20the%20smallest%20reachable%20level%20curve%20touches%20the%20region.%0A%20%20%20%20-%20A%20positive%20dual%20value%20marks%20a%20wall%20that%20holds%20the%20solution.%20It%20is%20the%20rate%20at%0A%20%20%20%20%20%20which%20moving%20that%20wall%20changes%20the%20optimal%20value.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20source(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Adapted%20from%20the%0A%20%20%20%20%5Bquadratic%20program%20notebook%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Flearn%2Fblob%2Fmain%2Foptimization%2F04_quadratic_program.py)%0A%20%20%20%20in%20marimo's%20learn%20repository%2C%20copyright%202026%20marimo%2C%20under%20the%0A%20%20%20%20%5BMIT%20License%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Flearn%2Fblob%2Fmain%2FLICENSE).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20figures(np%2C%20plt)%3A%0A%20%20%20%20from%20matplotlib.patches%20import%20Ellipse%2C%20Polygon%0A%0A%20%20%20%20INK%20%3D%20%22%231b1d22%22%0A%20%20%20%20MUTED%20%3D%20%22%239aa0a8%22%0A%20%20%20%20REGION%20%3D%20%22%23eef0f3%22%0A%20%20%20%20ACCENT%20%3D%20%22%23b33a2e%22%0A%0A%0A%20%20%20%20def%20draw_problem(region%2C%20bowl%2C%20solution)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Draw%20the%20feasible%20region%2C%20the%20level%20curves%2C%20and%20the%20solution.%22%22%22%0A%20%20%20%20%20%20%20%20figure%2C%20axes%20%3D%20plt.subplots(figsize%3D(6%2C%206))%0A%20%20%20%20%20%20%20%20axes.add_patch(Polygon(region%5B%22corners%22%5D%2C%20facecolor%3DREGION%2C%20edgecolor%3D%22none%22))%0A%20%20%20%20%20%20%20%20for%20index%2C%20(start%2C%20end)%20in%20enumerate(region%5B%22walls%22%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20color%20%3D%20ACCENT%20if%20solution%5B%22active%22%5D%5Bindex%5D%20else%20MUTED%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.plot(*zip(start%2C%20end)%2C%20color%3Dcolor%2C%20linewidth%3D1)%0A%20%20%20%20%20%20%20%20for%20radii%20in%20bowl%5B%22levels%22%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.add_patch(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Ellipse(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20solution%5B%22center%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%20*%20radii%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%20*%20radii%5B1%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20angle%3Dbowl%5B%22angle%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fill%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3DMUTED%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D0.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20solution%5B%22contact%22%5D%5B0%5D%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.add_patch(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Ellipse(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20solution%5B%22center%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%20*%20solution%5B%22contact%22%5D%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202%20*%20solution%5B%22contact%22%5D%5B1%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20angle%3Dbowl%5B%22angle%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fill%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3DACCENT%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D1.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20axes.plot(*solution%5B%22center%22%5D%2C%20%22o%22%2C%20markerfacecolor%3D%22white%22%2C%20markeredgecolor%3DINK)%0A%20%20%20%20%20%20%20%20axes.plot(*solution%5B%22optimum%22%5D%2C%20%22o%22%2C%20color%3DACCENT)%0A%20%20%20%20%20%20%20%20away%20%3D%20np.subtract(solution%5B%22optimum%22%5D%2C%20solution%5B%22center%22%5D)%0A%20%20%20%20%20%20%20%20distance%20%3D%20np.linalg.norm(away)%0A%20%20%20%20%20%20%20%20axes.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%24x%5E*%24%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20solution%5B%22optimum%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D14%20*%20away%20%2F%20distance%20if%20distance%20%3E%201e-3%20else%20(10%2C%2010)%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%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20axes.set(xlim%3D(-3%2C%203)%2C%20ylim%3D(-3%2C%203)%2C%20aspect%3D%22equal%22%2C%20xlabel%3D%22%24x_1%24%22%2C%20ylabel%3D%22%24x_2%24%22)%0A%20%20%20%20%20%20%20%20style_axes(axes)%0A%20%20%20%20%20%20%20%20return%20axes%0A%0A%0A%20%20%20%20def%20draw_sweep(sweep%2C%20direction)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Plot%20the%20optimal%20value%20and%20the%20walls%20holding%20the%20optimum%20against%20the%20direction%20of%20q.%22%22%22%0A%20%20%20%20%20%20%20%20figure%2C%20(values%2C%20holding)%20%3D%20plt.subplots(%0A%20%20%20%20%20%20%20%20%20%20%20%202%2C%201%2C%20figsize%3D(7%2C%203.6)%2C%20sharex%3DTrue%2C%20height_ratios%3D(3%2C%201)%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20directions%20%3D%20%5Brow%5B%22direction%22%5D%20for%20row%20in%20sweep%5D%0A%20%20%20%20%20%20%20%20values.plot(directions%2C%20%5Brow%5B%22value%22%5D%20for%20row%20in%20sweep%5D%2C%20color%3DINK%2C%20linewidth%3D1.4)%0A%20%20%20%20%20%20%20%20values.set(ylabel%3D%22Optimal%20value%22)%0A%20%20%20%20%20%20%20%20for%20wall%20in%20range(len(sweep%5B0%5D%5B%22active%22%5D))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20held%20%3D%20%5Brow%5B%22direction%22%5D%20for%20row%20in%20sweep%20if%20row%5B%22active%22%5D%5Bwall%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20holding.scatter(held%2C%20%5Bwall%20%2B%201%5D%20*%20len(held)%2C%20marker%3D%22%7C%22%2C%20color%3DACCENT%2C%20s%3D40)%0A%20%20%20%20%20%20%20%20holding.set(%0A%20%20%20%20%20%20%20%20%20%20%20%20xlim%3D(0%2C%20358)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xticks%3Drange(0%2C%20361%2C%2090)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ylim%3D(0.5%2C%20len(sweep%5B0%5D%5B%22active%22%5D)%20%2B%200.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20yticks%3Drange(1%2C%20len(sweep%5B0%5D%5B%22active%22%5D)%20%2B%201)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20yticklabels%3D%5Bf%22%24g_%7Bwall%20%2B%201%7D%24%22%20for%20wall%20in%20range(len(sweep%5B0%5D%5B%22active%22%5D))%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xlabel%3D%22Direction%20of%20%24q%24%20(degrees)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20for%20axes%20in%20(values%2C%20holding)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.axvline(direction%2C%20color%3DMUTED%2C%20linewidth%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20style_axes(axes)%0A%20%20%20%20%20%20%20%20figure.tight_layout()%0A%20%20%20%20%20%20%20%20return%20figure%0A%0A%0A%20%20%20%20def%20style_axes(axes)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Draw%20light%20axes%20on%20a%20transparent%20background%20that%20keep%20the%20data%20in%20front.%22%22%22%0A%20%20%20%20%20%20%20%20axes.set_facecolor(%22none%22)%0A%20%20%20%20%20%20%20%20axes.figure.patch.set_alpha(0)%0A%20%20%20%20%20%20%20%20for%20side%20in%20(%22top%22%2C%20%22right%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.spines%5Bside%5D.set_visible(False)%0A%20%20%20%20%20%20%20%20for%20side%20in%20(%22left%22%2C%20%22bottom%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20axes.spines%5Bside%5D.set_color(MUTED)%0A%20%20%20%20%20%20%20%20axes.tick_params(colors%3DMUTED%2C%20labelcolor%3DINK)%0A%0A%20%20%20%20return%20draw_problem%2C%20draw_sweep%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
5e5046c7777fca951d72a965ac558aa6