Supporting lines
We want to minimize an objective under a constraint. A Lagrange multiplier gives a lower bound on the constrained minimum. Move the multiplier to see how the bound is constructed and when it becomes exact.
Primal problem
minimizef0(x)
subject tof1(x) β€ 0
Dual lower bound
π(x, y) = f0(x) + y f1(x)
g(y) = infx π(x, y), y β₯ 0
The minimization defining g(y) is unconstrained. Every feasible point has f1 β€ 0, so g(y) β€ pβ.
Constraintβcost planex β¦ (fβ(x), fβ(x))
Supporting linet = 0.438 β 0.500u
feasibleinfeasiblesupporting line
Dual functiondrag the red marker to change y
Optimize the multiplierg(y) = y β yΒ²/4
Change the multiplier
Multiplier y
Dual bound g(y)
Primal value pβ
Best dual bound dβ
Current gap pβ β g(y)
Minimizer of π(Β·, y)