Machine Learning

Appendix C

Hints on Constrained Optimization

Chapter Outline

C.1 Equality Constraints 1023

C.2 Inequality Constraints 1025

The Karush-Kuhn-Tucker (KKT) conditions 1025

Min-Max duality 1026

Saddle point condition 1027

Lagrangian duality 1027

Convex programming 1028

Wolfe dual representation 1029

References 1029

C.1 Equality Constraints

We will first focus on linear equality constraints and then generalize to the nonlinear case. The problem is cast as

$\begin{array}{ll}\hfill \underset{\mathit{\theta }}{min}& J(\mathit{\theta }),\hfill \\ \hfill \text{s.t.}& A\mathit{\theta }=\mathit{b},\hfill \end{array}$

where A is an m × l matrix and b, θ are m × 1 and l × 1 vectors, respectively. It is assumed that the cost function J(θ) is twice continuously differentiable and it is, in general, ...