Nonlinear Opt.: Basic concepts 3: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
 
(19 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
== Theory ==
  
−
Theory
+
Nonlinear Optimization problems(NLP) described as a special type of optimization problems, where some of the constraints or the objective function is nonlinear.
−
----
+
In contrast to the Linear Optimization, which solution method is the simplex algorithm, there is no comparable solution method for NLP.  
−
In contrast to the Linear Optimization, which solution method is the simplex algorithm, there is no comparable solution method für Nonlinear Optimization problems.  
+
Instead of the Simplex algorithm there are different solution methods which are specific for a given problem.  
−
Instead of the Simplex algorithm there are different solution methods which are specific for a given problem. But there is no gurantee for an optimal solution.
+
In the field of nonlinear optimization we divide between restricted and non-restricted optimization problems.
 +
While the domain of restricted optimization problems is a subset of <math>\mathbb{R}^n</math> and usually described by a system of equalities and inequalities, the domain of non-restricted optimization problems is the entire range of <math>\mathbb{R}^n</math>.
 +
In the following we will point out some special algorithms, developed for restricted optimization problems with linear or nonlinear constraints.
 +
Convex optimization problems as a special case of restricted optimization problems have a convex objective function and a convex range. Therefore local and global minima coincide.  
  
−
Theory
+
In addition to the nonlinear objective function and at least one nonlinear constraint the result of our nonlinear optimization problem does not have to be the optimal solution.
−
----
+
 
−
In contrast to the Linear Optimization, which solution method is the simplex algorithm, there is no comparable solution method für Nonlinear Optimization problems.  
+
The gereral form of a non linear optimization can be stated as: --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)geNeral
−
Instead of the Simplex algorithm there are different solution methods which are specific for a given  problem. But there is no gurantee for an optimal solution.
+
  
−
The gereral form of a non linear optimization can be stated as:
 
  
 
<math>max~z= f(x_{1},...,x_{n})</math>
 
<math>max~z= f(x_{1},...,x_{n})</math>
 +
  
 
under the constraints that:
 
under the constraints that:
 +
  
 
<math>h_{i}(x_{1},...,x_{n})\leq b_{i}\qquad i=1,...,m</math>
 
<math>h_{i}(x_{1},...,x_{n})\leq b_{i}\qquad i=1,...,m</math>
 +
  
 
and:
 
and:
 +
  
 
<math>x_{j}\geq 0\qquad j=1,...,n</math>
 
<math>x_{j}\geq 0\qquad j=1,...,n</math>
  
−
Durch Umformen der Restriktion
+
 
 +
By transforming the restriction
 +
 
  
 
<math>h_{i}(x_{1},...,x_{n})\leq b_{i}</math>
 
<math>h_{i}(x_{1},...,x_{n})\leq b_{i}</math>
 +
  
 
in
 
in
 +
  
 
<math>h_{i}(x_{1},...,x_{n})-b_{i}\leq 0</math>
 
<math>h_{i}(x_{1},...,x_{n})-b_{i}\leq 0</math>
  
−
und der Benennung dieser Ungleichung mit <math>g_{i}</math>
+
 
 +
and by nominating this inequality with <math>g_{i}</math> you receive the general  form of a NLP:
 +
 
  
 
<math>max~z=f(x_{1},...,x_{n})</math>
 
<math>max~z=f(x_{1},...,x_{n})</math>
  
−
unter der Berücksichtigung der Nebenbedingungen:
+
 
 +
in consideration of the restrictions:
 +
 
  
 
<math>g_{i}(x_{1},...,x_{n})\leq 0\qquad i=1,...,m</math>
 
<math>g_{i}(x_{1},...,x_{n})\leq 0\qquad i=1,...,m</math>
  
  
 +
and:
  
  
−
Example
+
<math>x_j\geq 0\qquad j=1,...,n</math>
  
−
----
 
  
  
 +
== Example ==
  
