KKT optimality conditions for Max and Min under different constraints

1k Views Asked by At

I've found many papers and seen several posts on here that use notations for the KKT conditions different from the book I am using, this book. The book uses the following:

Given the following, $$\begin{align*} \text{Minimize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{Ax}\geq \textbf{b}\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ The the authors state that the KKT conditions are $$ \begin{align*} &\textbf{Ax}\geq\textbf{b}\:,\:\textbf{x}\geq\textbf{0}\\ &\textbf{wA}+\textbf{v}=\textbf{c}\:,\:\textbf{w,v}\geq\textbf{0}\\ &\textbf{w}(\textbf{Ax}-\textbf{b})=0\:,\:\textbf{vx}=0 \end{align*} $$ where the first, second, and third are called primal feasibility, dual feasibility, and complementary slackness, respectively. I got somewhat lost during the derivation of this. Also, suppose we change the given system to the following ones: $$\begin{align*} \text{Minimize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{Ax}\leq \textbf{b}\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ $$\begin{align*} \text{Maximize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{Ax}\geq \textbf{b}\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ $$\begin{align*} \text{Maximize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{Ax}\leq \textbf{b}\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ $$\begin{align*} \text{Minimize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{A}_1\textbf{x}=\textbf{b}_1\\ &\textbf{A}_2\textbf{x}\geq \textbf{b}_2\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ How would I modify the KKT conditions for these new systems?

1

There are 1 best solutions below

2
On BEST ANSWER

The important step is forming the Lagrangian. Let me give two examples

Example 1 $$\begin{align*} \text{Minimize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{Ax}\leq \textbf{b}\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ The Lagrangian is $L(x,\lambda) = c^Tx + w^T(Ax-b) + v^T(-x)$ with $w \geq 0$. The $+$ since it is minimization ($-$ for maximization), and the parts between parentheses are (always) the $\leq$ sides.

Example 2 $$\begin{align*} \text{Minimize}\:&\textbf{cx}\\ \text{subject to}\:&\textbf{A}_1\textbf{x}=\textbf{b}_1\\ &\textbf{A}_2\textbf{x}\geq \textbf{b}_2\\ &\textbf{x}\geq \textbf{0}\\ \end{align*} $$ The Lagrangian is $L(x,\lambda) = c^Tx + v^T(A_1x-b_1) + w^T(b_2-A_2x)-y^Tx$ with $w\geq0$. Here $v$ does not have to be nonnegative. You would arrive at the same function if you rewrite the equality as two inequalities.

Next step

After forming the Lagrangian you take the derivative with respect to $x$ to get the dual feasibility conditions. The other conditions follow trivially.