Linear programming duality

Linear programming duality pairs an optimization problem, the primal, with a dual problem whose feasible solutions bound the primal optimum. Under standard conditions, their optimal values are equal.

Primal problem: The original optimization problem in a primal–dual pair. Its feasible solutions provide the quantity the dual problem bounds.
Linear inequality: A relation between linear expressions using an order symbol such as ≤ or ≥. Each primal inequality contributes a dual variable and affects its sign.
Shadow price: The marginal change in an optimal objective value when a constraint’s right-hand side changes. An optimal dual variable often measures the value of relaxing its associated resource constraint.
Integer programming: Optimization in which some or all decision variables must take integer values. Its linear relaxation has a dual, but integrality can create a gap between primal and dual optima.
Dual problem: The companion optimization problem formed from a primal problem’s objective and constraints. Its feasible objective values bound the primal optimum.
Feasible region: The set of points satisfying all constraints of an optimization problem. Primal and dual feasibility define the solutions compared by duality.
Optimality certificate: A verifiable witness that a proposed solution is optimal for a specified problem. Matching feasible primal and dual values certifies optimality.
Lagrangian duality: A framework that forms a dual optimization problem by relaxing constraints into a Lagrangian. It generalizes the multiplier-based viewpoint beyond linear programs.
Weak duality: The principle that every feasible primal and dual pair of solutions gives ordered objective values. It supplies a bound even when neither problem has been solved.
Lagrange multiplier: A variable weighting a constraint in an optimization formulation or its Lagrangian. Dual variables act as multipliers on primal constraints.

Linked from 14 pages