#LyX 1.1 created this file. For more info see http://www.lyx.org/
\lyxformat 218
\textclass article
\begin_preamble
\usepackage{dsfont}

% No date please
\date{}
\fontfamily{cmss}
\selectfont
\end_preamble
\language english
\inputencoding auto
\fontscheme helvet
\graphics default
\paperfontsize default
\spacing single 
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Standard


\latex latex 
% This is for 
\backslash 
LyX
\layout Standard


\begin_inset FormulaMacro 
\newcommand{\bfrac}[2]{\frac{#1 }{#2 }}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\nth}{^{\textrm{th}}}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\R}{R}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\N}{N}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\Z}{Z}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\tra}{^{T}}

\end_inset 


\layout Standard


\begin_inset FormulaMacro 
\newcommand{\xx}{\mathbf{x}}

\end_inset 


\layout Standard


\latex latex 
% This is for 
\backslash 
LaTeX
\layout Standard


\latex latex 

\backslash 
fontfamily{cmss}
\backslash 
selectfont
\layout Standard


\latex latex 

\backslash 
renewcommand{
\backslash 
R}{{
\backslash 
mathds{R}}} 
\layout Standard


\latex latex 

\backslash 
renewcommand{
\backslash 
N}{{
\backslash 
mathds{N}}}
\layout Standard


\latex latex 

\backslash 
renewcommand{
\backslash 
Z}{{
\backslash 
mathds{Z}}}
\layout Standard


\latex latex 

\backslash 
renewcommand{
\backslash 
tra}{^{
\backslash 
top}}
\layout Standard


\latex latex 

\backslash 
renewcommand{
\backslash 
bfrac}[2]{
\backslash 
frac{{
\backslash 
textstyle #1 }}{{
\backslash 
textstyle #2 }}}
\layout Title

Mini-HOWTO on using Octave for Unconstrained Nonlinear Optimization
\begin_float footnote 
\layout Standard

Author : Etienne Grossmann 
\family typewriter 
<etienne@isr.ist.utl.pt>
\family default 
 (soon replaced by 
\begin_inset Quotes eld
\end_inset 

Octave-Forge developers
\begin_inset Quotes erd
\end_inset 

?).
 This document is free documentation; you can redistribute it and/or modify
 it under the terms of the GNU Free Documentation License as published by
 the Free Software Foundation.
\newline 
.\SpecialChar ~
\SpecialChar ~
\SpecialChar ~
This is distributed in the hope that it will be useful, but WITHOUT ANY
 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 FOR A PARTICULAR PURPOSE.
\end_float 
\layout Comment

Keywords: nonlinear optimization, octave, tutorial, Nelder-Mead, Conjugate
 Gradient, Levenberg-Marquardt
\layout Standard

Nonlinear optimization problems are very common and when a solution cannot
 be found analytically, one usually tries to find it numerically.
 This document shows how to perform unconstrained nonlinear minimization
 using the Octave language for numerical computation.
 We assume to be so lucky as to have an initial guess from which to start
 an iterative method, and so impatient as to avoid as much as possible going
 into the details of the algorithm.
 In the following examples, we consider multivariable problems, but the
 single variable case is solved in exactly the same way.
\layout Standard

All the algorithms used below return numerical approximations of 
\emph on 
local minima
\emph default 
 of the optimized function.
 In the following examples, we minimize a function with a single minimum
 (Figure\SpecialChar ~

\begin_inset LatexCommand \ref{fig:function}

\end_inset 

), which is relatively easily found.
 In practice, success of optimization algorithms greatly depend on the optimized
 function and on the starting point.
\layout Section*


\begin_inset ERT
collapsed true

\layout Standard


\latex latex 

\backslash 
fontfamily{cmss} 
\backslash 
selectfont 
\end_inset 

A simple example
\layout Standard

\begin_float fig 
\layout Standard
\align center 

\latex latex 

\backslash 
raisebox{6mm}{
\begin_inset Figure size 178 160
file figures/2D_slice-3.eps2
width 3 30
flags 11

\end_inset 

}\SpecialChar ~

\begin_inset Figure size 297 193
file figures/optim_tutorial_slice.eps
width 3 50
flags 9

\end_inset 


\layout Caption


\begin_inset LatexCommand \label{fig:function}

\end_inset 

 2D and 1D slices of the function that is minimized throughout this tutorial.
 Although not obvious at first sight, it has a unique minimum.
\end_float 
\layout Standard

We will use a call of the type
\layout LyX-Code

[x_best, best_value, niter] = minimize (func, x_init)
\layout Standard

to find the minimum of 
\begin_inset Formula \[
\begin{array}{cccc}
f\, : & \left( x_{1},.x_{2},x_{3}\right) \in \R ^{3} & \longrightarrow  & \left( x_{1}-1\right) ^{2}/9+\left( x_{3}-1\right) ^{2}/9+\left( x_{3}-1\right) ^{2}/9\\
 &  &  & -\cos \left( x_{1}-1\right) -\cos \left( x_{2}-1\right) -\cos \left( x_{3}-1\right) .
\end{array}\]

\end_inset 


\layout Standard

The following commands should find a local minimum of 
\begin_inset Formula \( f() \)
\end_inset 

, using the Nelder-Mead (aka 
\begin_inset Quotes eld
\end_inset 

downhill simplex
\begin_inset Quotes erd
\end_inset 

) algorithm and starting from a randomly chosen point 
\family typewriter 
x0
\family default 
\SpecialChar ~
:
\layout LyX-Code

function cost = foo (xx)
\layout LyX-Code

  xx--;  
\layout LyX-Code

  cost = sum (-cos(xx)+xx.^2/9);
\layout LyX-Code

endfunction
\layout LyX-Code

x0 = [-1, 3, -2];
\layout LyX-Code

[x,v,n] = minimize ("foo", x0)
\layout Standard

The output should look like\SpecialChar ~
:
\layout LyX-Code

x =
\layout LyX-Code

  1.00000 1.00000 1.00000
\layout LyX-Code

\layout LyX-Code

v = -3.0000
\layout LyX-Code

n = 248
\layout Standard

This means that a minimum has been found in 
\begin_inset Formula \( \left( 1,1,1\right)  \)
\end_inset 

 and that the value at that point is 
\begin_inset Formula \( -3 \)
\end_inset 

.
 This is correct, since all the points of the form 
\begin_inset Formula \( x_{1}=1+2i\pi ,\, x_{2}=1+2j\pi ,\, x_{3}=1+2k\pi  \)
\end_inset 

, for some 
\begin_inset Formula \( i,j,k\in \N  \)
\end_inset 

, minimize 
\begin_inset Formula \( f() \)
\end_inset 

.
 The number of function evaluations, 248, is also returned.
 Note that this number depends on the starting point.
 You will most likely obtain different numbers if you change 
\family typewriter 
x0
\family default 
.
\layout Standard

The Nelder-Mead algorithm is quite robust, but unfortunately it is not very
 efficient.
 For high-dimensional problems, its execution time may become prohibitive.
\layout Section*


\begin_inset ERT
collapsed true

\layout Standard


\latex latex 

\backslash 
fontfamily{cmss} 
\backslash 
selectfont 
\end_inset 

Using the first differential
\layout Standard

Fortunately, when a function, like 
\begin_inset Formula \( f() \)
\end_inset 

 above, is differentiable, more efficient optimization algorithms can be
 used.
 If 
\family typewriter 
minimize()
\family default 
 is given the differential of the optimized function, using the 
\family typewriter 
"df"
\family default 
 option, it will use a conjugate gradient method.
\layout LyX-Code

## Function returning partial derivatives
\layout LyX-Code

function dc = diffoo (x)
\layout LyX-Code

    x = x(:)' - 1;
\layout LyX-Code

    dc = sin (x) + 2*x/9;
\layout LyX-Code

endfunction
\layout LyX-Code

[x, v, n] = minimize ("foo", x0, "df", "diffoo")
\layout Standard

This produces the output\SpecialChar ~
:
\layout LyX-Code

x =
\layout LyX-Code

  1.00000 1.00000 1.00000
\layout LyX-Code

v = -3 
\layout LyX-Code

n =
\layout LyX-Code

  108 6
\layout Standard

The same minimum has been found, but only 108 function evaluations were
 needed, together with 6 evaluations of the differential.
 Here, 
\family typewriter 
diffoo()
\family default 
 takes the same argument as 
\family typewriter 
foo()
\family default 
 and returns the partial derivatives of 
\begin_inset Formula \( f() \)
\end_inset 

 with respect to the corresponding variables.
 It doesn't matter if it returns a row or column vector or a matrix, as
 long as the 
\begin_inset Formula \( i\nth  \)
\end_inset 

 element of 
\family typewriter 
diffoo(x)
\family default 
 is the partial derivative of 
\begin_inset Formula \( f() \)
\end_inset 

 with respect to 
\begin_inset Formula \( x_{i} \)
\end_inset 

 .
\layout Section*


\begin_inset ERT
collapsed true

\layout Standard


\latex latex 

\backslash 
fontfamily{cmss} 
\backslash 
selectfont 
\end_inset 

Using numerical approximations of the first differential
\layout Standard

Sometimes, the minimized function is differentiable, but actually writing
 down its differential is more work than one would like.
 Numerical differentiation offers a solution which is less efficient in
 terms of computation cost, but easy to implement.
 The 
\family typewriter 
"ndiff"
\family default 
 option of 
\family typewriter 
minimize()
\family default 
 uses numerical differentiation to execute exactly the same algorithm as
 in the previous example.
 However, because numerical approximation of the differentia is used, the
 outpud may differ slightly\SpecialChar ~
:
\layout LyX-Code

[x, v, n] = minimize ("foo", x0, "ndiff")
\layout Standard

wich yields\SpecialChar ~
:
\layout LyX-Code

x =
\layout LyX-Code

  1.00000 1.00000 1.00000
\layout LyX-Code

v = -3 
\layout LyX-Code

n =
\layout LyX-Code

  78 6
\layout Standard

Note that each time the differential is numerically approximated, 
\family typewriter 
foo()
\family default 
 is called 6 times (twice per input element), so that 
\family typewriter 
foo()
\family default 
 is evaluated a total of (78+6*6=) 114 times in this example.
\layout Section*


\begin_inset ERT
collapsed true

\layout Standard


\latex latex 

\backslash 
fontfamily{cmss} 
\backslash 
selectfont 
\end_inset 

Using the first and second differentials
\layout Standard

When the function is twice differentiable and one knows how to compute its
 first and second differentials, still more efficient algorithms can be
 used (in our case, a variant of Levenberg-Marquardt).
 The option 
\family typewriter 
"d2f"
\family default 
 allows to specify a function that returns the value of the function, the
 first and second differentials of the minimized function.
 Entering the commands\SpecialChar ~
: 
\layout LyX-Code

function [c, dc, d2c] = d2foo (x)
\layout LyX-Code

    c = foo(x);
\layout LyX-Code

    dc = diffoo(x);
\layout LyX-Code

    d2c = diag (cos (x(:)-1) + 2/9);
\layout LyX-Code

end
\layout LyX-Code

[x,v,n] = minimize ("foo", x0, "d2f", "d2foo") 
\layout Standard

produces the output\SpecialChar ~
:
\layout LyX-Code

x =
\layout LyX-Code

  1.0000 1.0000 1.0000
\layout LyX-Code

v = -3
\layout LyX-Code

n =
\layout LyX-Code

  34 5
\layout Standard

This time, 34 function evaluations, and 5 evaluations of 
\family typewriter 
d2foo()
\family default 
 were needed.
\layout Section*


\begin_inset ERT
collapsed true

\layout Standard


\latex latex 

\backslash 
fontfamily{cmss} 
\backslash 
selectfont 
\end_inset 

Summary
\layout Standard

We have just seen the most basic ways of solving nonlinear unconstrained
 optimization problems.
 The online help system of Octave (try e.g.
 
\begin_inset Quotes eld
\end_inset 


\family typewriter 
help minimize
\family default 

\begin_inset Quotes erd
\end_inset 

) will yield information on other issues, such as 
\emph on 
passing extra arguments
\emph default 
 to the minimized function, 
\emph on 
controling the termination
\emph default 
 of the optimization process, choosing the algorithm etc.
\layout LyX-Code

\the_end