How to find optimality conditions for a linear program with constraints $Ax \le b$?

Question

I have a feasible point $\hat{x}$ for the problem $$\min c^Tx \quad \text{subject to} \ Ax \le b$$ and I would like to determine if $\hat{x}$ is optimal. The KKT conditions seem to provide no information. Indeed, the Lagrangian is $$L(x, \lambda) = c^Tx - \lambda^T(b-Ax)$$ so the KKT conditions are: $x^*$ is optimal if there exists a $\lambda^*$ such that \begin{align} A^T\lambda^* &= c \\ \lambda^* &\ge 0. \end{align} Thus, given a $\hat x$, the KKT conditions do not help us classify it as optimal or suboptimal (unless of course the KKT conditions are infeasible, in which case there is no optimal solution).

Answer 1

KKT Conditions

For an optimization problem: $\min f\left(\mathbf{x}\right)$ subject to $g_{i}\left(\mathbf{x}\right)\leq 0\phantom{x}\forall\phantom{x}i\in\{1,...,n\}$. The necessary condition for a local optima is:

$$ \begin{aligned} \mathbf{0}&= \nabla_{\mathbf{x}}\left[f(\mathbf{x})+\sum_{i=1}^{m}\lambda_{i}\cdot g_{i}(\mathbf{x})\right] \\\\ 0&\geq g_{i}(\mathbf{x})\phantom{x}\forall\phantom{x}i\in\{1,...,n\} \\\\ 0&\leq \lambda_{i}\phantom{x}\forall\phantom{x}i\in\{1,...,n\} \\\\ 0&= \lambda_{i}\cdot g_{i}(\mathbf{x})\phantom{x}\forall\phantom{x}i\in\{1,...,n\} \end{aligned} $$

The conditions are stationarity, primal feasibility, dual feasibility, and complementary slackness respectively. Together, they are conditions for a point to be a stationary point in the feasible region.

KKT Conditions In Linear Programming

In linear problems, the gradients are not functions of $\mathbf{x}$. Therefore, we don't need a test point to check the existence of optima. An optima exists in the feasible region if and only if the stationarity and dual feasibility conditions are met:

$$ \exists\lambda\geq \mathbf{0}:\mathbf{A}^{\top}\mathbf{\lambda}=\mathbf{c} $$

After obtaining $\mathbf{\lambda}$, to check if a point $\hat{\mathbf{x}}$ is an optima and is in the feasible region, use the remaining KKT conditions: primal feasibility and complementary slackness:

$$ \mathbf{A}\hat{\mathbf{x}} \leq \mathbf{b} \phantom{x} \text{and} \phantom{x} \text{diag}(\mathbf{\lambda})\left(\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\right)=\mathbf{0} $$

TLDR

You have only used two out of four KKT conditions. Those two conditions are for proving that an optima exists in the feasible region.