Lagrange duality

From Wikipedia, the free encyclopedia

Given a convex optimization problem in standard form

minimize f0(x) subject to

f_i(x) \leq 0, i \in \left \{1,\dots,m \right \}
hi(x) = 0, i \in \left \{1,\dots,p \right \}

with the domain \mathcal{D} \subset \mathbb{R}^n having non-empty interior, the Lagrangian function L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} is defined as

L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x).

The vectors λ and ν are called the dual variables or Lagrange multiplier vectors associated with the problem. The Lagrange dual function g:\mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} is defined as

g(\lambda,\nu) = \inf_{x\in\mathcal{D}} L(x,\lambda,\nu) = \inf_{x\in\mathcal{D}} \left ( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right )

The dual function g is concave, even when the initial problem is not convex. The dual function yields lower bounds on the optimal value p * of the initial problem; for any \lambda \geq 0 and any ν we have g(\lambda,\nu) \leq p^*. If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality, i.e. d^* = \max g(\lambda,\nu) = \inf f_0 = p^*(x).

Retrieved from "http://en.wikipedia.org../../../l/a/g/Lagrange_duality.html"