−
'''Example 1 (Maximization)'''
+
Nowadays “Nonlinear Optimization” is an important technology in applied mathematics, science and engineering.
 +
“Nonlinear Optimization problems” appear in many applications, e.g., shape optimization in engineering, robust portfolio optimization in finance, parameter identification, optimal control,
 +
etc. “Nonlinear Optimization” has emerged as a key technology in modern scientific and industrial applications.
  
 +
=== Example 1: Maximization ===
  
 
<math> f(x)=5x-2x^2</math>
 
<math> f(x)=5x-2x^2</math>
Zeile 54: Zeile 72:
 
<math> \frac{\partial }{\partial x} f(x)=5-4x</math>
 
<math> \frac{\partial }{\partial x} f(x)=5-4x</math>
  
−
<math>\frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow  min            </math>
+
<math>\frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow  min            </math> --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)it has to be -4 and then your min is a max
  
  
−
'''Example 1 (Minimization)'''
+
=== Example 2: Minimization ===
  
  
Zeile 66: Zeile 84:
  
  
−
<math>\frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow max</math>  
+
<math>\frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow max</math> --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)has to be "min"
  
  
 +
=== Example 3: Hessian Matrix ===
  
−
'''Example 3 ( Hessian Matrix)'''
+
a)  
  
 +
<math>F(x_1,x_2)= 88x_1-x_1^2+88x_2-x_2^2</math>
  
−
<math>f(x_1,x_2)= 88x_1-x1^2+88x_2-x_2^2</math>
 
  
−
<math>\begin{pmatrix}
+
<math>\nabla F(x_1)=\begin{pmatrix}
−
88-2x^1\\ 88-2x^2
+
  88-2x_1\\ 88-2x_2
  
−
\end{pmatrix} \rightarrow      Hessian Matrix H(x)=       \begin{pmatrix}
+
\end{pmatrix}
−
-2 & 0 \\ 0
+
</math>
 +
 
 +
<math>Hessian- Matrix H(x)= \begin{pmatrix}
 +
-2 & 0\\ 0
 
  & -2
 
  & -2
−
\end{pmatrix}  </math>
+
\end{pmatrix}</math>
 +
 
 +
<math>\nabla F(x_1)=0=88-2x_1 \rightarrow x_1= 44</math>
 +
 
 +
<math>\nabla F(x_2)=0=88-2x_2 \rightarrow x_2= 44</math>
 +
 
 +
 
 +
b) Determine the relative extrema of the function:
 +
 
 +
<math>F(x,y)=4y^3-6xy^2+3x^2y-6xy</math>
 +
 
 +
Calculate the partial derivations:
 +
 
 +
<math>F_x(x,y)=-6y^2+6xy^2-6y</math>
 +
 
 +
<math>F_y( x, y ) = 12y^2-12xy+6x^2y-6x</math>
 +
 
 +
<math>F_{xx}(x, y)=6y^2</math>
 +
 
 +
<math>F_{yy}(x,y)=24y-12x + 6x^2</math>
 +
 
 +
<math>F_{xy}(x,y)= F_{yx}(x,x)=-12y+12x-6</math>
 +
 
 +
 
 +
We get the equations:
 +
 
 +
<math>0=-6y^2+6xy^2-6y=-6y(y-xy+1)</math>
 +
 
 +
<math>0=12y^2-12xy+6x^2y-6x \rightarrow 0=6y^2-6xy+x^2y-x</math>
 +
 
 +
 
 +
From the first equation we get:  <math>y=0</math> oder <math>0=y-xy+1</math>, also <math>y=\frac{1}{x-1}</math>
 +
 
 +
This result we put in the equation: <math>0=6y^2-6xy+x^2y-x</math> and calculate the missing results --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)We put this result...
 +
If <math>y=0</math> , we get  <math>x=0</math> .
 +
 
 +
If <math>y=\frac{1}{x-1}</math> , we get  <math>2(\frac{1}{x-1})^2- 2x\frac{1}{x-1}+x^2\frac{1}{x-1}-x=0</math> and with the multiplication of
 +
 
 +
<math>(x-1)^2</math> results <math>2-2x(x-1)+x^2(x-1)-x(x-1)^2=0 \rightarrow  x=2\vee x=-1</math>
 +
 
 +
Possible extreme points : <math>(0,0), (2,\frac{1}{x-1})= (2,1), (-1,\frac{1}{x-1})=(-1,-0,5)</math>
 +
 
 +
Sufficient condition: Hessian Matrix
 +
 
 +
<math>\begin{bmatrix}
 +
6y^2 & -12y+12x-6\\-12y+12x-6
 +
& 24y-12x+6x^2
 +
\end{bmatrix}</math>
 +
 
 +
 
 +
For <math>(0,0)</math> we get <math>\begin{bmatrix}
 +
0 &-6 \\ -6
 +
& 0
 +
\end{bmatrix} \rightarrow  Matrix= semidefinit \rightarrow  saddle point  for (0,0)</math> --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)semidefinitE
 +
 
 +
 
 +
For <math>(2,1)</math> we get <math>\begin{bmatrix}
 +
6 & 6\\ 6
 +
& 24
 +
\end{bmatrix} \rightarrow </math> Eigenvalues are positiv <math>\rightarrow </math> i.e at <math>(2,1)</math> is a minimum. --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)positivE
 +
 
 +
 
 +
For <math>(-1,-0.5)</math> we get  <math>
 +
\begin{bmatrix}
 +
\frac{3}{2} & 6\\ 6
 +
& 6
 +
\end{bmatrix}  \rightarrow</math> Eigenvalue  are both positiv and negativ <math>\rightarrow</math> Hessematrix = indefinit  <math>\rightarrow</math> saddle point at <math>(-1,-0,5)</math> --[[Benutzer:Schneids|schneids]] ([[Benutzer Diskussion:Schneids|Diskussion]]) 20:23, 7. Jul. 2013 (CEST)positivE/negativE/indefinitE
 +
 
 +
 
 +
== References ==
 +
Corsten Hans, Corsten Hilde und Sartor Carsten Operations Research [Buch]. - München : Verlag Franz Vahlen GmbH, 2005.
 +
 
 +
Domschke Wolfgang und Drexl Andreas Einführung in Operations Research [Buch]. - Berlin : Springer, 2007.
 +
 
 +
Neumann Klaus und Morlock Martin Operations Research [Buch]. - München : Carl Hanser Verlag, 2002.

Aktuelle Version vom 7. Juli 2013, 20:23 Uhr

Theory

Nonlinear Optimization problems(NLP) described as a special type of optimization problems, where some of the constraints or the objective function is nonlinear. In contrast to the Linear Optimization, which solution method is the simplex algorithm, there is no comparable solution method for NLP. Instead of the Simplex algorithm there are different solution methods which are specific for a given problem. In the field of nonlinear optimization we divide between restricted and non-restricted optimization problems. While the domain of restricted optimization problems is a subset of and usually described by a system of equalities and inequalities, the domain of non-restricted optimization problems is the entire range of . In the following we will point out some special algorithms, developed for restricted optimization problems with linear or nonlinear constraints. Convex optimization problems as a special case of restricted optimization problems have a convex objective function and a convex range. Therefore local and global minima coincide.

In addition to the nonlinear objective function and at least one nonlinear constraint the result of our nonlinear optimization problem does not have to be the optimal solution.

The gereral form of a non linear optimization can be stated as: --schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)geNeral



under the constraints that:


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


and:


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


By transforming the restriction


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


in


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


and by nominating this inequality with you receive the general form of a NLP:



in consideration of the restrictions:


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


and:


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



Example

