Dual Problem & KKT

I have written a note with respect to SVM. Unfortunately , I was not familiar with convex optimization at that time .Now ,it's time to fix it up .
http://www.reibang.com/p/8fd28df734a0

Convex Set

So what is convex set ?
For example ,round and square are convex set .Because all direction of these figure is not concave .So the definition of the convex set is :
Take two points in this set randomly ,if the line segment between two points inside this set ,we call this set is convex set .
Mathematical language description :
$x_1, x_2 \in C,\theta x_1 + (1 - \theta)x_2 \in C$ ,then C is a convex set .

Convex function

For example , $e^x ,-log x$ is a convex function .And convex function have four definition :
1) The dom f is convex set .Chose two points randomly from this function $f$ ,if the line segment is above the graph of f,the function f is convex function .
$f(\theta x + (1-\theta)y) < \theta f(x) + (1- \theta) f(y)$

2) The dom f is convex set , $g(t) = f(x + tv),dom(g)= \{ t|x + tv \in domf \},v \in R^m$ ,if g(t) is convex function ,then function f is convex function .
There is a function with a hight dimension .If we want to distinguish this function is convex or not ,we can cut this function into several low-dimension function ,if these incisions of this pieces are convex function,then the original function is convex too .
3) There is a function f with convex dom f ,and the function f is differentiable,the gradient of f is exist . $f(y) >= f(x) + \nabla f(x)(y-x)$ ,function f is convex .
4) If the dom f is convex ,and satisfy $\nabla ^2 f(x) >= 0$ (Hassain matrix is positive define matrix ),function f is convex .

Dual Function

Now ,we have mention all fundamental knowledge what we need .
There is a problem :
$minf(x) \\s.t \quad f_i(x) <= 0,i = 1...n \\ AX = B$
f(x) is the function we need to optimize ,subject to some inequality and affine function .And f(x) may not be a convex or concave function .If function f not a convex or concave ,it maybe have many minimum or maximum value .
So there is a feasible way that we could transform function f into a convex or concave function .Actually ,the difference between convex and concave is negative sign ,so there is no difference between concave and convex function in this case.
Therefore ,we can consider a method to transform f into concave function .Remember we have a optimal method ,Conjugate gradient descent .conjugate function is a convex function .
$Conjugate \quad Function: f^*(y) = sup_{x \in domf}(y^T x - f(x))$
We can prove it .
Retrospect convex function definition 1.We can use it to prove.
Prove :
Take two points randomly from domf .
Now ,support we have a function g , $g(x) = max \{g_i(x)\},i = 1...n$ ,and $g_i(x)$ is convex function .
$g(\theta x + (1-\theta)y) = max\{g_i(\theta x + (1-\theta)y)\} \\ <= max\{\theta g_i(x) + (1-\theta)g_i(y)\} \\ <= \theta * max\{g_i(x)\} + (1-\theta) * max\{g_i(y)\} \\ = \theta g(x) + (1 - \theta) g(y)$
And x is constant not variable ,so elements inside the 'sup' is affine function .As we know ,affine function must be convex .Support $g_i (y) = y^T - f(x),f^*(y) = g(y)$ ,it's over .Conjugate function is convex .
However ,in this case ,I wouldn't transform f(x) to convex function by conjugate function ,I just explain a proof method by conjugate function .
First ,Lagrange Function : $L(x, \lambda, u) = f(x) + \lambda f_i(x) + u(AX-B)$
Support a new function :
$g(\lambda ,u) = inf_{x \in domf} \{ L(x, \lambda ,u) \}$
Utilize the way we prove conjugate function ,we can prove this function is concave function ,so this function just have one maximum .
We call $g(\lambda ,u)$ is dual function .
Now ,we have an access to transform f into concave .

Dual Problem

