115_KKT Conditions for LP Problem

I plan to write and solve the KKT optimality conditions for an LP problem. The LP problem defined in standard form is as follows.

 

 

The above equations, when expressed in the form of a Lagrangian function, are as follows.

 

 

Where ${\bf{v}}$ and ${\bf{\lambda }}$ are the Lagrange multipliers for the constraints. The KKT necessary conditions are as follows.

 

 

The above equations can be solved for ${\bf{x}}$, ${\bf{v}}$, and ${\bf{\lambda }}$. They can be partitioned using vectors and matrices as follows.

 

 

The above equation expresses the basic variables ${{\bf{x}}_{\bf{b}}}$ as functions of the nonbasic variables ${{\bf{x}}_{\bf{N}}}$. This is referred to as the general solution to ${\bf{Ax}} = {\bf{b}}$. If ${{\bf{x}}_{\bf{N}}}$ is set to zero, then ${{\bf{x}}_{\bf{b}}}$ is as follows.

 

 

When the first of the KKT necessary conditions is expressed in its partitioned form, it appears as follows.

 

 

Where ${{\bf{x}}_{\bf{B}}} \ne 0$ and ${{\bf{\lambda }}_{\bf{B}}} \ne 0$, the following condition is satisfied.

 

 

From the second of the KKT necesary condition, the following can be derived.

 

 

The cost function can be expressed as a function of basic and nonbasic variables as follows.

 

 

By rearranging the previous equations, the following cost function can be obtained.

 

 

The above equation expresses the cost function using only nonbasic variables. The coefficients of the nonbasic variables are the reduced cost coefficients. At the optimal point, these values are nonnegative, which is used as a condition to recognize the optimal solution in the simplex method. Additionally, since ${{\bf{x}}_{\bf{N}}}$ are nonbasic variables, they are zero. Therefore, the optimal cost function is as follows.