Nonlinear Opt.: KKT- theorem 3: Unterschied zwischen den Versionen

Aktuelle Version vom 25. Juni 2013, 14:11 Uhr

Introduction:

The Karush–Kuhn–Tucker (KKT) conditions are first order necessary conditions for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. In general, many optimization algorithms can be interpreted as methods for numerically solving the KKT system of equations.

Optimization problem:

Given is the following optimization problem:

${\displaystyle \min z=f(x_{1},...,x_{n})}$

or

${\displaystyle \max z=f(x_{1},...,x_{n})}$

With these constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): h_{i}(x_{1},...,x_{n})\leq 0,i=1,...,m

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\geq 0, j=1,...,n

${\displaystyle f(x_{1},...,x_{n}),h_{i}(x_{1},...,x_{n})}$ are continuously differentiable.

1. Start with the Lagrangian function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x,\lambda)= f(x_{1},...,x_{n})+ \sum _{i=1}^{m}\lambda _{i}*h_{i}(x_{1},...,x_{n})

(Minimum-problem)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x,\lambda)= f(x_{1},...,x_{n})- \sum _{i=1}^{m}\lambda _{i}*h_{i}(x_{1},...,x_{n})
(Maximum-problem)

2. Continue with the Karush- Kuhn- Tucker conditions

I. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{j}}= \frac{\partial f}{\partial x_{j}}(\hat{\underline{x}})+ \sum_{i=1}^{m}\hat{\lambda_{i} }* \frac{\partial h_{i}}{\partial x_{j}}(\hat{\underline{x}})\geq 0 , j=1,..,n (Minimum-problem)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{j}}= \frac{\partial f}{\partial x_{j}}(\hat{\underline{x}})- \sum_{i=1}^{m}\hat{\lambda_{i} }* \frac{\partial h_{i}}{\partial x_{j}}(\hat{\underline{x}})\geq 0

, j=1,..,n (Maximum-problem)

II. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat{\underline{x}}*\frac{\partial L}{\partial x_{j}}= \hat{\underline{x}} *[\frac{\partial f(x)}{\partial}+\sum_{i=1}^{m}\hat{\lambda_{i} }* \frac{\partial h_{i}}{\partial x_{j}}(\hat{\underline{x}})]=0 , j=1,..,n (Minimum-problem)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat{\underline{x}}*\frac{\partial L}{\partial x_{j}}= \hat{\underline{x}} *[\frac{\partial f(x)}{\partial}-\sum_{i=1}^{m}\hat{\lambda_{i} }* \frac{\partial h_{i}}{\partial x_{j}}(\hat{\underline{x}})]=0

, j=1,..,n (Maximum-problem)

III. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_{i}}= h_{i}(\hat{x}))\leq 0 , i=1,…,m

IV. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat{\lambda_{i} }\frac{\partial L}{\partial \lambda_{i}}=\hat{\lambda_{i} }*h_{i}(\hat{x})=0 , i=1,…,m

V. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat{\underline{x}}\geq 0

VI. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat{\underline{\lambda}}\geq 0

${\displaystyle {\hat {x}}\varepsilon \mathbb {R} _{+}^{n}}$ is a global minimum/maximum of ${\displaystyle L(x,{\hat {\lambda }})}$ for a fixed ${\displaystyle {\hat {\lambda }}}$

${\displaystyle {\hat {\lambda }}\varepsilon \mathbb {R} _{+}^{m}}$ is a global maximum/minimum of ${\displaystyle L({\hat {x}},\lambda )}$ for a fixed ${\displaystyle {\hat {x}}}$

A vector ${\displaystyle {\hat {\underline {x}}},{\hat {\underline {\lambda }}}}$ in ${\displaystyle \mathbb {R} _{+}^{n+m}}$ is called saddle point of Lagrangian function ${\displaystyle L(x,\lambda )}$, if it holds for all ${\displaystyle x\varepsilon \mathbb {R} _{+}^{n}}$ and ${\displaystyle \lambda \varepsilon \mathbb {R} _{+}^{m}}$:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(\hat{x},\lambda )\leq L(\hat{x},\hat{\lambda} )\leq L(x,\hat{\lambda} )

If ${\displaystyle {\hat {\underline {x}}},{\hat {\underline {\lambda }}}}$ is a saddle point of ${\displaystyle L(x,\lambda )}$, then ${\displaystyle {\hat {x}}}$ is a minimizer/maximizer of the NLP.

If the function ${\displaystyle f(x_{1},...,x_{n})}$ is concave and all ${\displaystyle h_{i}(x_{1},...,x_{n})}$ are convex and the Slater condition (there exists a ${\displaystyle x\epsilon \mathbb {R} _{+}^{n}}$ with ${\displaystyle g(x)<0}$) is satisfied, then the KKT-conditions are necessary and sufficient for an optimal solution.

