I read an paper on Quadratic Programming:
Paul A. Jensen, Jonathan F. Bard: Operations Research Models and Methods
Nonlinear Programming Methods.S2
Quadratic Programming
Available here: https://www.me.utexas.edu/~jensen/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf
It defines the Quadratic Program as:
$Minimize \;\; f(x)=cx+\frac{1}{2}x^{T}Qx$
$Subject\, to\;\; Ax\leq b\;\; and\;\; x\geq 0$
On page 2 it states that the Karush-Kuhn-Tucker conditions for this are:
(JB.1) $\frac{\partial L}{\partial x_{j}}\geq 0,\; \; j = 1,…,n\; \; \; \; \; \; c+x^{T}Q+\mu A\geq0$
(JB.2) $\frac{\partial L}{\partial \mu_{i}}\leq 0,\; \; i = 1,…,m\; \; \; \; \; \; Ax-b\leq0$
(JB.3) $x_{j}\frac{\partial L}{\partial x_{j}}=0,\; \; j = 1,…,n\; \; \; \; \; \; x^{T}\left ( c^{T}+Qx+A^{T}\mu \right )=0$
(JB.4) $\mu_{i}g_{i}(x)=0,\;\;i=1,…,m \;\;\;\;\;\; \mu\left ( Ax-b \right )=0$
(JB.5) $x_{j}\geq 0,\;\; j=1,…,n \;\;\;\;\;\; x\geq 0$
(JB.6) $\mu_{i}\geq 0,\;\; i=1,…,m \;\;\;\;\;\; \mu\geq 0$
As far as I know the Karush-Kuhn-Tucker (in general, not in the special case of Quadratic Programming) are these:
(KKT.Stationarity) $\triangledown f(x) + \sum_{i=1}^{m} \mu_{i} \triangledown g_{i}(x) + \sum_{j=1}^{l} \lambda_{j} \triangledown h_{j}(x) = 0$
(KKT.PrimalFeasibility) $g_{i}(x)\leq 0,\;\; i=1,…,m \;\; and \;\; h_{j}(x)= 0,\;\; j=1,…,n$
(KKT.DualFeasibility) $\mu_{i}\geq 0,\;\; i=1,…,m$
(KKT.ComplementarySlackness) $\sum_{i=1}^{m} \mu_{i}g_{i}(x)=0$
I see how the following are related:
(JB.2) and (JB.5) <=> (KKT.PrimalFeasibility) with $g(x)=\begin{bmatrix} A & 0 \\ 0 & -I \end{bmatrix} x – \begin{bmatrix} b \\ 0 \end{bmatrix}$ and $h(x)=0$
(JB.6) <=> (KKT.DualFeasibility)
(JB.4) <=> (KKT.ComplementarySlackness)
However, I do not understand the connection between:
(JB.1), (JB.3) on the one hand and (KKT.Stationarity) on the other hand
Could you please explain me, how these follow from each other?
Best Answer
The authors didn't mention the multipliers (say $\lambda \ge 0$) for $x \ge $ 0 explicitly. Usually, you would have:
$c+x^{T}Q+\mu A - \lambda = 0$ and $\lambda \ge 0$ and $x_j \lambda_j = 0$
but this indeed implies
$c+x^{T}Q+\mu A \ge 0$ and $x^T (c+x^{T}Q+\mu A) = 0$
when you eliminate $\lambda = c+x^{T}Q+\mu A$.