Nonlinear Opt.: Basic concepts 2
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.
Inhaltsverzeichnis
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.
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 consist of the constants , 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.
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 is twice differentiable, so 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 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)
Class 2 (nonlinear objective function, linear restrictions)
Class 3 (nonlinear objective function, nonlinear restrictions)
Class 4 (linear objective function, nonlinear restrictions)
Sources
Internet sources
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
