Nonlinear Opt.: Basic concepts 2

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

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

Theory

In contrast to the linear programming where we have the simplex algorithm to solve this there is not an universal algorithm for solving a non-linear 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, non-linear optimization problems got a non-linear objective function and/or at least one non-linear restriction. As distinct from integer and combinatorial problems, where integer or binary variables occur, we assume that only (non-negative) real variables occur in non-linear optimization. The to be minimized objective function can be replaced with the to be maximized objective function 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


The following notation is assumed to be the notation of a non-linear 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 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 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.): \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 sufficiently 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 non-linear problems

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

Class 1 (non-linear objective function, no restrictions)

Class 2 (non-linear objective function, linear restrictions)

Class 3 (non-linear objective function, non-linear restrictions)

Class 4 (linear objective function, non-linear 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
Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Nonlinear_Opt.:_Basic_concepts_2&oldid=3941“