Nowadays “Nonlinear Optimization” is an important technology in applied mathematics, science and engineering. “Nonlinear Optimization problems” appear in many applications, e.g., shape optimization in engineering, robust portfolio optimization in finance, parameter identification, optimal control, etc. “Nonlinear Optimization” has emerged as a key technology in modern scientific and industrial applications.

Example 1: Maximization

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x)=5x-2x^2


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial }{\partial x} f(x)=5-4x


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow min 

--schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)it has to be -4 and then your min is a max


Example 2: Minimization


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial }{\partial x}f(x)=5+4x


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial^2 }{\partial x^2}f(x)=4>0 \rightarrow max 

--schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)has to be "min"


Example 3: Hessian Matrix

a)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x_1,x_2)= 88x_1-x_1^2+88x_2-x_2^2


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_1)=\begin{pmatrix} 88-2x_1\\ 88-2x_2 \end{pmatrix}


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Hessian- Matrix H(x)= \begin{pmatrix} -2 & 0\\ 0 & -2 \end{pmatrix}


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_1)=0=88-2x_1 \rightarrow x_1= 44


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_2)=0=88-2x_2 \rightarrow x_2= 44


b) Determine the relative extrema of the function:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x,y)=4y^3-6xy^2+3x^2y-6xy


Calculate the partial derivations:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F_x(x,y)=-6y^2+6xy^2-6y


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F_y( x, y ) = 12y^2-12xy+6x^2y-6x


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F_{yy}(x,y)=24y-12x + 6x^2


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F_{xy}(x,y)= F_{yx}(x,x)=-12y+12x-6


We get the equations:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0=-6y^2+6xy^2-6y=-6y(y-xy+1)


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0=12y^2-12xy+6x^2y-6x \rightarrow 0=6y^2-6xy+x^2y-x


From the first equation we get: oder Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0=y-xy+1 , also Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y=\frac{1}{x-1}


This result we put in the equation: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0=6y^2-6xy+x^2y-x 

and calculate the missing results --schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)We put this result...

If , we get .

If Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y=\frac{1}{x-1} 

, we get  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2(\frac{1}{x-1})^2- 2x\frac{1}{x-1}+x^2\frac{1}{x-1}-x=0
and with the multiplication of

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (x-1)^2 

results Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2-2x(x-1)+x^2(x-1)-x(x-1)^2=0 \rightarrow  x=2\vee x=-1


Possible extreme points : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (0,0), (2,\frac{1}{x-1})= (2,1), (-1,\frac{1}{x-1})=(-1,-0,5)


Sufficient condition: Hessian Matrix

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 6y^2 & -12y+12x-6\\-12y+12x-6 & 24y-12x+6x^2 \end{bmatrix}


For we get Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 0 &-6 \\ -6 & 0 \end{bmatrix} \rightarrow Matrix= semidefinit \rightarrow saddle point for (0,0) 

--schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)semidefinitE


For we get Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 6 & 6\\ 6 & 24 \end{bmatrix} \rightarrow 

Eigenvalues are positiv Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow 
i.e at  is a minimum. --schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)positivE


For Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (-1,-0.5) 

we get  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  \begin{bmatrix} \frac{3}{2} & 6\\ 6  & 6 \end{bmatrix}  \rightarrow
Eigenvalue  are both positiv and negativ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
Hessematrix = indefinit  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
saddle point at Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (-1,-0,5)
--schneids (Diskussion) 20:23, 7. Jul. 2013 (CEST)positivE/negativE/indefinitE


References

Corsten Hans, Corsten Hilde und Sartor Carsten Operations Research [Buch]. - München : Verlag Franz Vahlen GmbH, 2005.

Domschke Wolfgang und Drexl Andreas Einführung in Operations Research [Buch]. - Berlin : Springer, 2007.

Neumann Klaus und Morlock Martin Operations Research [Buch]. - München : Carl Hanser Verlag, 2002.

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Nonlinear_Opt.:_Basic_concepts_3&oldid=6741“