Infeasibility certificate from an unbounded Lagrangian dual
ID: infeasibility-certificate-from-an-unbounded-lagrangian-dual
For a maximization problem, every feasible point's finite objective is bounded above by every valid Lagrangian relaxation value. If a sequence of nonnegative multipliers makes those upper bounds tend to minus infinity, no feasible point can exist. Thus a minimization Lagrangian dual problem unbounded below certifies primal infeasibility. Finite dual value alone does not certify primal feasibility.
New to topics? Read the docs here!