Support P* is the optimal solution of the primal problem ,and d is the optimal solution of the dual problem .Obviously ,P* >= d.
Before we go into the detail ,we introduce several concepts .
$minf(x) \\s.t \quad f_i(x) <= 0,i = 1...n \\ AX = B$
The problem we mentioned at the beginning have two constraint .We define :
feasible region : $\{ x|f_i(x) <= 0,AX = B,x \in domf \}$
domain : $\{ x| x \in domf \}$
Now ,we transform the format of the question into Lagrange function .
$minimum L(x, \lambda, u) = f(x) + \lambda f_i(x) + u(AX-B),x \in \{ x|f_i(x) <= 0,AX = B,x \in domf \}, \lambda >= 0 \\ => min_{x}max{\lambda, u}L(x,\lambda, u),\lambda >= 0,x \in feasible \ region$
This format of problem still is equal to primal problem .
Look at dual function : $g(\lambda, u) = inf_{x \in domf}L(x,\lambda, u)$ ,we have two difference .
First ,in primal problem ,the x variable belong to feasible region .And dual function is from domain of the target function .
second ,dual function didn't maximum the parameters $\lambda,u$ ,and it drop another constraint $\lambda >= 0$ .If we lose this constraint ,dual function can be infinity .
For reaching a consensus with original problem ,dual function will take with $\lambda >= 0$ .
Obviously ,Domain is larger than feasible region .Therefore ,the minimum solution which we find in primal problem is greater than or equal to the one we find in dual function .And dual problem didn't maximize the parameters, $P^* >= d$
P * >= d is not the answer what we want ,we have to approach to the optimal solution of the primal problem .So we maximize the optimal solution of the dual function d.We got :
$P^* >= max \ d \\ => P^* >= d^*$
From now on ,dual problem appeared .
Dual Problem :
$max_{\lambda, u} g(\lambda, u) \\ s.t \ \lambda >= 0$
For example ,
$min \ C^T x \\ s.t \ Ax = b,x >= 0$
First ,construct Lagrange function .
$L(x,\lambda, u) = C^T x - \lambda x + u(Ax-b) \\ = -b^T v + (C + A^Tv-\lambda)^T x$
Second ,dual function .
$g(\lambda, u) = inf_{x \in domf}L(x,\lambda, u) = inf -b^Tv + (C + A^Tv - \lambda)^Tx$
If $C + A^Tv - \lambda$ have one element greater than zero and x equal to negative infinity ,then dual problem can reach negative infinity .
If $C + A^Tv - \lambda$ have one element less than zero and x equal to positive infinity ,then dual problem can still reach negative infinity .
Therefore , $C + A^Tv - \lambda$ must be equal to zero . Otherwise ,minimum a negative infinity is nonsensical .
According to theory above ,we can write down the concrete formula of dual problem :
$Dual \ Problem : max_{\lambda ,u} -b^Tv \\ s.t \ C+A^Tv-\lambda = 0 \\ \lambda >= 0$
Now ,we got dual problem .

KKT

P* >= d*,we can tackle the dual problem to approach the primal problem .But that is not we want .We want to get P* instead of d*.So ,under what situation is P* equal to d*?
(Why don't we solve the primal problem directly ?Coz f(x) we not sure is convex or not ,in contrast to dual problem ,dual function is an advantage for us .)
Support d* is equal to P*.And $x^*,\lambda^*, u^*$ is the optimal variable when we get P*.
Primal Problem :
$min_{x}max{\lambda, u}L(x,\lambda, u) \\ \lambda >= 0 \\ x \in feasible \ region$
Apparently , $x \in feasible \ region$ means $x^*$ subject to constraints .So the $P^* == f(x^*)$
Now ,leave the primal Problem alone ,we focus on dual problem .
Notice $x \in domf$ ,so $inf_{x}$ we can utilize gradient to solve this problem .
Then we got our first condition over the KKT:
$\frac{\delta L}{\delta x}_{x = x^*} = 0$
We call Stationary .
That is not enough .
$P^* = f(x^*) <= f(x^*) + \lambda f_i(x^*) + u(Ax-B)$
$\lambda f_i(x^*) = 0$ ,this is complementary slackness.
Addtion of Primal feasible and dual feasible,we got the whole KKT condition .
$KKT = \left\{ \begin{aligned} f_i(x^*) <= 0 \quad primal \ feasible \\ Ax = B \quad primal \ feasible\\ \lambda >= 0 \quad dual \ feasible \\ \frac{\delta L}{\delta x}_{x = x^*} = 0 \quad stationary \\ \lambda_i f_i(x) = 0 \quad complementary \ slackness \end{aligned} \right.$
From now on ,we have derived KKT.However ,it's a necessary condition .
When the f(x) is convex ,KKT condition is sufficient and necessary condition .
Prove :
Support $f(x)$ is convex ,and $x^*,\lambda^*,u^*$ satisfy KKT,prove the $d^* = P^*$ .
$g(\lambda^*, u^*) = inf_{x \in domf}L(x, \lambda^*, u^*) \\ = L(x^*, \lambda^*, u^*) \quad (stationary) \\ = f(x^*) + \sum_i \lambda^*_i f_i(x) + u^*(Ax-B) \\ = f(x^*) \quad (complementary \ slackness)$
If f(x) is convex ,then KKT condition is sufficient and necessary.

SVM

The target function is $\frac{1}{2} w^2$ ,obviously it's convex .So we can use KKT directly .

Slater Condition

For a convex problem :

If there exists a

x \in X, domf

,then P* = d*.KKT condition must be necessary ,so we could use KKT .

Weak Slater Condition

For a convex problem ,If the inequality is affine (Ax <= B),then P* = d*,we still can use KKT .SVM satisfy the weak salter condition ,so P* = d* and KKT is no problem .
Note Slater condition work for convex problem .If primal problem not convex ,we cannot use Slater.

Conclusion

At first ,we mentioned a primal problem .It may not be a convex or concave problem .So we can transform the problem into dual problem by dual function .Then we got P* >= d*.
As the result of the convenience of the dual problem ,we want to solve dual problem but primal problem .When P* = d*? Then we introduce the KKT and Slater condition .
KKT focus on optimal solution .Slater Condition focus on P* is equal to d* or not .But to some extend ,these two parties are connected .
If a problem satisfy Salter Condition ,optimal solution satisfy KKT condition because of the necessary of KKT .
If KKT are necessary and sufficient for a problem ,then P* = d*.But it may not satisfy Slater Condition .Because its f(x) < 0 or affine inequality may not exist .
So Inverse Slater Condition is not true.