Nonlinear Opt.: Basic concepts 3
Inhaltsverzeichnis
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.
