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

Aktuelle Version vom 8. Juli 2013, 08:42 Uhr

In a nonlinear problem there is either a nonlinear objective function and no restrictions or a nonlinear objective function and linear/nonlinear restrictions or a linear objective function and nonlinear restrictions.

Theory

In contrast to the linear programming where we have the simplex algorithm to solve this there is no universal algorithm for solving a nonlinear problem.

${\displaystyle Objective~function:Max~(orMin)z=F(x)}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Restrictions: g_i(x) \begin{Bmatrix} \le \\ = \\ \ge \end{Bmatrix}~0 ~~~~~~(for~ i ~= ~1,...,m)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \in W_1 \times W_2 \times ,..., \times W_n , W_j \in \{ \mathbb R_+, \mathbb Z_+, \mathbb B \} ~~~~~~~~~~(for~j = 1,...,n)

In contrast to linear problems, nonlinear optimization problems got a nonlinear objective function and/or at least one nonlinear restriction. As distinct from integer and combinatorial problems, where integer or binary variables occur, we assume that only (nonnegative) real variables occur in nonlinear optimization. The objective function, that has to be minimized can be replaced with the objective function, that has to be maximized and vice versa. Furthermore, every Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

– restriction can be transformed into a Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
– restriction by multiplication with -1. Beyond that, all equations can be replaced by two Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
– restrictions.

To simplify the notation, functions ${\displaystyle g_{i}}$ consist of the constants ${\displaystyle b_{i}}$, which are designated within the linear optimization:

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

is transformed into

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i(x) := f_i (x)-b_i \le 0

Assume the following notation is a nonlinear optimization problem:

Maximize F(x) under the restrictions

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i (x) \le 0 ~~for~~ i = 1,...,m

and

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

Examples

The first two examples are very easy, because there are not any restrictions. Example 1 is a simple minimization problem and example 2 a maximization problem.

Example 1 (Minimization)

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

Step 1: The necessary condition for solving this problem is to derive the function and set this derivative equal to zero.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f'(x) = 2x - 8 ~~=> ~2x - 8 = 0 ~<=>~ x = 4

Step 2: Now you have to check the sufficient condition; if you have a minimum, the second derivative of the function has to be greater than zero, for a maximum it has to be less than zero.

${\displaystyle f''(x)=2~>0~~=>minimum}$

Example 2 (Maximization)

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

Step 1: The necessary condition for solving this problem is to derive the function and set this derivative equal to zero.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f'(x) = -2x - 8 ~~=> ~-2x - 8 = 0 ~<=>~ x = -4

Step 2: Now you have to check the sufficient condition; if you have a minimum, the second derivative of the function has to be greater than zero, for a maximum it has to be less than zero.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f''(x) = -2 ~< 0 ~~=> maximum

Example 3 (Classical gradient method)

We would maximize the sum of the contribution margin of two products.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): C_m = p_i(x_i) x_i*c_i x_i ~~~~~i={1,2}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): p_i(x_i) = 7 - x_i ; c_i = 2

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_i) = \begin{bmatrix} 5-2x_1\\ 5-2x_2 \end{bmatrix} ~=> Hessian-Matrix~H(x)= \begin{bmatrix} -2&~0\\ ~0&-2 \end{bmatrix}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (-2-\lambda)*(-2-\lambda)=0 => \lambda=2 ~~

The eigenvalues are positive,so the matrix is positiv definite

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_1)=0=5-2x_1 ~=>x_1=2,5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla F(x_2)=0=5-2x_2 ~=>x_2=2,5

If ${\displaystyle F(x_{i})}$ is twice differentiable, so ${\displaystyle F(x_{i})}$ is a necessary and sufficient condition for a global maximum and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -H(x)

or ${\displaystyle H(x)}$ has to be positive definite.

How to solve different types of nonlinear problems

This is not a basic concept and therefore explained in other wiki-entries.

Class 1 (nonlinear objective function, no restrictions)

• Classical gradient method
• Golden section search

Class 2 (nonlinear objective function, linear restrictions)

• Lagrangian condition
• Karush-Kuhn-Tucker

Class 3 (nonlinear objective function, nonlinear restrictions)

• Lagrangian condition
• Karush-Kuhn-Tucker

Class 4 (linear objective function, nonlinear restrictions)

• Lagrangian condition
• Karush-Kuhn-Tucker

Sources

Internet sources

• http://de.wikipedia.org/wiki/Optimierung_(Mathematik)#Nichtlineare_Optimierung

Literature

• Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013
• Immanuel M. Bomze/W. Grossmann: Optimierung - Theorie und Algorithmen, ISBN:3-411-1509-1
• Kurt Marti/Detlef Gröger: Einführung in die lineare und nichtlineare Optimierung, ISBN:3-790-81297-8
• Wolfgang Domschke/Andreas Drexl: Einführung in Operations Research 6. Auflage ISBN:3-540-23431-4
• Hans Corsten/Hilde Corsten/Carsten Sartor: Operations Research ISBN:9-783800-632022