changeset 6741:00116015904d

[project @ 2007-06-18 16:07:14 by jwe]
author jwe
date Mon, 18 Jun 2007 16:07:14 +0000
parents 605ea655366d
children ebf96cc00ee9
files doc/ChangeLog doc/interpreter/octave.texi doc/interpreter/optim.txi doc/interpreter/quad.txi doc/interpreter/set.txi scripts/ChangeLog scripts/general/cumtrapz.m scripts/optimization/glpk.m scripts/optimization/qp.m scripts/optimization/sqp.m src/DLD-FUNCTIONS/quad.cc
diffstat 11 files changed, 336 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
--- a/doc/ChangeLog	Sat Jun 16 15:51:49 2007 +0000
+++ b/doc/ChangeLog	Mon Jun 18 16:07:14 2007 +0000
@@ -1,3 +1,11 @@
+2007-06-18  Søren Hauberg  <hauberg@gmail.com>
+
+        * interpreter/optim.txi: Added some introductory text to each
+	section.
+
+        * interpreter/set.txi: Added some introductory text.
+        * interpreter/octave.texi: Updated to reflect changes in set.txi.
+
 2007-06-15  David Bateman  <dbateman@free.fr>
 
 	* faq/Octave-FAQ.texi: Document the gnuplot 4.2 bug using pipes.
--- a/doc/interpreter/octave.texi	Sat Jun 16 15:51:49 2007 +0000
+++ b/doc/interpreter/octave.texi	Mon Jun 18 16:07:14 2007 +0000
@@ -149,7 +149,7 @@
 * Linear Algebra::              
 * Nonlinear Equations::         
 * Sparse Matrices::
-* Quadrature::                  
+* Numerical Integration::                  
 * Differential Equations::      
 * Optimization::                
 * Statistics::                  
@@ -413,10 +413,11 @@
 * Iterative Techniques::
 * Real Life Example::
 
-Quadrature
+Numerical Integration
 
 * Functions of One Variable::   
 * Orthogonal Collocation::      
+* Functions of Multiple Variables:: 
 
 Differential Equations
 
@@ -436,6 +437,10 @@
 * Models::                      
 * Distributions::               
 
+Sets
+
+* Set Operations::
+
 Interpolation
 * One-dimensional Interpolation::
 * Multi-dimensional Interpolation::
--- a/doc/interpreter/optim.txi	Sat Jun 16 15:51:49 2007 +0000
+++ b/doc/interpreter/optim.txi	Mon Jun 18 16:07:14 2007 +0000
@@ -5,6 +5,11 @@
 @node Optimization
 @chapter Optimization
 
+Octave comes with support for solving various kinds of optimization
+problems. Specifically Octave can solve problems in Linear Programming,
+Quadratic Programming, Nonlinear Programming, and Linear Least Squares
+Minimization.
+
 @menu
 * Linear Programming::       
 * Quadratic Programming::       
@@ -23,21 +28,98 @@
 @node Linear Programming
 @section Linear Programming
 
+Octave can solve Linear Programming problems using the @code{glpk}
+function.  That is, Octave can solve
+
+@iftex
+@tex
+$$
+  \min_x c^T x
+$$
+@end tex
+@end iftex
+@ifnottex
+@example
+min C'*x
+@end example
+@end ifnottex
+subject to the linear constraints
+@iftex
+@tex
+$Ax = b$ where $x \geq 0$.
+@end tex
+@end iftex
+@ifnottex
+@math{A*x = b} where @math{x >= 0}.
+@end ifnottex
+
+@noindent
+The @code{glpk} function also supports variations of this problem.
+
 @DOCSTRING(glpk)
 
 @node Quadratic Programming
 @section Quadratic Programming
 
+Octave can also solve Quadratic Programming problems, this is
+@iftex
+@tex
+$$
+ \min_x {1 \over 2} x^T H x + x^T q
+$$
+@end tex
+@end iftex
+@ifnottex
+@example
+min 0.5 x'*H*x + x'*q
+@end example
+@end ifnottex
+subject to
+@iftex
+@tex
+$$
+ Ax = b \qquad lb \leq x \leq ub \qquad A_{lb} \leq A_{in} \leq A_{ub}
+$$
+@end tex
+@end iftex
+@ifnottex
+@example
+     A*x = b
+     lb <= x <= ub
+     A_lb <= A_in*x <= A_ub
+@end example
+@end ifnottex
+
 @DOCSTRING(qp)
 
 @node Nonlinear Programming
 @section Nonlinear Programming
 
+Octave can also perform general nonlinear minimization using a
+successive quadratic programming solver.
+
 @DOCSTRING(sqp)
 
 @node Linear Least Squares
 @section Linear Least Squares
 
+Octave also supports linear least squares minimization.  That is,
+Octave can find the parameter @math{b} such the the model
+@iftex
+@tex
+$y = xb$
+@end tex
+@end iftex
+@ifnottex
+@math{y = x*b}
+@end ifnottex
+fits data @math{(x,y)} as good as possible, assuming zero-mean
+Gaussian noise.  If the noise is assumed to be isotropic the problem
+can be solved using the @samp{\} or @samp{/} operators, or the @code{ols}
+function.  In the general case where the noise is assumed to be anisotropic
+the @code{gls} is needed.
+
+@DOCSTRING(ols)
+
 @DOCSTRING(gls)
 
-@DOCSTRING(ols)
--- a/doc/interpreter/quad.txi	Sat Jun 16 15:51:49 2007 +0000
+++ b/doc/interpreter/quad.txi	Mon Jun 18 16:07:14 2007 +0000
@@ -2,17 +2,49 @@
 @c This is part of the Octave manual.
 @c For copying conditions, see the file gpl.texi.
 
-@node Quadrature
-@chapter Quadrature
+@node Numerical Integration
+@chapter Numerical Integration
+
+Octave comes with several built-in functions for computing the integral
+of a function numerically.  These functions all solve 1-dimensional
+integration problems.
 
 @menu
-* Functions of One Variable::   
+* Functions of One Variable:: 
+* Functions of Multiple Variables:: 
 * Orthogonal Collocation::      
 @end menu
 
 @node Functions of One Variable
 @section Functions of One Variable
 
+Octave supports three different algorithms for computing the integral
+@iftex
+@tex
+$$
+ \int_a^b f(x) d x
+$$
+@end tex
+@end iftex
+of a function @math{f} over the interval from @math{a} to @math{b}.
+These are
+
+@table @code
+@item quad
+Numerical integration based on Gaussian quadrature.
+
+@item quadl
+Numerical integration using an adaptive Lobatto rule.
+
+@item trapz
+Numerical integration using the trapezodial method.
+@end table
+
+@noindent
+Besides these functions Octave also allows you to perform cumulative
+numerical integration using the trapezodial method through the
+@code{cumtrapz} function.
+
 @DOCSTRING(quad)
 
 @DOCSTRING(quad_options)
@@ -26,7 +58,7 @@
 from $x = 0$ to $x = 3$.
 @end tex
 @end iftex
-@ifinfo
+@ifnottex
 
 @example
   @var{f}(@var{x}) = @var{x} * sin (1/@var{x}) * sqrt (abs (1 - @var{x}))
@@ -34,7 +66,7 @@
 
 @noindent
 from @var{x} = 0 to @var{x} = 3.
-@end ifinfo
+@end ifnottex
 
 This is a fairly difficult integration (plot the function over the range
 of integration to see why).
@@ -89,10 +121,10 @@
 $u(0) = 0$ and $u(1) = 1$.
 @end tex
 @end iftex
-@ifinfo
+@ifnottex
 @var{u}' - @var{alpha} * @var{u}'' = 0 with the boundary conditions
 @var{u}(0) = 0 and @var{u}(1) = 1.
-@end ifinfo
+@end ifnottex
 
 First, we can generate the weight matrices for @var{n} points (including
 the endpoints of the interval), and incorporate the boundary conditions
