Mercurial > forge
changeset 2592:aeec4097c132 octave-forge
First attempt at automatic doc build
| author | adb014 |
|---|---|
| date | Thu, 05 Oct 2006 10:44:49 +0000 |
| parents | 33bcf6e72d9c |
| children | e61209c0f871 |
| files | main/optim/Makefile main/optim/doc/Makefile main/optim/doc/optim-mini-howto-2.lyx main/optim/doc/optim-mini-howto-2.tex main/optim/doc/optim-mini-howto.2.html main/optim/doc/optim-mini-howto.2.lyx main/optim/doc/optim-mini-howto.2.tex |
| diffstat | 7 files changed, 1066 insertions(+), 1324 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/optim/Makefile Thu Oct 05 10:44:49 2006 +0000 @@ -0,0 +1,18 @@ +sinclude ../../Makeconf +sinclude ../../pkg.mk + +PKG_FILES = COPYING DESCRIPTION INDEX $(wildcard src/*) \ + $(wildcard inst/*) doc/*.pdf +SUBDIRS = doc/ + +.PHONY: $(SUBDIRS) + +pre-pkg/%:: + @for _dir in $(SUBDIRS); do \ + make -C $$_dir; \ + done + +clean: + @for _dir in $(SUBDIRS); do \ + make -C $$_dir $(MAKECMDGOALS); \ + done
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/optim/doc/Makefile Thu Oct 05 10:44:49 2006 +0000 @@ -0,0 +1,35 @@ +sinclude ../../../Makeconf + +TEX = mintoolkit.tex optim-mini-howto-2.tex +PDF = $(patsubst %.tex,%.pdf,$(TEX)) +HTML = $(patsubst %.tex,%/index.html,$(TEX)) + +all : $(PDF) html + +.PHONY: html +html : $(HTML) + if [ -e "html" ]; then \ + rm -fr html; \ + fi; \ + mkdir html; \ + $(INSTALL_DATA) -d mintoolkit html; \ + $(INSTALL_DATA) -d optim-mini-howto-2 html; \ + echo '<html><body>' > html/index.html; \ + echo '<p><a href="minitoolkit/index.html">minitoolkit</a></p>' >> html/index.html; \ + echo '<p><a href="optim-mini-howto-2/index.html">optim-mini-howto-2</a></p>' >> html/index.html; \ + echo '</body></html>' >> html/index.html + +%.pdf : %.tex + latex $< > /dev/null 2>&1 + latex $< > /dev/null 2>&1 + dvipdf $(@:.pdf=.dvi) + +%/index.html : %.tex + latex2html $< + +clean: + rm -fr $(patsubst %.tex,%,$(TEX)) html *.log + rm -f $(PDF) *~ + rm -f $(patsubst %.tex,%.aux,$(TEX)) + rm -f $(patsubst %.tex,%.out,$(TEX)) + rm -f $(patsubst %.tex,%.dvi,$(TEX))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/optim/doc/optim-mini-howto-2.lyx Thu Oct 05 10:44:49 2006 +0000 @@ -0,0 +1,703 @@ +#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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/optim/doc/optim-mini-howto-2.tex Thu Oct 05 10:44:49 2006 +0000 @@ -0,0 +1,310 @@ +%% LyX 1.1 created this file. For more info, see http://www.lyx.org/. +%% Do not edit unless you really know what you are doing. +\documentclass[english]{article} +\usepackage{helvet} +\usepackage[T1]{fontenc} +\usepackage[latin1]{inputenc} +% \usepackage{babel} +\usepackage{graphics} + +\makeatletter + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. +\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. + \newenvironment{lyxcode} + {\begin{list}{}{ + \setlength{\rightmargin}{\leftmargin} + \raggedright + \setlength{\itemsep}{0pt} + \setlength{\parsep}{0pt} + \normalfont\ttfamily}% + \item[]} + {\end{list}} + \usepackage{verbatim} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. +\usepackage{dsfont} + +% No date please +\date{} +\fontfamily{cmss} +\selectfont +\makeatother +\begin{document} +% This is for \LyX + + +\newcommand{\bfrac}[2]{\frac{#1 }{#2 }} + + + +\newcommand{\nth}{^{\textrm{th}}} + + + +\newcommand{\R}{R} + + + +\newcommand{\N}{N} + + + +\newcommand{\Z}{Z} + + + +\newcommand{\tra}{^{T}} + + + +\newcommand{\xx}{\mathbf{x}} + + +% This is for \LaTeX + +\fontfamily{cmss}\selectfont + +\renewcommand{\R}{{\mathds{R}}} + +\renewcommand{\N}{{\mathds{N}}} + +\renewcommand{\Z}{{\mathds{Z}}} + +\renewcommand{\tra}{^{\top}} + +\renewcommand{\bfrac}[2]{\frac{{\textstyle #1 }}{{\textstyle #2 }}} + + +\title{Mini-HOWTO on using Octave for Unconstrained Nonlinear Optimization% +\thanks{Author : Etienne Grossmann \texttt{<etienne@isr.ist.utl.pt>} (soon +replaced by {}``Octave-Forge developers''?). 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.\protect \\ +.~~~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. +}} + +\maketitle +\begin{comment} +Keywords: nonlinear optimization, octave, tutorial, Nelder-Mead, Conjugate +Gradient, Levenberg-Marquardt +\end{comment} +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. + +All the algorithms used below return numerical approximations of \emph{local +minima} of the optimized function. In the following examples, we minimize +a function with a single minimum (Figure~\ref{fig:function}), which +is relatively easily found. In practice, success of optimization algorithms +greatly depend on the optimized function and on the starting point. + + +\section*{\fontfamily{cmss} \selectfont A simple example} + + +\begin{figure} +{\centering \raisebox{6mm}{\resizebox*{0.3\textwidth}{!}{\includegraphics{figures/2D_slice-3.eps2}} }~\resizebox*{0.5\textwidth}{!}{\includegraphics{figures/optim_tutorial_slice.eps}} \par} + + +\caption{\label{fig:function} 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{figure} + + +We will use a call of the type + +\begin{lyxcode} +{[}x\_best,~best\_value,~niter{]}~=~minimize~(func,~x\_init) +\end{lyxcode} +to find the minimum of \[ +\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}\] + + +The following commands should find a local minimum of \( f() \), +using the Nelder-Mead (aka {}``downhill simplex'') algorithm and +starting from a randomly chosen point \texttt{x0}~: + +\begin{lyxcode} +function~cost~=~foo~(xx) + +~~xx-{}-;~~ + +~~cost~=~sum~(-cos(xx)+xx.\textasciicircum{}2/9); + +endfunction + +x0~=~{[}-1,~3,~-2{]}; + +{[}x,v,n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0) +\end{lyxcode} +The output should look like~: + +\begin{lyxcode} +x~= + +~~1.00000~1.00000~1.00000 + + + +v~=~-3.0000 + +n~=~248 +\end{lyxcode} +This means that a minimum has been found in \( \left( 1,1,1\right) \) +and that the value at that point is \( -3 \). This is correct, since +all the points of the form \( x_{1}=1+2i\pi ,\, x_{2}=1+2j\pi ,\, x_{3}=1+2k\pi \), +for some \( i,j,k\in \N \), minimize \( f() \). 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 \texttt{x0}. + +The Nelder-Mead algorithm is quite robust, but unfortunately it is +not very efficient. For high-dimensional problems, its execution time +may become prohibitive. + + +\section*{\fontfamily{cmss} \selectfont Using the first differential} + +Fortunately, when a function, like \( f() \) above, is differentiable, +more efficient optimization algorithms can be used. If \texttt{minimize()} +is given the differential of the optimized function, using the \texttt{\char`\"{}df\char`\"{}} +option, it will use a conjugate gradient method. + +\begin{lyxcode} +\#\#~Function~returning~partial~derivatives + +function~dc~=~diffoo~(x) + +~~~~x~=~x(:)'~-~1; + +~~~~dc~=~sin~(x)~+~2{*}x/9; + +endfunction + +{[}x,~v,~n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}df\char`\"{},~\char`\"{}diffoo\char`\"{}) +\end{lyxcode} +This produces the output~: + +\begin{lyxcode} +x~= + +~~1.00000~1.00000~1.00000 + +v~=~-3~ + +n~= + +~~108~6 +\end{lyxcode} +The same minimum has been found, but only 108 function evaluations +were needed, together with 6 evaluations of the differential. Here, +\texttt{diffoo()} takes the same argument as \texttt{foo()} and returns +the partial derivatives of \( f() \) 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 \( i\nth \) element of \texttt{diffoo(x)} +is the partial derivative of \( f() \) with respect to \( x_{i} \) +. + + +\section*{\fontfamily{cmss} \selectfont Using numerical approximations of +the first differential} + +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 \texttt{\char`\"{}ndiff\char`\"{}} +option of \texttt{minimize()} 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~: + +\begin{lyxcode} +{[}x,~v,~n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}ndiff\char`\"{}) +\end{lyxcode} +wich yields~: + +\begin{lyxcode} +x~= + +~~1.00000~1.00000~1.00000 + +v~=~-3~ + +n~= + +~~78~6 +\end{lyxcode} +Note that each time the differential is numerically approximated, +\texttt{foo()} is called 6 times (twice per input element), so that +\texttt{foo()} is evaluated a total of (78+6{*}6=) 114 times in this +example. + + +\section*{\fontfamily{cmss} \selectfont Using the first and second differentials} + +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 +\texttt{\char`\"{}d2f\char`\"{}} allows to specify a function that +returns the value of the function, the first and second differentials +of the minimized function. Entering the commands~: + +\begin{lyxcode} +function~{[}c,~dc,~d2c{]}~=~d2foo~(x) + +~~~~c~=~foo(x); + +~~~~dc~=~diffoo(x); + +~~~~d2c~=~diag~(cos~(x(:)-1)~+~2/9); + +end + +{[}x,v,n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}d2f\char`\"{},~\char`\"{}d2foo\char`\"{})~ +\end{lyxcode} +produces the output~: + +\begin{lyxcode} +x~= + +~~1.0000~1.0000~1.0000 + +v~=~-3 + +n~= + +~~34~5 +\end{lyxcode} +This time, 34 function evaluations, and 5 evaluations of \texttt{d2foo()} +were needed. + + +\section*{\fontfamily{cmss} \selectfont Summary} + +We have just seen the most basic ways of solving nonlinear unconstrained +optimization problems. The online help system of Octave (try e.g. +{}``\texttt{help minimize}'') will yield information on other issues, +such as \emph{passing extra arguments} to the minimized function, +\emph{controling the termination} of the optimization process, choosing +the algorithm etc. + +\begin{lyxcode} +\end{lyxcode} + +\end{document}
--- a/main/optim/doc/optim-mini-howto.2.html Thu Oct 05 10:24:36 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,311 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" - "http://www.w3.org/TR/REC-html40/loose.dtd"> -<HTML> -<HEAD><TITLE></TITLE> - -<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> -<META name="GENERATOR" content="hevea 1.06"> -</HEAD> -<BODY > -<!--HEVEA command line is: /usr/bin/hevea optim-mini-howto.2.tex --> -<!--HTMLHEAD--> -<!--ENDHTML--> -<!--PREFIX <ARG ></ARG>--> -<!--CUT DEF section 1 --> - -<BR> -<BR> -cmss<BR> -<BR> - - -<H1 ALIGN=center>Mini-HOWTO on using Octave for Unconstrained Nonlinear Optimization<A NAME="text1" HREF="#note1"><SUP><FONT SIZE=2>1</FONT></SUP></A></H1> - -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.<BR> -<BR> -All the algorithms used below return numerical approximations of <EM>local -minima</EM> of the optimized function. In the following examples, we minimize -a function with a single minimum (Figure <A HREF="#fig:function">1</A>), which -is relatively easily found. In practice, success of optimization algorithms -greatly depend on the optimized function and on the starting point.<BR> -<BR> -<!--TOC section cmss A simple example--> - -<H2>cmss A simple example</H2><!--SEC END --> - -<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV> -<DIV ALIGN=center>6mm<IMG SRC="optim-mini-howto.2001.png"> <IMG SRC="optim-mini-howto.2002.png"> </DIV><BR> -<DIV ALIGN=center>Figure 1: <A NAME="fig:function"></A> 2D and 1D slices of the function that is minimized -throughout this tutorial. Although not obvious at first sight, it -has a unique minimum.</DIV><BR> - -<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE> -We will use a call of the type -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -[x_best, best_value, niter] = minimize (func, x_init) -</TT></DL></DIV> -to find the minimum of <DIV ALIGN=center><TABLE> -<TR VALIGN=middle><TD NOWRAP> -</TD> -<TD NOWRAP><TABLE CELLSPACING=2 CELLPADDING=0> -<TR><TD ALIGN=center NOWRAP><I>f</I> :</TD> -<TD ALIGN=center NOWRAP><TABLE> -<TR VALIGN=middle><TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>1</FONT></SUB>,.<I>x</I><SUB><FONT SIZE=2>2</FONT></SUB>,<I>x</I><SUB><FONT SIZE=2>3</FONT></SUB></TD> -<TD NOWRAP>)</TD> -<TD NOWRAP><FONT FACE=symbol>Î</FONT> <I>R</I> <SUP><FONT SIZE=2>3</FONT></SUP></TD> -</TR></TABLE></TD> -<TD ALIGN=center NOWRAP><FONT FACE=symbol>¾®</FONT></TD> -<TD ALIGN=center NOWRAP><TABLE> -<TR VALIGN=middle><TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>1</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0> -<TR><TD ALIGN=left NOWRAP><FONT SIZE=2>2</FONT></TD> -</TR> -<TR><TD ALIGN=left> </TD> -</TR> -<TR><TD ALIGN=left NOWRAP> </TD> -</TR></TABLE></TD> -<TD NOWRAP>/9+</TD> -<TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>3</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0> -<TR><TD ALIGN=left NOWRAP><FONT SIZE=2>2</FONT></TD> -</TR> -<TR><TD ALIGN=left> </TD> -</TR> -<TR><TD ALIGN=left NOWRAP> </TD> -</TR></TABLE></TD> -<TD NOWRAP>/9+</TD> -<TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>3</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP><TABLE CELLSPACING=0 CELLPADDING=0> -<TR><TD ALIGN=left NOWRAP><FONT SIZE=2>2</FONT></TD> -</TR> -<TR><TD ALIGN=left> </TD> -</TR> -<TR><TD ALIGN=left NOWRAP> </TD> -</TR></TABLE></TD> -<TD NOWRAP>/9</TD> -</TR></TABLE></TD> -</TR> -<TR><TD ALIGN=center NOWRAP> </TD> -<TD ALIGN=center NOWRAP> </TD> -<TD ALIGN=center NOWRAP> </TD> -<TD ALIGN=center NOWRAP><TABLE> -<TR VALIGN=middle><TD NOWRAP>-cos</TD> -<TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>1</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP>-cos</TD> -<TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>2</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP>-cos</TD> -<TD NOWRAP>(</TD> -<TD NOWRAP><I>x</I><SUB><FONT SIZE=2>3</FONT></SUB>-1</TD> -<TD NOWRAP>)</TD> -<TD NOWRAP>.</TD> -</TR></TABLE></TD> -</TR></TABLE></TD> -</TR></TABLE></DIV><BR> -The following commands should find a local minimum of <I>f</I>() , -using the Nelder-Mead (aka ``downhill simplex'') algorithm and -starting from a randomly chosen point <TT>x0</TT> : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -function cost = foo (xx)<BR> -<BR> - xx--; <BR> -<BR> - cost = sum (-cos(xx)+xx.2/9);<BR> -<BR> -endfunction<BR> -<BR> -x0 = [-1, 3, -2];<BR> -<BR> -[x,v,n] = minimize ("foo", x0) -</TT></DL></DIV> -The output should look like : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -x =<BR> -<BR> - 1.00000 1.00000 1.00000<BR> -<BR> -v = -3.0000<BR> -<BR> -n = 248 -</TT></DL></DIV> -This means that a minimum has been found in <TABLE> -<TR VALIGN=middle><TD NOWRAP>(</TD> -<TD NOWRAP>1,1,1</TD> -<TD NOWRAP>)</TD> -</TR></TABLE> -and that the value at that point is -3 . This is correct, since -all the points of the form <I>x</I><SUB><FONT SIZE=2>1</FONT></SUB>=1+2<I>i</I><FONT FACE=symbol>p</FONT> , <I>x</I><SUB><FONT SIZE=2>2</FONT></SUB>=1+2<I>j</I><FONT FACE=symbol>p</FONT> , <I>x</I><SUB><FONT SIZE=2>3</FONT></SUB>=1+2<I>k</I><FONT FACE=symbol>p</FONT> , -for some <I>i</I>,<I>j</I>,<I>k</I><FONT FACE=symbol>Î</FONT> <I>N</I> , minimize <I>f</I>() . 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 <TT>x0</TT>.<BR> -<BR> -The Nelder-Mead algorithm is quite robust, but unfortunately it is -not very efficient. For high-dimensional problems, its execution time -may become prohibitive.<BR> -<BR> -<!--TOC section cmss Using the first differential--> - -<H2>cmss Using the first differential</H2><!--SEC END --> - -Fortunately, when a function, like <I>f</I>() above, is differentiable, -more efficient optimization algorithms can be used. If <TT>minimize()</TT> -is given the differential of the optimized function, using the <TT>"df"</TT> -option, it will use a conjugate gradient method. -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -## Function returning partial derivatives<BR> -<BR> -function dc = diffoo (x)<BR> -<BR> - x = x(:)' - 1;<BR> -<BR> - dc = sin (x) + 2*x/9;<BR> -<BR> -endfunction<BR> -<BR> -[x, v, n] = minimize ("foo", x0, "df", "diffoo") -</TT></DL></DIV> -This produces the output : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -x =<BR> -<BR> - 1.00000 1.00000 1.00000<BR> -<BR> -v = -3 <BR> -<BR> -n =<BR> -<BR> - 108 6 -</TT></DL></DIV> -The same minimum has been found, but only 108 function evaluations -were needed, together with 6 evaluations of the differential. Here, -<TT>diffoo()</TT> takes the same argument as <TT>foo()</TT> and returns -the partial derivatives of <I>f</I>() 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 <I>i</I><SUP><FONT SIZE=2>th</FONT></SUP> element of <TT>diffoo(x)</TT> -is the partial derivative of <I>f</I>() with respect to <I>x</I><SUB><FONT SIZE=2><I>i</I></FONT></SUB> -.<BR> -<BR> -<!--TOC section cmss Using numerical approximations of -the first differential--> - -<H2>cmss Using numerical approximations of -the first differential</H2><!--SEC END --> - -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 <TT>"ndiff"</TT> -option of <TT>minimize()</TT> 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 : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -[x, v, n] = minimize ("foo", x0, "ndiff") -</TT></DL></DIV> -wich yields : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -x =<BR> -<BR> - 1.00000 1.00000 1.00000<BR> -<BR> -v = -3 <BR> -<BR> -n =<BR> -<BR> - 78 6 -</TT></DL></DIV> -Note that each time the differential is numerically approximated, -<TT>foo()</TT> is called 6 times (twice per input element), so that -<TT>foo()</TT> is evaluated a total of (78+6*6=) 114 times in this -example.<BR> -<BR> -<!--TOC section cmss Using the first and second differentials--> - -<H2>cmss Using the first and second differentials</H2><!--SEC END --> - -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 -<TT>"d2f"</TT> allows to specify a function that -returns the value of the function, the first and second differentials -of the minimized function. Entering the commands : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -function [c, dc, d2c] = d2foo (x)<BR> -<BR> - c = foo(x);<BR> -<BR> - dc = diffoo(x);<BR> -<BR> - d2c = diag (cos (x(:)-1) + 2/9);<BR> -<BR> -end<BR> -<BR> -[x,v,n] = minimize ("foo", x0, "d2f", "d2foo") -</TT></DL></DIV> -produces the output : -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -x =<BR> -<BR> - 1.0000 1.0000 1.0000<BR> -<BR> -v = -3<BR> -<BR> -n =<BR> -<BR> - 34 5 -</TT></DL></DIV> -This time, 34 function evaluations, and 5 evaluations of <TT>d2foo()</TT> -were needed.<BR> -<BR> -<!--TOC section cmss Summary--> - -<H2>cmss Summary</H2><!--SEC END --> - -We have just seen the most basic ways of solving nonlinear unconstrained -optimization problems. The online help system of Octave (try e.g. -``<TT>help minimize</TT>'') will yield information on other issues, -such as <EM>passing extra arguments</EM> to the minimized function, -<EM>controling the termination</EM> of the optimization process, choosing -the algorithm etc. -<DIV ALIGN=left><DL COMPACT=compact><DT><DD><TT> -</TT></DL></DIV> -<!--BEGIN NOTES document--> -<HR WIDTH="50%" SIZE=1><DL><DT><A NAME="note1" HREF="#text1"><FONT SIZE=5>1</FONT></A><DD>Author : Etienne Grossmann <TT><etienne@isr.ist.utl.pt></TT> (soon -replaced by ``Octave-Forge developers''?). 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.<BR> -. 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. - -</DL> -<!--END NOTES--> -<!--HTMLFOOT--> -<!--ENDHTML--> -<!--FOOTER--> -<HR SIZE=2> -<BLOCKQUOTE><EM>This document was translated from L<sup>A</sup>T<sub>E</sub>X by -</EM><A HREF="http://pauillac.inria.fr/~maranget/hevea/index.html"><EM>H<FONT SIZE=2><sup>E</sup></FONT>V<FONT SIZE=2><sup>E</sup></FONT>A</EM></A><EM>. -</EM></BLOCKQUOTE> -</BODY> -</HTML>
--- a/main/optim/doc/optim-mini-howto.2.lyx Thu Oct 05 10:24:36 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,703 +0,0 @@ -#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
--- a/main/optim/doc/optim-mini-howto.2.tex Thu Oct 05 10:24:36 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,310 +0,0 @@ -%% LyX 1.1 created this file. For more info, see http://www.lyx.org/. -%% Do not edit unless you really know what you are doing. -\documentclass[english]{article} -\usepackage{helvet} -\usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} -% \usepackage{babel} -\usepackage{graphics} - -\makeatletter - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. -\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. - \newenvironment{lyxcode} - {\begin{list}{}{ - \setlength{\rightmargin}{\leftmargin} - \raggedright - \setlength{\itemsep}{0pt} - \setlength{\parsep}{0pt} - \normalfont\ttfamily}% - \item[]} - {\end{list}} - \usepackage{verbatim} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. -\usepackage{dsfont} - -% No date please -\date{} -\fontfamily{cmss} -\selectfont -\makeatother -\begin{document} -% This is for \LyX - - -\newcommand{\bfrac}[2]{\frac{#1 }{#2 }} - - - -\newcommand{\nth}{^{\textrm{th}}} - - - -\newcommand{\R}{R} - - - -\newcommand{\N}{N} - - - -\newcommand{\Z}{Z} - - - -\newcommand{\tra}{^{T}} - - - -\newcommand{\xx}{\mathbf{x}} - - -% This is for \LaTeX - -\fontfamily{cmss}\selectfont - -\renewcommand{\R}{{\mathds{R}}} - -\renewcommand{\N}{{\mathds{N}}} - -\renewcommand{\Z}{{\mathds{Z}}} - -\renewcommand{\tra}{^{\top}} - -\renewcommand{\bfrac}[2]{\frac{{\textstyle #1 }}{{\textstyle #2 }}} - - -\title{Mini-HOWTO on using Octave for Unconstrained Nonlinear Optimization% -\thanks{Author : Etienne Grossmann \texttt{<etienne@isr.ist.utl.pt>} (soon -replaced by {}``Octave-Forge developers''?). 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.\protect \\ -.~~~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. -}} - -\maketitle -\begin{comment} -Keywords: nonlinear optimization, octave, tutorial, Nelder-Mead, Conjugate -Gradient, Levenberg-Marquardt -\end{comment} -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. - -All the algorithms used below return numerical approximations of \emph{local -minima} of the optimized function. In the following examples, we minimize -a function with a single minimum (Figure~\ref{fig:function}), which -is relatively easily found. In practice, success of optimization algorithms -greatly depend on the optimized function and on the starting point. - - -\section*{\fontfamily{cmss} \selectfont A simple example} - - -\begin{figure} -{\centering \raisebox{6mm}{\resizebox*{0.3\textwidth}{!}{\includegraphics{figures/2D_slice-3.eps2}} }~\resizebox*{0.5\textwidth}{!}{\includegraphics{figures/optim_tutorial_slice.eps}} \par} - - -\caption{\label{fig:function} 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{figure} - - -We will use a call of the type - -\begin{lyxcode} -{[}x\_best,~best\_value,~niter{]}~=~minimize~(func,~x\_init) -\end{lyxcode} -to find the minimum of \[ -\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}\] - - -The following commands should find a local minimum of \( f() \), -using the Nelder-Mead (aka {}``downhill simplex'') algorithm and -starting from a randomly chosen point \texttt{x0}~: - -\begin{lyxcode} -function~cost~=~foo~(xx) - -~~xx-{}-;~~ - -~~cost~=~sum~(-cos(xx)+xx.\textasciicircum{}2/9); - -endfunction - -x0~=~{[}-1,~3,~-2{]}; - -{[}x,v,n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0) -\end{lyxcode} -The output should look like~: - -\begin{lyxcode} -x~= - -~~1.00000~1.00000~1.00000 - - - -v~=~-3.0000 - -n~=~248 -\end{lyxcode} -This means that a minimum has been found in \( \left( 1,1,1\right) \) -and that the value at that point is \( -3 \). This is correct, since -all the points of the form \( x_{1}=1+2i\pi ,\, x_{2}=1+2j\pi ,\, x_{3}=1+2k\pi \), -for some \( i,j,k\in \N \), minimize \( f() \). 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 \texttt{x0}. - -The Nelder-Mead algorithm is quite robust, but unfortunately it is -not very efficient. For high-dimensional problems, its execution time -may become prohibitive. - - -\section*{\fontfamily{cmss} \selectfont Using the first differential} - -Fortunately, when a function, like \( f() \) above, is differentiable, -more efficient optimization algorithms can be used. If \texttt{minimize()} -is given the differential of the optimized function, using the \texttt{\char`\"{}df\char`\"{}} -option, it will use a conjugate gradient method. - -\begin{lyxcode} -\#\#~Function~returning~partial~derivatives - -function~dc~=~diffoo~(x) - -~~~~x~=~x(:)'~-~1; - -~~~~dc~=~sin~(x)~+~2{*}x/9; - -endfunction - -{[}x,~v,~n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}df\char`\"{},~\char`\"{}diffoo\char`\"{}) -\end{lyxcode} -This produces the output~: - -\begin{lyxcode} -x~= - -~~1.00000~1.00000~1.00000 - -v~=~-3~ - -n~= - -~~108~6 -\end{lyxcode} -The same minimum has been found, but only 108 function evaluations -were needed, together with 6 evaluations of the differential. Here, -\texttt{diffoo()} takes the same argument as \texttt{foo()} and returns -the partial derivatives of \( f() \) 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 \( i\nth \) element of \texttt{diffoo(x)} -is the partial derivative of \( f() \) with respect to \( x_{i} \) -. - - -\section*{\fontfamily{cmss} \selectfont Using numerical approximations of -the first differential} - -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 \texttt{\char`\"{}ndiff\char`\"{}} -option of \texttt{minimize()} 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~: - -\begin{lyxcode} -{[}x,~v,~n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}ndiff\char`\"{}) -\end{lyxcode} -wich yields~: - -\begin{lyxcode} -x~= - -~~1.00000~1.00000~1.00000 - -v~=~-3~ - -n~= - -~~78~6 -\end{lyxcode} -Note that each time the differential is numerically approximated, -\texttt{foo()} is called 6 times (twice per input element), so that -\texttt{foo()} is evaluated a total of (78+6{*}6=) 114 times in this -example. - - -\section*{\fontfamily{cmss} \selectfont Using the first and second differentials} - -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 -\texttt{\char`\"{}d2f\char`\"{}} allows to specify a function that -returns the value of the function, the first and second differentials -of the minimized function. Entering the commands~: - -\begin{lyxcode} -function~{[}c,~dc,~d2c{]}~=~d2foo~(x) - -~~~~c~=~foo(x); - -~~~~dc~=~diffoo(x); - -~~~~d2c~=~diag~(cos~(x(:)-1)~+~2/9); - -end - -{[}x,v,n{]}~=~minimize~(\char`\"{}foo\char`\"{},~x0,~\char`\"{}d2f\char`\"{},~\char`\"{}d2foo\char`\"{})~ -\end{lyxcode} -produces the output~: - -\begin{lyxcode} -x~= - -~~1.0000~1.0000~1.0000 - -v~=~-3 - -n~= - -~~34~5 -\end{lyxcode} -This time, 34 function evaluations, and 5 evaluations of \texttt{d2foo()} -were needed. - - -\section*{\fontfamily{cmss} \selectfont Summary} - -We have just seen the most basic ways of solving nonlinear unconstrained -optimization problems. The online help system of Octave (try e.g. -{}``\texttt{help minimize}'') will yield information on other issues, -such as \emph{passing extra arguments} to the minimized function, -\emph{controling the termination} of the optimization process, choosing -the algorithm etc. - -\begin{lyxcode} -\end{lyxcode} - -\end{document}