0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ did you appreciate my answer? $\endgroup$ – LinAlg Oct 30 '18 at 12:54
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Quick question, in the example I gave, how did the authors get the dual feasibility? The $\textbf{wA}$ makes sense but I don't know where the other variables came from. $\endgroup$ – Tomás Palamás Oct 30 '18 at 15:23
  • $\begingroup$ @TomásPalamás $v$ comes from the nonnegativity constraint. In my initial answer you would get $c + A^T w \geq 0$, with my updated answer you get $c+A^T w - v = 0$ with $v \geq 0$ $\endgroup$ – LinAlg Oct 30 '18 at 16:01
  • $\begingroup$ Got it, thanks! $\endgroup$ – Tomás Palamás Oct 30 '18 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.