Nonlinear Opt.: Examples and Modeling 3

Theory

Minimize nonlinear functions subject to constraints. Nonlinear programming (NP) involves minimizing or maximining a nonlinear objective function subject to bound constraints, linear constraints, or nonlinear constraints, where the constraints can be inequalities or equalities. Unconstrained nonlinear programming is the mathematical problem of finding a vector x that is a local minimum to the nonlinear scalar function f(x). Unconstrained means that there are no restrictions placed on the range of x.

${\underset {x}{min}}f(x)$

Nonlinear Optimization

The nonlinear Optimization is differently structured. There is no single solution method. The function $f$ is usually called the objective function or criterion function . Each of the constraints Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g\leq n

is called an inequality constraint and each of the constraints $h=n$ is called an equality constraint.

General problems of nonlinear Optimization problems:

- a nonlinear objective function and/or

- at least one nonlinear constraint

Example:

- nonlinear objective function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max f(x)=-x_{1}^{3}-5x_{2}^{2}+\frac{5}{2}x^{_{3}}

- nonlinear constraint: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y(x)= x_1 + x_2 + 5 \leq 0

Compared to the Linear Optimization there is no comparable solution method of NLP. Instead of the Simplex algorithm there are different solution methods which are specific for a given problem.

Constraints like , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_{i}(x)\leq b

are transformed into   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  g_{i}(x) = f_{i}(x)-b \leq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_{i}(x) \leq 0

for $i=1,..,m$

and

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

for $j=1,..,n$

For function with one variable, the first and second derivatives are used.

Example Minimization

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f'(x)=10x-30

$f'(x)=0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 10x-30=0

$x=3$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f''(x)=10>0\rightarrow Minimum

Example Maximization

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

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

$f'(x)=0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -12x -12=0

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f''(x)=-12<0\rightarrow Maximum

For functions with multiple variables, identical information is used, that is the gradiant and the Hessian. The gradient Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Delta

 is the first derivative. The Hessian Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Delta^{2}
is the second derivative.
          

Gradient: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Delta f(x)= (\delta f / \delta x_{i})

Hessian: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Delta^{2}f(x) = (\delta^{2} f / \delta x_{i} \delta x_{k})

Example Hessian Matrix

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Gradient: f (x_{1}, x_{2}) = \begin{bmatrix}12-2x_{1}\\12-2x_{2}\end{bmatrix}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1}) = 0 = 12-2x_{1}\rightarrow x_{1}= 6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{2}) = 0 = 12-2x_{2} \rightarrow x_{2}= 6

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

Example Nonlinear Optimization

A company produce two products j with the same structure.

Sales price function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): p_{i}=7-x_{i}

Cost function: $c_{i}=2x_{i}$

Objective function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): objective function=5x_{1}-x^{2}+5x_{2}-x_{2}^{2} max

Machine A: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}+2x_{2}\leq 8

Machine B: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_{1}+x_{2}\leq 9

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