mmin_constr.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2006-2017, Andrew W. Steiner
5 
6  This file is part of O2scl.
7 
8  O2scl is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version.
12 
13  O2scl is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
20 
21  -------------------------------------------------------------------
22 */
23 /*------------------------------------------------------------------------*
24  * Open Optimization Library - Constrained Minimization
25  *
26  * tools/tools_diff.c
27  *
28  * This program is free software; you can redistribute it and/or modify
29  * it under the terms of the GNU General Public License as published by
30  * the Free Software Foundation; either version 2 of the License, or (at
31  * your option) any later version.
32  *
33  * This program is distributed in the hope that it will be useful, but
34  * WITHOUT ANY WARRANTY; without even the implied warranty of
35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
36  * General Public License for more details.
37  *
38  * You should have received a copy of the GNU General Public License
39  * along with this program; if not, write to the Free Software
40  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
41  *
42  * since: May, 23, 2004
43  *
44  * $Id: tools_diff.c,v 1.2 2004/06/04 21:26:23 akiles Exp $
45  *------------------------------------------------------------------------*/
46 #ifndef O2SCL_OOL_CONSTR_MMIN_H
47 #define O2SCL_OOL_CONSTR_MMIN_H
48 
49 /** \file mmin_constr.h
50  \brief File defining \ref o2scl::mmin_constr and associated function
51  objects
52 */
53 #include <o2scl/multi_funct.h>
54 #include <o2scl/mmin.h>
55 #include <o2scl/vector.h>
56 
57 #ifndef DOXYGEN_NO_O2NS
58 namespace o2scl {
59 #endif
60 
61  /** \brief Hessian product function for \ref o2scl::mmin_constr
62  */
63  typedef std::function<int
67 
68  /** \brief Constrained multidimensional minimization (OOL) [abstract base]
69 
70  \future Implement automatic computations of \gradient and Hessian
71  \future Construct a more difficult example for the "examples" directory
72  \future Finish mmin() interface
73  \future Implement a direct computation of the hessian as the
74  jacobian of the gradient
75  */
76  template<class func_t, class dfunc_t=func_t,
77  class hfunc_t=func_t, class vec_t=boost::numeric::ublas::vector<double> >
78  class mmin_constr : public mmin_base<func_t,dfunc_t,vec_t> {
79 
80  public:
81 
82 #ifndef DOXYGEN_INTERNAL
83 
84  protected:
85 
86  /// The current function value
87  double f;
88  /// Desc
89  double size;
90 
91  /// The current minimum vector
92  vec_t x;
93  /// The current gradient vector
94  vec_t gradient;
95  /// Desc
96  vec_t dx;
97 
98  /// Number of function evaluations
99  size_t fcount;
100  /// Number of gradient evaluations
101  size_t gcount;
102  /// Number of Hessian evaluations
103  size_t hcount;
104 
105  /// Number of parameters
106  size_t dim;
107  /// Number of constraints
108  size_t nconstr;
109  /// User-supplied function
110  func_t *func;
111  /// Gradient function
112  dfunc_t *dfunc;
113  /// Hessian function
114  hfunc_t *hfunc;
115 
116  /// Lower bound constraints
117  vec_t L;
118  /// Upper bound constraints
119  vec_t U;
120 
121  /// If true, the algorithm requires the hessian vector product
123 
124  /// Shrink vector \c V from the full to the reduced space
125  void shrink(const size_t nind, gsl_vector_uint *Ind,
126  const vec_t &V) {
127  size_t ii, indii;
128 
129  for( ii = 0; ii < nind; ii++ ) {
130  indii = gsl_vector_uint_get(Ind,ii);
131 
132  double tmp=V[ii];
133  V[ii]=V[indii];
134  V[indii]=tmp;
135  }
136  }
137 
138  /// Expand vector \c V from the reduced to the full space
139  void expand(const size_t nind, gsl_vector_uint *Ind,
140  const vec_t &V) {
141 
142  size_t jj, ii, indii;
143 
144  ii = nind;
145  for( jj = 0; jj < nind; jj++ ) {
146  ii--;
147  indii = gsl_vector_uint_get( Ind, ii );
148 
149  double tmp=V[ii];
150  V[ii]=V[indii];
151  V[indii]=tmp;
152  }
153  }
154 
155  /// Evaluate the objective function from the reduced space
156  double calc_f(const size_t nind, gsl_vector_uint *Ind,
157  vec_t &X, vec_t &Xc) {
158 
159  const size_t missing=this->dim-nind;
160  double ftmp;
161 
162  if (missing>0) {
163 
164  // Complete X with values from Xc
165  for(size_t i=nind;i<nind+missing;i++) {
166  X[i]=Xc[i];
167  }
168 
169  // Expand to full space
170  expand(nind,Ind,X);
171  }
172 
173  // Compute f
174  func(dim,X,ftmp);
175 
176  if(missing>0) {
177  // Shrink to reduced space
178  shrink(nind,Ind,X);
179  }
180 
181  return f;
182  }
183 
184  /// Compute gradient in the reduced space
185  int calc_g(const size_t nind, gsl_vector_uint *Ind, vec_t &X,
186  vec_t &Xc, vec_t &G) {
187 
188  const size_t missing=this->dim-nind;
189 
190  if( missing > 0 ) {
191 
192  // Complete X with values from Xc
193  for(size_t i=nind;i<nind+missing;i++) {
194  X[i]=Xc[i];
195  }
196 
197  // Expand to full space
198  expand(nind,Ind,X);
199  }
200 
201  // Compute gradient
202  dfunc_t(dim,X,G);
203 
204  if (missing>0) {
205  // Shrink to reduced space
206  shrink(nind,Ind,X);
207  shrink(nind,Ind,G);
208  }
209 
210  return 0;
211  }
212 
213  /// Evaluate a hessian times a vector from the reduced space
214  int calc_Hv(const size_t nind, gsl_vector_uint *Ind,
215  vec_t &X, vec_t &Xc, vec_t &V, vec_t &Hv) {
216 
217  const size_t missing=this->ndim-nind;
218 
219  if (missing>0) {
220  // Complete X with values from Xc and set V to zero
221  for(size_t i=nind;i<nind+missing;i++) {
222  X[i]=Xc[i];
223  V[i]=0.0;
224  }
225  /// Expand to full space
226  expand(nind,Ind,X);
227  expand(nind,Ind,V);
228  }
229 
230  // Compute gradient
231  hfunc(this->dim,X,V,Hv);
232 
233  if (missing>0) {
234  // Shrink to reduced space
235  shrink(nind,Ind,X);
236  shrink(nind,Ind,V);
237  shrink(nind,Ind,Hv);
238  }
239 
240  return 0;
241  }
242 
243 #endif
244 
245  public:
246 
247  mmin_constr() {
248  dim=0;
249  nconstr=0;
250  requires_hess=false;
251  }
252 
253  virtual ~mmin_constr() {
254  }
255 
256  /// Allocate memory
257  virtual int allocate(const size_t n) {
258  int status;
259 
260  x.resize(n);
261  gradient.resize(n);
262  dx.resize(n);
263  dim=n;
264 
265  for(size_t i=0;i<n;i++) {
266  x[i]=0.0;
267  gradient[i]=0.0;
268  dx[i]=0.0;
269  }
270 
271  return 0;
272  }
273 
274  /// Restart the minimizer
275  virtual int restart() {
276 
277  // Reset dx vector
278  for(size_t i=0;i<dim;i++) dx[i]=0.0;
279 
280  // Restart evaluation counters
281  fcount = 0;
282  gcount = 0;
283  hcount = 0;
284 
285  return 0;
286  }
287 
288  /// Set the function, the gradient, and the initial guess
289  virtual int set(func_t &fn, dfunc_t &dfn, vec_t &init) {
290 
291  o2scl::vector_copy(dim,init,x);
292  for(size_t i=0;i<dim;i++) dx[i]=0.0;
293 
294  func=&fn;
295  dfunc=&dfn;
296 
297  // Start evaluation conunters
298  fcount = 0;
299  gcount = 0;
300  hcount = 0;
301 
302  return 0;
303  }
304 
305  /** \brief Set the function, the gradient, the Hessian product,
306  and the initial guess
307  */
308  virtual int set_hess(func_t &fn, dfunc_t &dfn, hfunc_t &hfn,
309  vec_t &init) {
310 
311  o2scl::vector_copy(dim,init,x);
312  for(size_t i=0;i<dim;i++) dx[i]=0.0;
313 
314  func=&fn;
315  dfunc=&dfn;
316  hfunc=&hfn;
317 
318  // Start evaluation conunters
319  fcount = 0;
320  gcount = 0;
321  hcount = 0;
322 
323  return 0;
324  }
325 
326  /// Set the constraints
327  virtual int set_constraints(size_t nc, vec_t &lower, vec_t &upper) {
328  L.resize(nc);
329  U.resize(nc);
330  nconstr=nc;
331  o2scl::vector_copy(nc,lower,L);
332  o2scl::vector_copy(nc,upper,U);
333  return 0;
334  }
335 
336  /// Perform an iteration
337  virtual int iterate()=0;
338 
339  /// See if we're finished
340  virtual int is_optimal()=0;
341 
342  /** \brief Calculate the minimum \c min of \c func w.r.t. the
343  array \c x of size \c nvar.
344 
345  \note This is unimplemented.
346  */
347  virtual int mmin(size_t nvar, vec_t &xx, double &fmin,
348  func_t &ff)
349  {
350  O2SCL_ERR("Not yet implemented mmin_constr::mmin().",
351  exc_eunimpl);
352  return exc_eunimpl;
353  }
354 
355  /** \brief Calculate the minimum \c min of \c ff
356  w.r.t. the array \c x of size \c nvar with gradient
357  \c df and hessian vector product \c hf
358  */
359  virtual int mmin_hess(size_t nvar, vec_t &xx, double &fmin,
360  func_t &ff, dfunc_t &df, hfunc_t &hf)
361  {
362 
363  int status;
364  allocate(nvar);
365  if (requires_hess) set_hess(ff,df,hf,xx);
366  else set(ff,df,xx);
367  int it=0;
368  do {
369  status=iterate();
370  status=is_optimal();
371  it++;
372  } while (it<this->ntrial && status==gsl_continue);
373 
374  for(size_t i=0;i<nvar;i++) xx[i]=this->x[i];
375  fmin=this->f;
376  this->last_ntrial=it;
377 
378  return 0;
379  }
380 
381  /** \brief Calculate the minimum \c min of \c func
382  w.r.t. the array \c x of size \c nvar with gradient
383  \c dfunc
384  */
385  virtual int mmin_de(size_t nvar, vec_t &xx, double &fmin,
386  func_t &ff, dfunc_t &df) {
387 
388  int status;
389  allocate(nvar);
390  set(ff,df,xx);
391  int it=0;
392  do {
393  status=iterate();
394  status=is_optimal();
395  it++;
396  } while (it<this->ntrial && status==gsl_continue);
397 
398  for(size_t i=0;i<nvar;i++) xx[i]=this->x[i];
399  fmin=this->f;
400  this->last_ntrial=it;
401 
402  return 0;
403  }
404 
405  /// Return string denoting type ("mmin_constr")
406  const char *type() { return "mmin_constr"; }
407 
408 #ifndef DOXYGEN_INTERNAL
409 
410  private:
411 
415  (const mmin_constr<func_t,dfunc_t,hfunc_t,vec_t>&);
416 
417 #endif
418 
419  };
420 
421 #ifndef DOXYGEN_NO_O2NS
422 }
423 #endif
424 
425 #endif
426 
virtual int mmin_hess(size_t nvar, vec_t &xx, double &fmin, func_t &ff, dfunc_t &df, hfunc_t &hf)
Calculate the minimum min of ff w.r.t. the array x of size nvar with gradient df and hessian vector p...
Definition: mmin_constr.h:359
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
size_t dim
Number of parameters.
Definition: mmin_constr.h:106
const char * type()
Return string denoting type ("mmin_constr")
Definition: mmin_constr.h:406
virtual int is_optimal()=0
See if we&#39;re finished.
vec_t L
Lower bound constraints.
Definition: mmin_constr.h:117
virtual int restart()
Restart the minimizer.
Definition: mmin_constr.h:275
dfunc_t * dfunc
Gradient function.
Definition: mmin_constr.h:112
iteration has not converged
Definition: err_hnd.h:51
double f
The current function value.
Definition: mmin_constr.h:87
requested feature not (yet) implemented
Definition: err_hnd.h:99
size_t gcount
Number of gradient evaluations.
Definition: mmin_constr.h:101
double calc_f(const size_t nind, gsl_vector_uint *Ind, vec_t &X, vec_t &Xc)
Evaluate the objective function from the reduced space.
Definition: mmin_constr.h:156
vec_t dx
Desc.
Definition: mmin_constr.h:96
virtual int mmin(size_t nvar, vec_t &xx, double &fmin, func_t &ff)
Calculate the minimum min of func w.r.t. the array x of size nvar.
Definition: mmin_constr.h:347
vec_t x
The current minimum vector.
Definition: mmin_constr.h:92
Constrained multidimensional minimization (OOL) [abstract base].
Definition: mmin_constr.h:78
virtual int iterate()=0
Perform an iteration.
void vector_copy(const vec_t &src, vec2_t &dest)
Simple vector copy.
Definition: vector.h:127
Multidimensional minimization [abstract base].
Definition: mmin.h:164
size_t fcount
Number of function evaluations.
Definition: mmin_constr.h:99
virtual int set_constraints(size_t nc, vec_t &lower, vec_t &upper)
Set the constraints.
Definition: mmin_constr.h:327
func_t * func
User-supplied function.
Definition: mmin_constr.h:110
void shrink(const size_t nind, gsl_vector_uint *Ind, const vec_t &V)
Shrink vector V from the full to the reduced space.
Definition: mmin_constr.h:125
void expand(const size_t nind, gsl_vector_uint *Ind, const vec_t &V)
Expand vector V from the reduced to the full space.
Definition: mmin_constr.h:139
size_t nconstr
Number of constraints.
Definition: mmin_constr.h:108
hfunc_t * hfunc
Hessian function.
Definition: mmin_constr.h:114
#define O2SCL_ERR(d, n)
Set an error with message d and code n.
Definition: err_hnd.h:273
int last_ntrial
The number of iterations for in the most recent minimization.
Definition: mmin.h:206
bool requires_hess
If true, the algorithm requires the hessian vector product.
Definition: mmin_constr.h:122
virtual int set_hess(func_t &fn, dfunc_t &dfn, hfunc_t &hfn, vec_t &init)
Set the function, the gradient, the Hessian product, and the initial guess.
Definition: mmin_constr.h:308
vec_t U
Upper bound constraints.
Definition: mmin_constr.h:119
int calc_Hv(const size_t nind, gsl_vector_uint *Ind, vec_t &X, vec_t &Xc, vec_t &V, vec_t &Hv)
Evaluate a hessian times a vector from the reduced space.
Definition: mmin_constr.h:214
std::function< int(size_t, const boost::numeric::ublas::vector< double > &, const boost::numeric::ublas::vector< double > &, boost::numeric::ublas::vector< double > &)> ool_hfunct11
Hessian product function for o2scl::mmin_constr.
Definition: mmin_constr.h:66
virtual int allocate(const size_t n)
Allocate memory.
Definition: mmin_constr.h:257
double size
Desc.
Definition: mmin_constr.h:89
int calc_g(const size_t nind, gsl_vector_uint *Ind, vec_t &X, vec_t &Xc, vec_t &G)
Compute gradient in the reduced space.
Definition: mmin_constr.h:185
virtual int mmin_de(size_t nvar, vec_t &xx, double &fmin, func_t &ff, dfunc_t &df)
Calculate the minimum min of func w.r.t. the array x of size nvar with gradient dfunc.
Definition: mmin_constr.h:385
size_t hcount
Number of Hessian evaluations.
Definition: mmin_constr.h:103
vec_t gradient
The current gradient vector.
Definition: mmin_constr.h:94
int ntrial
Maximum number of iterations.
Definition: mmin.h:197

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).