Proof of KKT Conditions (sufficient)

p∗=min⁡f0(x⃗)s.t.fi(x⃗)≤0,i=1,…,mhi(x⃗)=0,i=1,…,pp^* = \min f_0(\vec{x}) \\ \text{s.t.} \\ f_i(\vec{x}) \le 0, i = 1, \dots, m \\ h_i(\vec{x}) = 0, i = 1, \dots, p
d∗=max⁡g(λ⃗,ν⃗)s.t.λ⃗≥0d^* = \max g(\vec{\lambda},\vec{\nu}) \\ \text{s.t.} \\ \vec{\lambda} \ge 0

Sufficient Condition:

x~,λ~,ν~\tilde{x}, \tilde{\lambda}, \tilde{\nu} are points that satisfy

  1. ∀i∈[1,m],fi(x~)≤0\forall i \in [1,m], f_i(\tilde{x}) \le 0
  1. ∀i∈[1,p],hi(x~)=0\forall i \in [1,p], h_i(\tilde{x}) = 0
  1. ∀i∈[1,m],λ~i≥0\forall i \in [1,m], \tilde{\lambda}_i \ge 0
  1. ∀i∈[1,m],λ~i⋅fi(x~)=0\forall i \in [1,m], \tilde{\lambda}_i \cdot f_i(\tilde{x}) = 0
  1. ∇f0(x~)+∑λ~i∇fi(x~)+∑ν~i∇hi(x~)=0\nabla f_0(\tilde{x}) + \sum \tilde{\lambda}_i \nabla f_i(\tilde{x}) + \sum \tilde{\nu}_i \nabla h_i(\tilde{x}) = 0

Then:

x~,λ~,ν~\tilde{x}, \tilde{\lambda}, \tilde{\nu} are primal and dual optimum

Proof:

Consider L(x,λ~,ν~)=f0(x)+∑λ~ifi(x)+∑ν~ihi(x)L(x, \tilde{\lambda}, \tilde{\nu}) = f_0(x) + \sum \tilde{\lambda}_i f_i(x) + \sum \tilde{\nu}_i h_i(x) ⇒ its a convex function in xx

If x~\tilde{x} satisfies FOC, then it must be a minimizer

We know

g(λ~,ν~)=min⁡xL(x,λ~,ν~)=min⁡x[f0(x)+∑λ~ifi(x)+∑ν~ihi(x)]=f0(x~)+∑λ~ifi(x)+∑ν~ihi(x)=f0(x~)\begin{split} g(\tilde{\lambda}, \tilde{\nu}) &= \min_{x} L(x, \tilde{\lambda}, \tilde{\nu}) \\ &= \min_{x} [f_0(x) + \sum \tilde{\lambda}_if_i(x) + \sum \tilde{\nu}_i h_i(x)] \\ &= f_0(\tilde{x}) + \sum \tilde{\lambda}_i f_i(x) + \sum \tilde{\nu}_i h_i(x) \\ &= f_0(\tilde{x}) \end{split}

So: