Mercurial > hg > octave-lyh
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 +++ b/doc/ChangeLog @@ -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 +++ b/doc/interpreter/octave.texi @@ -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 +++ b/doc/interpreter/optim.txi @@ -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 +++ b/doc/interpreter/quad.txi @@ -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 +++ b/doc/interpreter/set.txi @@ -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 +++ b/scripts/ChangeLog @@ -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 +++ b/scripts/general/cumtrapz.m @@ -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 +++ b/scripts/optimization/glpk.m @@ -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 +++ b/scripts/optimization/qp.m @@ -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 +++ b/scripts/optimization/sqp.m @@ -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 +++ b/src/DLD-FUNCTIONS/quad.cc @@ -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;