106_KKT Condition

In this post, I intend to explain the "Karush-Kuhn-Tucker (KKT) Optimality Conditions," widely used in optimization theory. The KKT conditions can be applied to optimization problems with both equality and inequality constraints. They can be considered a more generalized form of the Lagrangian function described in the previous post(105_Lagrange Multiplier Theorem).

 

 

In this problem, there are both equality and inequality constraints. If Lagrange multipliers ${{\bf{v}}^{\bf{*}}}$ ($p$-vector) and ${{\bf{u}}^{\bf{*}}}$ ($m$-vector) exist, then the Lagrangian function is stationary at the point ${{\bf{x}}^{\bf{*}}}$ with respect to ${x_j}$, ${v_i}$, ${u_j}$, and ${s_j}$.

 

Represented as a Lagrangian function is as follows.

 

 

The gradient condition is

 

 

Feasibility and swiching condition check

 

 

Solve a simple example using the KKT conditions. The definition of the problem is as follows.

 

 

The two inequality constraints, expressed in their general form, are as follows.

 

 

Through the Lagrange function, that problem can be represented as follows.

 

 

Where ${u_1}$ and ${u_2}$ are the Lagrange multipliers, ${s_1}$ and ${s_2}$ are the slack variables for the ${g_1}$ and ${g_2}$. The KKT conditions is represented as follows.

 

 

Due to the switching condition of ${u_1}{s_1}, {u_2}{s_2}$, the KKT conditions allow for consideration of four different scenarios, and each case must be considered.

 

1. ${u_1} = 0,{u_2} = 0$

In this case, two solutions can be obtained $x=b$ and $x=c$, and all constraints are satisfied at these points.

 

 

Therefore, all KKT conditions are satisfied, and the sufficient condition can be varified by calculating the curvature of the cost function at these two points.

 

 

Since $b$ is less than $c$, it is negative. Therefore, it dose not satisfy the sufficient condition for a local minimum, indicating it corresponds to a local maximum.

 

2. ${u_1} = 0,{s_2} = 0$

In this case, ${g_2}$ is active, and since ${s_2}=0, x=d$. Therefore, it is as follows.

 

 

In this case, since ${u_2}<0$, the KKT necessary condition is violated. Therefore, ${x=d}$ cannot be a minimum or maximum point.

 

3. ${s_1} = 0,{u_2} = 0$

If ${s_1} = 0$, then $x = a$. Thus, it can be represented as follows.

 

 

At $x = a$, ${u_1}$ takes a positive value, and all KKT conditions are satisfied. Therefore, $x=a$ is a local minimum point.

 

4. ${s_1} = 0,{s_2} = 0$

In this case, both constraints are active, which means $x$ cannot be both $a$ and $d$ at the same time, making it unsolvable.