[Optimization] Duality
1. The Lagrange dual function
1.1 The Lagrangian - (definition)
An optimization problem in the standard form
\[\text{minimize} \;\; f_0(x) \\ \text{subject to} \;\; f_i(x) \leq 0 \;\; i = 1, 2, ..., m \\ h_i(x) = 0, \;\; i = 1, ..., p, \\ \text{with variable} x \in R^n\]Lagrangian $L : \textbf{R}^n \times \textbf{R}^m \times \textbf{R}^p \rightarrow \textbf{R}$ associated with the this problem
\[L(x, \lambda, v) = f_o(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=0}^pv_i h_i(x) \\ \textbf{dom} L = D \times \textbf{R}^m \times \textbf{R}^n\]- Lagrangian multiplier associated with the $i$ th inequality constraint $f_i(x) \leq 0$ : $\lambda_i$
- Lagrangian multiplier associated with the $i$ th equality constraint $h_i(x) = 0$ : $v_i$
- dual variables(or Lagrange multiplier vector associated with the problem) : $\lambda, v$
1.2 The Larrange dual function - (definition)
Largrane dual function(or dual function) $g : \textbf{R}^m \times \textbf{R}^p \rightarrow \textbf{R}$ : the minimum value of the Largrangian over $x$
\[g(\lambda, v) = inf_{x \in D} L(x, \lambda, v) = inf_{x \in D} (f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i = 1}^p v_i h_i(x)) \\ \text{for} \; \lambda \in R^m, v \in R^p\]1.3 Lower bounds on optimal value - (theorem)
For any $\lambda \geq 0$ and any $v$,
\[g(\lambda, v) \leq p*\]- Dual feasible : $\text{a pair} \;(\lambda, v) \; \text{with} \;\lambda \geq 0 \; \text{and} \; (\lambda, v) \in \textbf{dom} g$
1.4 Linear aprroximation interpretation
1.5 Examples
Examples for which we can derive an analytical expression for the Lagrange dual function
Least-square solution of linear equations
Standard form LP
LP in standard form
\[\text{minimize} \; c^Tx \\ \text{subject to} \; Ax = b \\ x \geq 0\]Lagrangian
\[L(x, \lambda, v) = c^Tx + \sum_{i=0}^n \lambda_i(-x_i) + v^T(Ax - b) \\ = c^Tx - \lambda^Tx + v^T(Ax - b) \\ = c^Tx - \lambda^Tx + v^TAx - v^Tb \\ = - b^Tv + (c + A^Tv - \lambda)^Tx\]Lagrange dual function
\[g(\lambda, v) = inf_x L(x, \lambda, v) = -b^Tv + inf_x(c + A^Tv - \lambda)^Tx = \begin{cases} -b^Tv & c + A^Tv - \lambda = 0 \\ -\infty & \text{otherwise} \end{cases}\]Two-way partitioning problem
1.6 The Lagrange dual function and conjugate functions - (theorem)
An optimization problem with linear inequality and equality constraints
\[\text{minimize} f_0(x) \\ \text{subject to} \; Ax \leq b \\ \;\;\;\;Cx = d\]Using the conjegate of f_0 we can write the dual function for the problem as
\[g(\lambda, v) = inf_x(f_0(x) + \lambda^T(Ax - b) + v^T(Cx - d)) \\ = -b^T\lambda - d^Tv + inf_x(f_0(x) + (A^T\lambda + C^Tv)^Tx) \\ = -b^T\lambda - d^Tv - f_0*(-A^T\lambda - C^Tv) \\ \textbf{dom}g = \{(\lambda, v) | -A^T\lambda - C^Tv \in f_0*\}\]Equality constrained norm minimization
Entropy minimization
Minimum volume covering ellipsoid
2. The Lagrange dual problem
What is the best lower bound that depend on some parameters $\lambda, v$?
Lagrange dual problem associated with the optimization problem
\[\text{maximize} \; g(\lambda, v) \\ \text{subject to} \; \lambda \geq 0\]- Primal problem : the origin problem - optimization problem
- Dual feasible : a pair $(\lambda, v) \; \text{with} \lambda \geq 0, \text{and} \; g(\lambda, v) > -\infty$
- Dual optimal(or optimal Lagrange multipliers) : optimal for the Lagrange dual problem $(\lambda, v)$
Whether or not the primal problem is convex, the largrange dual problem is a convex optimization problem, since the objective to be maximized is concave and the constraint is convex.
2.1 Making dual constraints explicit
Lagrange dual of standard form LP
Lagrange dual of inequality form LP
\[\text{minimize}\; c^Tx \\ \text{subject to}\; Ax \leq b\]The Lagrange
\[L(x, \lambda, v) = c^Tx + \lambda^T(Ax - b) = -b^T\lambda + (c + A^T\lambda)^Tx\]The dual function
\[g(\lambda, v) = inf_x(-b^T\lambda + (c + A^T\lambda)x) = \begin{cases} -b^T\lambda & c + A^T\lambda = 0 \\ -\infty & \text{otherwise} \end{cases}\]The Largrane dual problem
\[\text{maximize}\; -b^T\lambda \\ \text{subject to}\; A^T\lambda + c = 0 \\ \lambda \geq 0\]2.2 Week duality
\[d* \leq p*\]- The optimal value of the Lagrange dual problem : $d*$
- The best lower bound that can be obtained from the Lagrange dual function : $p*$
- The optimal duality gap of the origin main problem : $p* - d*$
The bound can sometimes be used to find a lower bound on the optimal value of a problem that is difficult to solve, since the dual problem is always convex, and in the many cases can be solved efficiently, to find $d*$
2.3 String duality and Slater’s constraint qualification
\[d* = p*\]- Strong duality holds := the equality holds
This means that the best bound that can be obtained from the Lagrange dual function is tight. (이것은 라그랑주 이중 함수에서 얻을 수 있는 가장 좋은 하한값이 엄밀하게 일치한다는 것을 의미합니다.)
- Constraint qualification : conditions which strong duality holds
Slater’s condition : there exists an $x \in \textbf{relint} D$ such that
\[f_i(x) < 0, \;\;\; i = 1, ..., m, Ax = b.\]Slater’s theorem : strong duality holds if Slater’s condition holds(and the problem is convex).
Reference
Stephen Boyd - Convex Optimization