@@ -102,9 +134,9 @@
 $\alpha$).
 @end tex
 @end iftex
-@ifinfo
+@ifnottex
 @var{alpha}).
-@end ifinfo
+@end ifnottex
 
 @example
 @group
@@ -123,3 +155,85 @@
 u = [ 0; (at - alpha * bt) \ rhs; 1]
      @result{} [ 0.00; 0.004; 0.01 0.00; 0.12; 0.62; 1.00 ]
 @end example
+
+@node Functions of Multiple Variables
+@section Functions of Multiple Variables
+
+Octave does not have built-in functions for computing the integral
+of functions of multiple variables.  It is however possible to compute
+the integral of a function of multiple variables using the functions
+for one-dimensional integrals.
+
+To illustrate how the integration can be performed, we will integrate
+the function
+@iftex
+@tex
+$$
+  f(x, y) = \sin(\pi x y)\sqrt{x y}
+$$
+@end tex
+@end iftex
+@ifnottex
+@example
+f(x, y) = sin(pi*x*y)*sqrt(x*y)
+@end example
+@end ifnottex
+for @math{x} and @math{y} between 0 and 1.
+
+The first approach creates a function that integrates @math{f} with
+respect to @math{x}, and then integrates that function with respect to
+@math{y}.  Since @code{quad} is written in Fortran it cannot be called
+recursively.  This means that @code{quad} cannot integrate a function
+that calls @code{quad}, and hence cannot be used to perform the double
+integration.  It is however possible with @code{quadl}, which is what
+the following code does.
+
+@example
+function I = g(y)
+  I = ones(1, length(y));
+  for i = 1:length(y)
+    f = @@(x) sin(pi.*x.*y(i)).*sqrt(x.*y(i));
+    I(i) = quadl(f, 0, 1);
+  endfor
+endfunction
+
+I = quadl("g", 0, 1)
+      @result{} 0.30022
+@end example
+
+The above mentioned approach works but is fairly slow, and that problem
+increases exponentially with the dimensionality the problem.  Another
+possible solution is to use Orthogonal Collocation as described in the
+previous section.  The integral of a function @math{f(x,y)} for
+@math{x} and @math{y} between 0 and 1 can be approximated using @math{n}
+points by
+@iftex
+@tex
+$$
+ \int_0^1 \int_0^1 f(x,y) d x d y \approx \sum_{i=1}^n \sum_{j=1}^n q_i q_j f(r_i, r_j),
+$$
+@end tex
+@end iftex
+@ifnottex
+the sum over @code{i=1:n} and @code{j=1:n} of @code{q(i)*q(j)*f(r(i),r(j))},
+@end ifnottex
+where @math{q} and @math{r} is as returned by @code{colloc(n)}.  The
+generalisation to more than two variables is straight forward.  The
+following code computes the studied integral using @math{n=7} points.
+
+@example
+f = @@(x,y) sin(pi*x*y').*sqrt(x*y');
+n = 7;
+[t, A, B, q] = colloc(n);
+I = q'*f(t,t)*q;
+      @result{} 0.30022
+@end example
+
+@noindent
+It should be noted that the number of points determines the quality
+of the approximation.  If the integration needs to be performed between
+@math{a} and @math{b} instead of 0 and 1, a change of variables is needed.
+
+
+
+
--- a/doc/interpreter/set.txi	Sat Jun 16 15:51:49 2007 +0000
+++ b/doc/interpreter/set.txi	Mon Jun 18 16:07:14 2007 +0000
@@ -6,13 +6,35 @@
 @chapter Sets
 
 Octave has a limited set of functions for managing sets of data, where a
-set is defined as a collection unique elements.
+set is defined as a collection unique elements.  In Octave a set is
+represented as a vector of numbers.
 
 @DOCSTRING(create_set)
 
-@DOCSTRING(ismember)
+@DOCSTRING(unique)
+
+@menu
+* Set Operations:: 
+@end menu
+
+@node Set Operations
+@section Set Operations
 
-@DOCSTRING(unique)
+Octave supports the basic set operations.  That is, Octave can compute
+the union, intersection, complement, and difference of two sets.
+Octave can also supports the @emph{Exclusive Or} set operation, and
+membership determination.  The functions for set operations all work in
+pretty much the same way.  As an example, assume that @code{x} and
+@code{y} contains two sets, then
+
+@example
+union(x, y)
+@end example
+
+@noindent
+computes the union of the two sets.
+
+@DOCSTRING(ismember)
 
 @DOCSTRING(union)
 
--- a/scripts/ChangeLog	Sat Jun 16 15:51:49 2007 +0000
+++ b/scripts/ChangeLog	Mon Jun 18 16:07:14 2007 +0000
@@ -1,3 +1,9 @@
+2007-06-18  Søren Hauberg  <hauberg@gmail.com>
+
+        * optimization/glpk.m: TeXified the help text.
+        * optimization/qp.m: TeXified the help text.
+        * optimization/sqp.m: TeXified the help text.
+
 2007-06-16  Søren Hauberg  <hauberg@gmail.com>
 
         * plot/legend.m: Replace 'vargin' with 'varargin'.
--- a/scripts/general/cumtrapz.m	Sat Jun 16 15:51:49 2007 +0000
+++ b/scripts/general/cumtrapz.m	Mon Jun 18 16:07:14 2007 +0000
@@ -23,9 +23,9 @@
 ## @deftypefnx {Function File} {@var{z} =} cumtrapz (@dots{}, @var{dim})
 ## 
 ## Cumulative numerical intergration using trapezodial method.
-## @code{trapz (@var{y})} computes the cummulative integral of the 
+## @code{cumtrapz (@var{y})} computes the cummulative integral of the 
 ## @var{y} along the first non singleton dimension. If the argument 
-## @var{x} is omitted a equally spaced vector is assumed. @code{trapz 
+## @var{x} is omitted a equally spaced vector is assumed. @code{cumtrapz 
 ## (@var{x}, @var{y})} evaluates the cummulative integral with respect 
 ## to @var{x}.
 ##  
--- a/scripts/optimization/glpk.m	Sat Jun 16 15:51:49 2007 +0000
+++ b/scripts/optimization/glpk.m	Mon Jun 18 16:07:14 2007 +0000
@@ -22,27 +22,62 @@
 ## Solve a linear program using the GNU GLPK library.  Given three
 ## arguments, @code{glpk} solves the following standard LP:
 ## 
+## @iftex
+## @tex
+## $$
+##   \min_x C^T x
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ## @example
 ## min C'*x
 ## @end example
+## @end ifnottex
 ## 
 ## subject to
 ## 
+## @iftex
+## @tex
+## $$
+##   Ax = b \qquad x \geq 0
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ## @example
 ## @group
 ## A*x  = b
 ##   x >= 0
 ## @end group
 ## @end example
+## @end ifnottex
 ## 
 ## but may also solve problems of the form
 ## 
+## @iftex
+## @tex
+## $$
+##   [ \min_x | \max_x ] C^T x
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ## @example
 ## [ min | max ] C'*x
 ## @end example
+## @end ifnottex
 ## 
 ## subject to
 ## 
+## @iftex
+## @tex
+## $$
+##  Ax [ = | \leq | \geq ] b \qquad  LB \leq x \leq UB
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ## @example
 ## @group
 ## A*x [ "=" | "<=" | ">=" ] b
@@ -50,6 +85,7 @@
 ##   x <= UB
 ## @end group
 ## @end example
+## @end ifnottex
 ## 
 ## Input arguments:
 ## 
--- a/scripts/optimization/qp.m	Sat Jun 16 15:51:49 2007 +0000
+++ b/scripts/optimization/qp.m	Mon Jun 18 16:07:14 2007 +0000
@@ -18,33 +18,39 @@
 ## 02110-1301, USA.
 
 ## -*- texinfo -*-
-## @deftypefn {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}, @var{A}, @var{b}, @var{lb}, @var{ub}, @var{A_lb}, @var{Ain}, @var{A_ub})
+## @deftypefn {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}, @var{A}, @var{b}, @var{lb}, @var{ub}, @var{A_lb}, @var{A_in}, @var{A_ub})
 ## Solve the quadratic program
-## @ifinfo
+## @iftex
+## @tex
+## $$
+##  \min_x {1 \over 2} x^T H x + x^T q
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ##
 ## @example
 ##      min 0.5 x'*H*x + x'*q
 ##       x
 ## @end example
 ##
-## @end ifinfo
+## @end ifnottex
+## subject to
 ## @iftex
 ## @tex
+## $$
+##  Ax = b \qquad lb \leq x \leq ub \qquad A_{lb} \leq A_{in} \leq A_{ub}
+## $$
 ## @end tex
 ## @end iftex
-## subject to
-## @ifinfo
+## @ifnottex
 ##
 ## @example
 ##      A*x = b
 ##      lb <= x <= ub
-##      A_lb <= Ain*x <= A_ub
+##      A_lb <= A_in*x <= A_ub
 ## @end example
-## @end ifinfo
-## @iftex
-## @tex
-## @end tex
-## @end iftex
+## @end ifnottex
 ##
 ## @noindent
 ## using a null-space active-set method.
--- a/scripts/optimization/sqp.m	Sat Jun 16 15:51:49 2007 +0000
+++ b/scripts/optimization/sqp.m	Mon Jun 18 16:07:14 2007 +0000
@@ -20,30 +20,36 @@
 ## -*- texinfo -*-
 ## @deftypefn {Function File} {[@var{x}, @var{obj}, @var{info}, @var{iter}, @var{nf}, @var{lambda}] =} sqp (@var{x}, @var{phi}, @var{g}, @var{h})
 ## Solve the nonlinear program
-## @ifinfo
+## @iftex
+## @tex
+## $$
+## \min_x \phi (x)
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ##
 ## @example
 ##      min phi (x)
 ##       x
 ## @end example
 ##
-## @end ifinfo
+## @end ifnottex
+## subject to
 ## @iftex
 ## @tex
+## $$
+##  g(x) = 0 \qquad h(x) \geq 0
+## $$
 ## @end tex
 ## @end iftex
-## subject to
-## @ifinfo
+## @ifnottex
 ##
 ## @example
 ##      g(x)  = 0
 ##      h(x) >= 0
 ## @end example
-## @end ifinfo
-## @iftex
-## @tex
-## @end tex
-## @end iftex
+## @end ifnottex
 ##
 ## @noindent
 ## using a successive quadratic programming method.
@@ -109,11 +115,22 @@
 ## function and the second should point to a function that computes the
 ## gradient of the constraint function:
 ##
+## @iftex
+## @tex
+## $$
+##  \Bigg( {\partial f(x) \over \partial x_1}, 
+##         {\partial f(x) \over \partial x_2}, \ldots,
+##         {\partial f(x) \over \partial x_N} \Bigg)^T
+## $$
+## @end tex
+## @end iftex
+## @ifnottex
 ## @example
 ##                 [ d f(x)   d f(x)        d f(x) ]
 ##     transpose ( [ ------   -----   ...   ------ ] )
 ##                 [  dx_1     dx_2          dx_N  ]
 ## @end example
+## @end ifnottex
 ##
 ## Here is an example of calling @code{sqp}:
 ##
--- a/src/DLD-FUNCTIONS/quad.cc	Sat Jun 16 15:51:49 2007 +0000
+++ b/src/DLD-FUNCTIONS/quad.cc	Mon Jun 18 16:07:14 2007 +0000
@@ -165,6 +165,9 @@
 \n\
 You can use the function @code{quad_options} to set optional\n\
 parameters for @code{quad}.\n\
+\n\
+It should be noted that since @code{quad} is written in Fortran it\n\
+cannot be called recursively.\n\
 @end deftypefn")
 {
   octave_value_list retval;