Example

Given is the following optimization problem:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \max f(x_{1},x_{2})=8*x_{1}-x_{1}^2+4*x_{2}-x_{2}^2

Under the restrictions Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g(x_{1}, x_{1})=x_{1}+x_{2}\leq 2

and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  x_{1},x_{2}\geq 0

Start with the Lagrangian-function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x,\lambda)=8*x_{1}-x_{1}^2+4*x_{2}-x_{2}^2 - \lambda*(x_{1}+x_{2}-2)

Continue with the KKT conditions:

I.(a) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{1}}= 8-2*x_{1}-\lambda\leq 0

I.(b) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{2}}= 4-2*x_{2}-\lambda\leq 0

II.(a) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}*\frac{\partial L}{\partial x_{1}}=x_{1}*(8-2*x_{1}-\lambda)=0

II.(b) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}*\frac{\partial L}{\partial x_{2}}=x_{2}*(4-2*x_{2}-\lambda)=0

III. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda }= x_{1}+x_{2}-2 \leq 0

IV. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda *\frac{\partial L}{\partial \lambda }= \lambda *(x_{1}+x_{2}-2) = 0

V. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}, x_{2}\geq 0

VI. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda \geq 0

There are four possible cases for the solution:

(1) ${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}=0}$

(2) ${\displaystyle x_{1}>0}$ and ${\displaystyle x_{2}>0}$

(3) ${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}>0}$

(4) ${\displaystyle x_{1}>0}$ and ${\displaystyle x_{2}=0}$

- case (1): ${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}=0}$

If ${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}=0}$ then ${\displaystyle \lambda =0}$ because of IV.

This is contradictory to I: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 8-2*0-0\leq 0

- case (2): ${\displaystyle x_{1}>0}$ and ${\displaystyle x_{2}>0}$

Because of II: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}=4-0,5*\lambda

and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  x_{2}=2-0,5*\lambda

a) Because of IV: ${\displaystyle \lambda =0}$,then ${\displaystyle x_{1}=4}$ and ${\displaystyle x_{2}=2}$

This is contradictory to III: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4+2\leq 2

b) Because of IV: ${\displaystyle x_{1}+x_{2}=2}$ ,so Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4-0,5*\lambda+2-0,5*\lambda=2

and so ${\displaystyle \lambda =4}$.

This is contradictory to II: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}=2-0,5*4 ,because ${\displaystyle x_{2}>0}$

- case (3):${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}>0}$

Then Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda \geq 8

because of I.(a) and ${\displaystyle x_{2}=2}$ because of IV.

With II.(b) you get for ${\displaystyle \lambda =0}$. This is contradictory to I.(a)

- case (4): ${\displaystyle x_{1}>0}$ and ${\displaystyle x_{2}=0}$

Then Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda \geq 4

because of I. (b) and ${\displaystyle x_{1}=2}$ because of IV.

With II.(a) you get for ${\displaystyle \lambda =4}$.

If you check now all KKT conditions, you can see that ${\displaystyle x_{1}=2,x_{2}=0}$ and ${\displaystyle \lambda =4}$ fulfill all the conditions.

The function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1},x_{2})=8*x_{1}-x_{1}^2+4*x_{2}-x_{2}^2

is concave (I*) and the Slater conditions is satisfied (II*). 

So the KKT-conditions are necessary and sufficient for an optimal solution.

(I*) A function f(x) is strictly concave if the Hessian matrix is negative definite.

Here: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bigtriangledown f(x)=\begin{bmatrix}8-2*x_{1}\\4-2*x_{2}\end{bmatrix}

and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  G(x)=\begin{bmatrix}-2 &0 \\ 0&-2 \end{bmatrix}
,so 

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det(H(x)-\lambda*I))=\begin{bmatrix}-2-\lambda &0 \\0&-2-\lambda\end{bmatrix}=(2+\lambda )^2=0

So Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda = -2< 0 , id est G(x) is negative definite and consequently f(x) concave.

(II*) The Slater-condition is sufficient, if a Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x=(x_{1},x_{2})\geq 0

exists, so that ${\displaystyle x_{1}+x_{2}<2}$

this is given with ${\displaystyle (0,5/0,5)}$

The optimal solution is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^*=(2,0)

with ${\displaystyle f(2,0)=12}$

Source

S. Boyd, L.Vandenberghe, Convex Optimization, Cambridge: Cambridge University Press, 2004

W. Domschke, A.Drexl, Einführung in Operations Research, 6th edition,2005

W. Domschke, et al., Übungen und Fallbeispiele zum Operations Research, 5th edition,2005