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

Version vom 1. Juli 2013, 16:21 Uhr

Nonlinear Optimaziation: Basic Concepts

Theory

A nonlinear problem also so called NLP, is similar to a linear program but it is created by the objective function, general constraints and variable bounds. The significant difference from a NLP to a LP is that NLP includes minimum one nonlinear function.

First we define what an optimal solution is. The function which is supposed to be minimized or maximized is (${\displaystyle )f(x),forx\epsilon \mathbb {R} ^{n}(}$) called the objective function. x* is an local minimum, if:

(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): )x^*\epsilon\,\mathbb{R}^n,\varepsilon > 0 f(x^*)\leq f(x)\, for\,all\,x\, \epsilon A (x^*; \varepsilon)( )

And the global minimum, if:

(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): )f(x^*)\leq f(x)\, for\, all\, x\, \epsilon \, \mathbb{R}^n\ ( )

Maximum is vice versa.

The problem can be stated simply as:

(${\displaystyle )x\,\epsilon \,X\,maxf(x)\,to\,maximize\,some\,variable\,such\,as\,product\,throughput\,x\,\epsilon \,X\,minf(x)\,to\,minimize\,a\,cost\,function\,where(}$)

(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): )f=R^n \rightarrow R\ x\, \epsilon\, R^n( )

subject to:

(${\displaystyle )h_{i}(x)=0,\,i\,\epsilon \,I\,=1,...,p(}$)

(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): ) g_j(x)\,\leq \,0,\,j\,\epsilon \,J\,= 1,...,m( )

Example

The following set of NLP are genaral subroutines:

NLPCG Conjugate Gradient Method

NLPDD Double Dogleg Method

NLPNMS Nelder-Mead Simplex Method

NLPNRA Newton-Raphson Method

NLPNRR Newton-Raphson Ridge Method

NLPQN (Dual) Quasi-Newton Method

NLPQUA Quadratic Optimization Method

NLPTR Trust-Region Method

The following subroutines are provided for solving nonlinear least-squares problems:

NLPLM Levenberg-Marquardt Least-Squares Method

NLPHQN Hybrid Quasi-Newton Least-Squares Methods

Example 1:

Simple NLP maximization

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

First derivative:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f'(x)= 3-3x^2 \Rightarrow 3-3x^2=0 \Rightarrow x_1 = +1, \, x_2= -1

Second derivative:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f''(x)= -6 \Rightarrow -6< 0 \Rightarrow max (local maximum)

Example 2:

NLP Gradient Method

First we need to find the gradient:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x,y,z)= 6x^2 +2y^2+2z^2 \rightarrow \triangledown_f (6x^2 +2y+2z)=\left \{ 6x,\, 2y,\, 2z \right \}

Gradient has to equal 0:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \triangledown f(x)=0 \left \{ 6x,\, 2y,\, 2z \right \}= 0

Now we get the Hesse-Matrix by the derivative once again:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \triangledown^2_f = (6, 2, 2)

Solve for example with Rule of SARRUS:

${\displaystyle a_{1}=2,a_{2}=2,a_{3}=6;a_{1},a_{2},a_{3}>0}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow\, global\, minimum\, at\, (0,0,0)

Sources:

http://ciser.cornell.edu/sasdoc/saspdf/iml/chap11.pdf

http://www.wikipedia.org/nonlinear_programming

http://www.sce.carleton.ca/faculty/chinneck/po/Chapter%2016.pdf

http://www.wolframalpha.com