Nonlinear Opt.: Classical gradient method 2

Nonlinear optimization: Classical gradient method

The classical gradient method is used to find a solution for an optimization problem. The basic idea is to start with a starting value or approximated value respectively and step forward to the direction of the negative gradient until no numeric improvement is verifiably. We are using a negative gradient, because the gradient should show off the steepest descent emanating from the approximated value.

The method

Input is a solvable constant differentiable optimization problem. By taking point x ∈ Z as a given, amount Z(x) includes the admissible directions, which means all vectors s ∈ Ζ with δ’ > 0, so that x + δs ∈ Z for 0 < δ < δ’. If ∇ f (x) is the gradient of a minimized function f, so it is essential at the optimum:

                                                                  s$^{T}$ ∇f(x*) ≥ 0, ∀ s ∈ Z(x*) .

If at point x does exist a s ∈ Z(x) with s$^{T}$ ∇ f (x) < 0, so you’ll get an improved solution in direction s.

Algorithm of the classical gradient method:

1. Choose x$_{0}$ ∈ Z$^{n}$ and apply k := 0.

2. Calculate ∇ f (x$^{k}$). If ∇ f (x$^{k}$) = 0, optimum founded, end.

3. Decide s$_{k}$ ∈ $\mathbb {R}$$^{n}$ with s$_{k}^{T}$∇ f (x$_{k}$) < 0.

4. Calculate δ$_{k}$ > 0 with f (x$_{k}$ + δ$_{k}$ s$_{k}$) < f(x$_{k}$).

5. Apply x$_{k+1}$ := x$_{k}$ + δ$_{k}$ s$_{k}$, raise k and go to step 2.

Gradient methods differ according to the concrete choice of s$_{k}$ and δ$_{k}$. The nearest approach is the gradient descent method.

Gradient descent method

Point of origin, the gradient features at every point the direction of the steepest ascent. Thus for ∇ f (x$_{k}$) ≠ 0 apply s$_{k}$ = - ∇ f (x$_{k}$) to achieve the steepest descent. There we search the greatest possible improvement. Consequentially define function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \varphi (δ) := f (x$_{k}$ + δ s$_{k}$) and decide minimum (for δ > 0).

Algorithm of the gradient descent method:

1. Choose x$_{0}$ ∈ $\mathbb {R}$$^{n}$ and apply k := 0.

2. Calculate ∇ f (x$_{k}$). If ∇ f (x$_{k}$) = 0, optimum founded, end.

3. Calculate δ$_{k}$ > 0 as the minimum of function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \varphi

(δ) := f (x$_{k}$ – δ f ∇(x$_{k}$)).

4. Apply x$_{k+1}$ := x$_{k}$ - δ$_{k}$∇ f (x$_{k}$), raise k and go to step 2.

Alternatively, another method is to get by on using a range-tolerance ε defined by oneself. The optimum would be founded, if ||∇ f (''x$_{k}$)|| < ε. In that case ∇ f (x$_{k}$) is located nearby the zero vector, so x$_{k}$ would be accepted as an approximation of a critical point.

Example:

1. x$_{0}$ = ${\binom {1}{1}}$; k := 0.

2. Searching a minimum of the function: f (x$_{1}$,x$_{2}$) = 2x$_{1}^{2}$ + 4x$_{2}^{2}$. The gradient is:

  					        	          ∇f(x$_{1}$,x$_{2}$) = (4x$_{1}$,8x$_{2}$)$^{T}$.

Gradient ∇ f (1,1) = ${\binom {4}{8}}$, i.e. the steepest descent is in direction Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \binom{-4}{-8} .

3. Calculate Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \varphi (δ):

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

(δ)	= 	f (${\binom {1}{1}}$ – δ${\binom {4}{8}}$)

= 2(1 – 4*δ)$^{2}$ + 4(1 – 8*δ)$^{2}$ 6 – 80*δ + 288*δ$^{2}$

                                       Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \varphi
’(δ)	=	-80 + 576*δ		
                                               => δ 	=	 ${\frac {5}{36}}$ 		= 0,1389

4. x$_{1}$ = ${\binom {1}{1}}$ – ${\frac {5}{36}}$*${\binom {4}{8}}$ = ${\frac {1}{9}}$*${\binom {4}{7}}$

Continuing steps feature the convergence toward ${\binom {0}{0}}$.

References

Nickel, Stefan; Stein, Oliver; Waldmann, Karl-Heinz: Operations Research, Verlag Springer 2011

Zimmermann, Hans-Jürgen: Operations Research, Verlag Vieweg, 1. Auflage März 2005

Wendt, Prof. Dr. Oliver: Spript Operations Research, University of Kaiserslautern, Summer Semester 2013

Beisel, David: Das Gradientenverfahren, University of Paderborn, 10. December 2012