= Dual of a maximum of affine functions
{title2=$\max\{b^Ty:y\geq0,\ \mathbf1^Ty=1,\ \sum_i y_i a_i=0\}$}
Minimizing $\max_i(a_i^Tx+b_i)$ over unrestricted $x$ is a <linear program> after introducing an <epigraph> variable $t$ and inequalities $a_i^Tx+b_i\leq t$. Its <optimization Lagrangian> has finite infimum over $x,t$ exactly when the nonnegative multipliers sum to one and their weighted slopes sum to zero. The displayed <Lagrangian dual problem> maximizes the resulting constant lower bound. It identifies the role of a zero-slope <convex combination> of the affine functions.
Back to article page
