ʻOhana
Population structure, admixture history, and selection using learning methods.
jade.simplex.hpp
1 /* -------------------------------------------------------------------------
2  Ohana
3  Copyright (c) 2015-2020 Jade Cheng (\___/)
4  Jade Cheng <info@jade-cheng.com> (='.'=)
5  ------------------------------------------------------------------------- */
6 
7 #ifndef JADE_SIMPLEX_HPP__
8 #define JADE_SIMPLEX_HPP__
9 
10 #include "jade.assert.hpp"
11 
12 namespace jade
13 {
14  ///
15  /// A template for a class that implements the Nelder-Mead Simplex Method,
16  /// which attempts to minimize an objective function in a many-dimensional
17  /// space by continually refining a simplex.
18  ///
19  template <typename TValue>
21  {
22  public:
23  /// The value type.
24  typedef TValue value_type;
25 
26  /// The container type.
27  typedef std::vector<value_type> container_type;
28 
29  ///
30  /// An indication of what caused the execute to temrinate.
31  ///
33  {
34  ///
35  /// The exit condition.
36  ///
37  enum type
38  {
39  delta, ///< The minimum delta occurred.
40  epsilon, ///< The minimum epsilon occurred.
41  iteration, ///< The maximum iteration occurred.
42  length, ///< The minimum length occurred.
43  timeout ///< The maximum timeout occurred.
44  };
45 
46  ///
47  /// \return A string representation of the type.
48  ///
49  static const char * str(
50  const type value) ///< The type to format.
51  {
52  switch (value)
53  {
54  #define CASE(E) case E: return #E
55  CASE(delta);
56  CASE(epsilon);
57  CASE(iteration);
58  CASE(length);
59  CASE(timeout);
60  #undef CASE
61  }
62 
63  return nullptr;
64  }
65  };
66 
67  /// The exit condition type.
69 
70  ///
71  /// An operation performed during an iteration.
72  ///
73  struct operation
74  {
75  ///
76  /// The type of operation.
77  ///
78  enum type
79  {
80  expansion, ///< An expansion.
81  contraction_in, ///< An inside contraction.
82  contraction_out, ///< An outside contraction.
83  reflection, ///< A reflection.
84  shrinkage ///< A shrinkage.
85  };
86 
87  ///
88  /// \return A string representation of the type.
89  ///
90  static const char * str(
91  const type value) ///< The value to format.
92  {
93  switch (value)
94  {
95  #define CASE(E) case E: return #E
96  CASE(expansion);
97  CASE(contraction_in);
98  CASE(contraction_out);
99  CASE(reflection);
100  CASE(shrinkage);
101  #undef CASE
102  }
103 
104  return nullptr;
105  }
106  };
107 
108  /// The operation type.
109  typedef typename operation::type operation_type;
110 
111  ///
112  /// Arguments passed to the logging function.
113  ///
114  struct log_args
115  {
116  size_t iteration; ///< The completed iteration.
117  double second; ///< The seconds elapsed.
118  const basic_simplex * simplex; ///< The simplex instance.
119  void * user; ///< User-supplied value.
120 
121  ///
122  /// Initializes a new instance of the class.
123  ///
124  /// \param simplex_ The simplex generating the log event.
125  /// \param second_ The number of seconds elapsed.
126  /// \param iteration_ The completed iteration.
127  /// \param user_ The user-supplied value, or nullptr.
128  ///
129  inline log_args(
130  const basic_simplex * const simplex_,
131  const double second_,
132  const size_t iteration_,
133  void * const user_)
134  : iteration (iteration_)
135  , second (second_)
136  , simplex (simplex_)
137  , user (user_)
138  {
139  }
140 
141  ///
142  /// \return A string representation of the class.
143  ///
144  std::string str() const
145  {
146  std::ostringstream out;
147  out << "iteration: " << iteration << std::endl
148  << "second: " << second << std::endl;
149  return out.str();
150  }
151  };
152 
153  ///
154  /// Arguments to the execute method.
155  ///
157  {
158  /// The C-style log function.
159  typedef void (*logfunc_type)(const log_args &);
160 
161  /// The value assigned for no maximum iterations.
162  static constexpr auto no_max_iterations =
163  std::numeric_limits<size_t>::max();
164 
165  /// The value assigned for no maximum seconds.
166  static constexpr auto no_max_seconds =
167  std::numeric_limits<double>::quiet_NaN();
168 
169  /// The value assigned for no minimum delta.
170  static constexpr auto no_min_delta =
171  std::numeric_limits<value_type>::quiet_NaN();
172 
173  /// The value assigned for no minimum epsilon.
174  static constexpr auto no_min_epsilon =
175  std::numeric_limits<value_type>::quiet_NaN();
176 
177  /// The value assigned for no minimum length.
178  static constexpr auto no_min_length =
179  std::numeric_limits<value_type>::quiet_NaN();
180 
181  logfunc_type logfunc; ///< The logging function.
182  size_t max_iterations; ///< The maximum iterations.
183  double max_seconds; ///< The maximum seconds.
184  value_type min_delta; ///< The minimum delta.
185  value_type min_epsilon; ///< The minimum change in objval.
186  value_type min_length; ///< The minimum length.
187  void * user; ///< User-supplied value.
188 
189  ///
190  /// Initializes a new instance of the class.
191  ///
192  inline execute_args()
193  : logfunc (nullptr)
199  , user (nullptr)
200  {
201  }
202 
203  ///
204  /// \return True if the logging function is assigned.
205  ///
206  bool is_logfunc_assigned() const
207  {
208  return logfunc != nullptr;
209  }
210 
211  ///
212  /// \return True if the maximum iterations is assigned.
213  ///
215  {
217  }
218 
219  ///
220  /// \return True if the maximum seconds is assigned.
221  ///
223  {
224  return !std::isnan(max_seconds);
225  }
226 
227  ///
228  /// \return True if the minimum delta is assigned.
229  ///
231  {
232  return !std::isnan(min_delta);
233  }
234 
235  ///
236  /// \return True if the minimum epsilon is assigned.
237  ///
239  {
240  return !std::isnan(min_epsilon);
241  }
242 
243  ///
244  /// \return True if the minimum length is assigned.
245  ///
247  {
248  return !std::isnan(min_length);
249  }
250 
251  ///
252  /// \return A string representation of the class.
253  ///
254  std::string str() const
255  {
256  std::ostringstream out;
257  out << "logfunc: "
258  << _str(logfunc != nullptr, "assigned")
259  << std::endl
260  << "user: "
261  << _str(user != nullptr, "assigned")
262  << std::endl
263  << "max_iteration: "
265  << std::endl
266  << "max_second: "
268  << std::endl
269  << "min_delta: "
270  << _str(is_min_delta_assigned(), min_delta)
271  << std::endl
272  << "min_epsilon: "
274  << std::endl
275  << "min_length: "
277  << std::endl;
278  return out.str();
279  }
280 
281  private:
282  // ----------------------------------------------------------------
283  template <typename T>
284  static std::string _str(
285  const bool is_assigned,
286  const T value)
287  {
288  std::ostringstream out;
289  if (is_assigned) out << value;
290  else out << "<not-assigned>";
291  return out.str();
292  }
293  };
294 
295  ///
296  /// A data structure used to initialize the Nelder-Mead algorithm.
297  ///
298  /// The default values for rho, chi, gamma, and sigma are based on the
299  /// 2010 paper 'Implementing the Nelder-Mead simplex algorithm with
300  /// adaptive parameters' by Fuchang Gao and Lixing Han.
301  ///
302  struct options
303  {
304  ///
305  /// A vertex in the initial formation of the simplex.
306  ///
308 
309  ///
310  /// The expansion coefficient, which must be greater than the
311  /// larger or rho or 1.0.
312  ///
314 
315  ///
316  /// The contraction coefficient, which must be greater than 0.0 and
317  /// less than 1.0.
318  ///
320 
321  ///
322  /// The reflection coefficient, which must be greater than 0.0.
323  ///
325 
326  ///
327  /// The shrinkage coefficient, which must be greater than 0.0 and
328  /// less than 1.0.
329  ///
331 
332  ///
333  /// A scaling coefficient used to construct the unit vectors in each
334  /// dimension of the simplex, or undefined to use 1.0.
335  ///
337 
338  ///
339  /// Initializes a new instance of the class.
340  ///
341  explicit options(
342  const size_t n) ///< The container size.
343  : vertex ()
344  , chi (_init_chi(n))
345  , gamma (_init_gamma(n))
346  , rho (1)
347  , sigma (_init_sigma(n))
348  , unit (1)
349  {
350  assert(n > 0);
351  vertex.resize(n);
352  }
353 
354  ///
355  /// Initializes a new instance of the class.
356  ///
357  explicit options(
358  const container_type & vertex_) ///< The container size.
359  : vertex (vertex_)
360  , chi (_init_chi(vertex.size()))
361  , gamma (_init_gamma(vertex.size()))
362  , rho (1)
363  , sigma (_init_sigma(vertex.size()))
364  , unit (1)
365  {
366  assert(vertex.size() > 0);
367  }
368 
369  ///
370  /// \return A string representation of the class.
371  ///
372  std::string str() const
373  {
374  std::ostringstream out;
375 
376  out << "vertex: {";
377  auto iter = vertex.begin();
378  if (iter != vertex.end())
379  {
380  out << *iter;
381  while (++iter != vertex.end())
382  out << "," << *iter;
383  }
384  out << "}" << std::endl;
385 
386  out
387  << "chi: " << chi << std::endl
388  << "gamma: " << gamma << std::endl
389  << "rho: " << rho << std::endl
390  << "sigma: " << sigma << std::endl
391  << "unit: " << unit << std::endl;
392 
393  return out.str();
394  }
395 
396  private:
397  static constexpr value_type k1_00 = value_type(1.00);
398  static constexpr value_type k2_00 = value_type(2.00);
399  static constexpr value_type k0_50 = value_type(0.50);
400  static constexpr value_type k0_75 = value_type(0.75);
401 
402  // ----------------------------------------------------------------
403  static value_type _init_chi(const size_t n)
404  {
405  return n >= 2 ? k1_00 + (k2_00 / value_type(n)) : k2_00;
406  }
407 
408  // ----------------------------------------------------------------
409  static value_type _init_gamma(const size_t n)
410  {
411  return n >= 2 ? k0_75 - (k1_00 /
412  (k2_00 * value_type(n))) : k0_50;
413  }
414 
415  // ----------------------------------------------------------------
416  static value_type _init_sigma(const size_t n)
417  {
418  return n >= 2 ? k1_00 - (k1_00 / value_type(n)) : k0_50;
419  }
420  };
421 
422  ///
423  /// Statistics about the behavior of the algorithm.
424  ///
425  struct stats
426  {
427  ///
428  /// The number of expansions that have occurred.
429  ///
430  size_t expansions;
431 
432  ///
433  /// The number of evaluations of the objective function.
434  ///
435  size_t evaluations;
436 
437  ///
438  /// The number of inside contractions that have occurred.
439  ///
441 
442  ///
443  /// The number of outside contractions that have occurred.
444  ///
446 
447  ///
448  /// The number of iterations that have executed.
449  ///
450  size_t iterations;
451 
452  ///
453  /// The number of reflections that have occurred.
454  ///
455  size_t reflections;
456 
457  ///
458  /// The number of shrinkages that have occurred.
459  ///
460  size_t shrinkages;
461 
462  ///
463  /// Initializes a new instance of the class.
464  ///
465  inline stats()
466  : expansions (0)
467  , evaluations (0)
468  , contractions_in (0)
469  , contractions_out (0)
470  , iterations (0)
471  , reflections (0)
472  , shrinkages (0)
473  {
474  }
475 
476  ///
477  /// \return A string representation of the class.
478  ///
479  std::string str() const
480  {
481  std::ostringstream out;
482  out << "evaluations: " << evaluations << std::endl
483  << "iterations: " << iterations << std::endl
484  << "reflections: " << reflections << std::endl
485  << "expansions: " << expansions << std::endl
486  << "contractions_in: " << contractions_in << std::endl
487  << "contractions_out: " << contractions_out << std::endl
488  << "shrinkages: " << shrinkages << std::endl;
489  return out.str();
490  }
491  };
492 
493  ///
494  /// Initializes a new instance of the class based on the specified
495  /// required values.
496  ///
497  template <typename TObjfunc>
499  const TObjfunc objfunc, ///< The objective function.
500  const size_t n) ///< The number of dimensions.
501  : basic_simplex(objfunc, options(n))
502  {
503  }
504 
505  ///
506  /// Initializes a new instance of the class based on the specified
507  /// options.
508  ///
509  template <typename TObjfunc>
511  const TObjfunc objfunc, ///< The objective function.
512  const options & opts) ///< The options.
513  : _n (opts.vertex.size())
514  , _opts (opts)
515  , _stats ()
516  , _x ()
517  , _xbar ()
518  , _xr ()
519  , _xc ()
520  , _xcc ()
521  , _xe ()
522  {
523  assert(_n > 0);
524 
525  assert(opts.rho > 0);
526  assert(opts.chi >= 1 && opts.chi >= opts.rho);
527  assert(opts.gamma > 0 && opts.gamma < 1);
528  assert(opts.sigma > 0 && opts.sigma < 1);
529  assert(opts.unit > 0);
530  assert(opts.vertex.empty() || opts.vertex.size() == _n);
531 
532  //
533  // Add N+1 vertices with N of them offset from the initial vertex by
534  // one unit in a dimension corresponding to their index.
535  //
536  for (size_t i = 0; i <= _n; i++)
537  _x.emplace_back(new vertex(opts, i));
538 
539  //
540  // Initially evaluate the objective function for the simplex.
541  //
542  for (const auto & xi : _x)
543  xi->objval = _evaluate(objfunc, xi->params);
544 
545  //
546  // Initially sort the vertices.
547  //
548  std::sort(_x.begin(), _x.end(), _is_less);
549 
550  //
551  // Declare vertices here to avoid memory allocations while
552  // iterating.
553  //
554  _xbar.resize(_n);
555  _xr.resize(_n);
556  _xc.resize(_n);
557  _xcc.resize(_n);
558  _xe.resize(_n);
559  }
560 
561  ///
562  /// Calls the iterate method until an exit condition is reached.
563  ///
564  /// \return The exit condition.
565  ///
566  template <typename TObjfunc>
568  const TObjfunc objfunc, ///< The objective function.
569  const execute_args & exe_args) ///< The execution arguments.
570  {
571  typedef std::chrono::high_resolution_clock clock_type;
572  typedef std::chrono::duration<double> duration_type;
573 
574  const auto t0 = clock_type::now();
575  const auto get_seconds = [t0]() -> double
576  {
577  return duration_type(clock_type::now() - t0).count();
578  };
579 
580  auto iteration = size_t(0);
581  auto flux0 = get_flux();
582 
583  for (;;)
584  {
585  if (exe_args.is_max_iterations_assigned())
586  if (iteration >= exe_args.max_iterations)
587  return exit_condition_type::iteration;
588 
589  if (exe_args.is_max_seconds_assigned())
590  if (get_seconds() >= exe_args.max_seconds)
591  return exit_condition_type::timeout;
592 
593  if (exe_args.is_min_delta_assigned())
594  if (get_delta() <= exe_args.min_delta)
595  return exit_condition_type::delta;
596 
597  if (exe_args.is_min_length_assigned())
598  if (get_length() <= exe_args.min_length)
599  return exit_condition_type::length;
600 
601  iterate(objfunc);
602  iteration++;
603 
604  if (exe_args.is_logfunc_assigned())
605  exe_args.logfunc(log_args(
606  this,
607  get_seconds(),
608  iteration,
609  exe_args.user));
610 
611  auto flux = get_flux();
612 
613  if (exe_args.is_min_epsilon_assigned())
614  if (std::fabs(flux0 - flux) <= exe_args.min_epsilon)
616  flux0 = flux;
617  }
618  }
619 
620  ///
621  /// \return The difference between the best and worst values returned
622  /// from the objective function for all vertices of the simplex.
623  ///
625  {
626  return _x.back()->objval - _x.front()->objval;
627  }
628 
629  ///
630  /// \return The difference between the value compared to the epsilon
631  /// in the execute method. This value is determined by dividing the
632  /// sum of the non-infinite values by the number of non-infinite values
633  /// squared.
634  ///
636  {
637  static const auto inf = std::numeric_limits<value_type>::max();
638 
639  auto sum = value_type(0);
640  auto count = 0;
641 
642  for (const auto & x : _x)
643  {
644  if (x->objval < inf)
645  {
646  sum += x->objval;
647  count++;
648  }
649  }
650 
651  return count == 0 ? value_type(0) : sum / count / count;
652  }
653 
654  ///
655  /// \return The square of the maximum length of the vector connecting
656  /// the vertex with the minimum value returned from the objective
657  /// function and any other vertex of the simplex.
658  ///
660  {
661  container_type vec;
662  vec.resize(_n);
663 
664  value_type max = value_type(0);
665 
666  const auto & p0 = _x[0]->params;
667 
668  for (size_t i = 1; i <= _n; i++)
669  {
670  const auto & p = _x[i]->params;
671 
672  _subtract(vec, p, p0);
673  _multiply(vec, vec, vec);
674 
675  max = std::max(max, std::accumulate(
676  vec.begin(),
677  vec.end(),
678  value_type(0),
679  std::plus<value_type>()));
680  }
681 
682  return max;
683  }
684 
685  ///
686  /// \return The maximum length of the vector connecting the vertex with
687  /// the minimum value returned from the objective function and any other
688  /// vertex of the simplex.
689  ///
691  {
692  return std::sqrt(get_length_squared());
693  }
694 
695  ///
696  /// \return The options used for the class.
697  ///
698  const options & get_options() const
699  {
700  return _opts;
701  }
702 
703  ///
704  /// \return The statistics about the execution.
705  ///
706  const stats & get_stats() const
707  {
708  return _stats;
709  }
710 
711  ///
712  /// \return The minimum objective value.
713  ///
714  const value_type & get_objval() const
715  {
716  return _x[0]->objval;
717  }
718 
719  ///
720  /// \return The minimum objective value.
721  ///
723  const size_t index) ///< The vertex index.
724  const
725  {
726  assert(index <= _n);
727  return _x[index]->objval;
728  }
729 
730  ///
731  /// \return The vertex with the minimum value returned from the
732  /// objective function.
733  ///
734  const container_type & get_vertex() const
735  {
736  return _x[0]->params;
737  }
738 
739  ///
740  /// \return The vertex with the minimum value returned from the
741  /// objective function.
742  ///
744  const size_t index) ///< The vertex index.
745  const
746  {
747  assert(index <= _n);
748  return _x[index]->params;
749  }
750 
751  ///
752  /// Performs one iteration of the Nelder-Mead algorithm. In an
753  /// iteration over two-dimensional space, a point p_min is reflected to
754  /// point p_r, expanded to point p_e, or contracted to point p_c. If
755  /// these test points do not improve the overall score of the simplex,
756  /// then it shrinks around the point p_max with the highest score.
757  ///
758  /// \return The operation performed by the iteration.
759  ///
760  template <typename TObjfunc>
762  const TObjfunc objfunc) ///< The objective function.
763  {
764  const auto & x0 = _x[0];
765 
766  _stats.iterations++;
767 
768  //
769  // REFLECTION
770  //
771  _copy(_xbar, x0->params);
772  for (size_t i = 1; i < _n; i++)
773  _add(_xbar, _xbar, _x[i]->params);
774  _scale(_xbar, value_type(1.0) / value_type(_n));
775 
776  _subtract(_xr, _xbar, _x[_n]->params);
777  _scale(_xr, _opts.rho);
778  _add(_xr, _xr, _xbar);
779 
780  const auto fr = _evaluate(objfunc, _xr);
781  if (x0->objval <= fr && fr < _x[_n - 1]->objval)
782  return _accept(_xr, fr, _stats.reflections,
784 
785  //
786  // EXPANSION
787  //
788  if (fr < x0->objval)
789  {
790  _subtract(_xe, _xr, _xbar);
791  _scale(_xe, _opts.chi);
792  _add(_xe, _xe, _xbar);
793 
794  const auto fe = _evaluate(objfunc, _xe);
795  return fe < fr
796  ? _accept(_xe, fe, _stats.expansions,
798  : _accept(_xr, fr, _stats.reflections,
800  }
801 
802  //
803  // CONTRACTION
804  //
805  if (fr >= _x[_n - 1]->objval)
806  {
807  if (fr < _x[_n]->objval)
808  {
809  _subtract(_xc, _xr, _xbar);
810  _scale(_xc, _opts.gamma);
811  _add(_xc, _xc, _xbar);
812 
813  const auto fc = _evaluate(objfunc, _xc);
814  if (fc <= fr)
815  return _accept(_xc, fc, _stats.contractions_out,
817  }
818  else
819  {
820  _subtract(_xcc, _xbar, _x[_n]->params);
821  _scale(_xcc, _opts.gamma);
822  _subtract(_xcc, _xbar, _xcc);
823 
824  const auto fcc = _evaluate(objfunc, _xcc);
825  if (fcc < _x[_n]->objval)
826  return _accept(_xcc, fcc, _stats.contractions_in,
828  }
829  }
830 
831  //
832  // SHRINKAGE
833  //
834  for (size_t i = 1; i <= _n; i++)
835  {
836  auto & xi = _x[i];
837  _subtract(xi->params, xi->params, x0->params);
838  _scale(xi->params, _opts.sigma);
839  _add(xi->params, xi->params, x0->params);
840  xi->objval = _evaluate(objfunc, xi->params);
841  }
842 
843  std::sort(_x.begin(), _x.end(), _is_less);
844  _stats.shrinkages++;
845  return operation::shrinkage;
846  }
847 
848  private:
849  // --------------------------------------------------------------------
850  struct vertex
851  {
852  container_type params;
853  value_type objval;
854 
855  // ----------------------------------------------------------------
856  vertex(
857  const options & opts,
858  const size_t index)
859  : params (opts.vertex)
860  , objval (0)
861  {
862  if (index > 0)
863  params[index - 1] += opts.unit;
864  }
865  };
866 
867  typedef std::unique_ptr<vertex> vertex_ptr_type;
868  typedef std::vector<vertex_ptr_type> vertex_container_type;
869 
870  // --------------------------------------------------------------------
871  operation_type _accept(
872  const container_type & params,
873  const value_type objval,
874  size_t & stat,
875  const operation_type type)
876  {
877  //
878  // Accepts a new vertex into the simplex by replacing the vertex
879  // with the highest value returned from the objective function and
880  // then resorting.
881  //
882  const auto n = params.size();
883  auto & v = _x[n];
884  _copy(v->params, params);
885  v->objval = objval;
886  std::sort(_x.begin(), _x.end(), _is_less);
887  stat++;
888  return type;
889  }
890 
891  // --------------------------------------------------------------------
892  static void _add(
893  container_type & dst,
894  const container_type & lhs,
895  const container_type & rhs)
896  {
897  assert(dst.size() == lhs.size());
898  assert(lhs.size() == rhs.size());
899  std::transform(lhs.begin(), lhs.end(), rhs.begin(), dst.begin(),
900  std::plus<value_type>());
901  }
902 
903  // --------------------------------------------------------------------
904  static bool _is_less(
905  const vertex_ptr_type & lhs,
906  const vertex_ptr_type & rhs)
907  {
908  return lhs->objval < rhs->objval;
909  }
910 
911  // --------------------------------------------------------------------
912  static void _copy(
913  container_type & dst,
914  const container_type & src)
915  {
916  assert(dst.size() == src.size());
917  std::copy(src.begin(), src.end(), dst.begin());
918  }
919 
920  // --------------------------------------------------------------------
921  template <typename TObjfunc>
922  value_type _evaluate(
923  const TObjfunc objfunc,
924  const container_type & params)
925  {
926  _stats.evaluations++;
927  return objfunc(params);
928  }
929 
930  // --------------------------------------------------------------------
931  static void _multiply(
932  container_type & dst,
933  const container_type & lhs,
934  const container_type & rhs)
935  {
936  assert(dst.size() == lhs.size());
937  assert(dst.size() == rhs.size());
938  std::transform(lhs.begin(), lhs.end(), rhs.begin(), dst.begin(),
939  std::multiplies<value_type>());
940  }
941 
942  // --------------------------------------------------------------------
943  static void _scale(
944  container_type & dst,
945  const value_type k)
946  {
947  for (auto & n : dst)
948  n *= k;
949  }
950 
951  // --------------------------------------------------------------------
952  static void _subtract(
953  container_type & dst,
954  const container_type & lhs,
955  const container_type & rhs)
956  {
957  assert(dst.size() == lhs.size());
958  assert(dst.size() == rhs.size());
959  std::transform(lhs.begin(), lhs.end(), rhs.begin(), dst.begin(),
960  std::minus<value_type>());
961  }
962 
963  size_t _n; // number of dimensions
964  options _opts; // algorithm options
965  stats _stats; // execution stats
966  vertex_container_type _x; // the vertices of the simplex
967  container_type _xbar; // centroid excluding x[n]
968  container_type _xr; // reflection vertex
969  container_type _xc; // outside contraction vertex
970  container_type _xcc; // inside contraction vertex
971  container_type _xe; // expansion vertex
972  };
973 }
974 
975 ///
976 /// Writes a simplex to the specified output stream.
977 /// \return The output stream.
978 ///
979 template <typename TValue>
980 std::ostream & operator << (
981  std::ostream & lhs, ///< The output stream.
982  const jade::basic_simplex<TValue> & rhs) ///< The simplex.
983 {
984  return lhs
985  << rhs.get_stats().str()
986  << "delta: " << rhs.get_delta() << std::endl
987  << "flux: " << rhs.get_flux() << std::endl
988  << "length: " << rhs.get_length() << std::endl;
989 }
990 
991 #endif // JADE_SIMPLEX_HPP__
jade::basic_simplex::get_length_squared
value_type get_length_squared() const
Definition: jade.simplex.hpp:659
jade::basic_simplex::execute_args::is_min_epsilon_assigned
bool is_min_epsilon_assigned() const
Definition: jade.simplex.hpp:238
jade::basic_simplex::options::options
options(const size_t n)
Initializes a new instance of the class.
Definition: jade.simplex.hpp:341
jade::basic_simplex::log_args
Arguments passed to the logging function.
Definition: jade.simplex.hpp:115
jade::basic_simplex::stats::shrinkages
size_t shrinkages
The number of shrinkages that have occurred.
Definition: jade.simplex.hpp:460
jade::basic_simplex::execute_args::min_length
value_type min_length
The minimum length.
Definition: jade.simplex.hpp:186
jade::basic_simplex::execute_args::no_min_delta
static constexpr auto no_min_delta
The value assigned for no minimum delta.
Definition: jade.simplex.hpp:170
jade::basic_simplex::execute_args::execute_args
execute_args()
Initializes a new instance of the class.
Definition: jade.simplex.hpp:192
jade::basic_simplex::operation::str
static const char * str(const type value)
Definition: jade.simplex.hpp:90
jade::basic_simplex::stats::expansions
size_t expansions
The number of expansions that have occurred.
Definition: jade.simplex.hpp:430
jade::basic_simplex::log_args::str
std::string str() const
Definition: jade.simplex.hpp:144
jade::basic_simplex::options::options
options(const container_type &vertex_)
Initializes a new instance of the class.
Definition: jade.simplex.hpp:357
jade::basic_simplex::execute_args::logfunc_type
void(* logfunc_type)(const log_args &)
The C-style log function.
Definition: jade.simplex.hpp:159
jade::basic_simplex::log_args::second
double second
The seconds elapsed.
Definition: jade.simplex.hpp:117
jade::basic_simplex::get_objval
const value_type & get_objval(const size_t index) const
Definition: jade.simplex.hpp:722
jade::basic_simplex::exit_condition::length
@ length
The minimum length occurred.
Definition: jade.simplex.hpp:42
jade::basic_simplex::stats::iterations
size_t iterations
The number of iterations that have executed.
Definition: jade.simplex.hpp:450
jade::basic_simplex::stats::reflections
size_t reflections
The number of reflections that have occurred.
Definition: jade.simplex.hpp:455
jade::basic_simplex::execute_args::is_min_length_assigned
bool is_min_length_assigned() const
Definition: jade.simplex.hpp:246
jade::basic_simplex::execute_args
Arguments to the execute method.
Definition: jade.simplex.hpp:157
jade::basic_simplex::options::gamma
value_type gamma
The contraction coefficient, which must be greater than 0.0 and less than 1.0.
Definition: jade.simplex.hpp:319
jade::basic_simplex::iterate
operation_type iterate(const TObjfunc objfunc)
Performs one iteration of the Nelder-Mead algorithm. In an iteration over two-dimensional space,...
Definition: jade.simplex.hpp:761
jade::basic_simplex::options::sigma
value_type sigma
The shrinkage coefficient, which must be greater than 0.0 and less than 1.0.
Definition: jade.simplex.hpp:330
jade::basic_simplex::options::chi
value_type chi
The expansion coefficient, which must be greater than the larger or rho or 1.0.
Definition: jade.simplex.hpp:313
jade::basic_simplex::operation_type
operation::type operation_type
The operation type.
Definition: jade.simplex.hpp:109
jade::basic_simplex::get_stats
const stats & get_stats() const
Definition: jade.simplex.hpp:706
jade::basic_simplex::value_type
TValue value_type
The value type.
Definition: jade.simplex.hpp:24
jade::basic_simplex::operation::contraction_in
@ contraction_in
An inside contraction.
Definition: jade.simplex.hpp:81
jade::basic_simplex
A template for a class that implements the Nelder-Mead Simplex Method, which attempts to minimize an ...
Definition: jade.simplex.hpp:21
jade::basic_simplex::stats::stats
stats()
Initializes a new instance of the class.
Definition: jade.simplex.hpp:465
jade::basic_simplex::get_flux
value_type get_flux() const
Definition: jade.simplex.hpp:635
jade::basic_simplex::operation::contraction_out
@ contraction_out
An outside contraction.
Definition: jade.simplex.hpp:82
jade::basic_simplex::container_type
std::vector< value_type > container_type
The container type.
Definition: jade.simplex.hpp:27
jade::basic_simplex::execute_args::no_min_epsilon
static constexpr auto no_min_epsilon
The value assigned for no minimum epsilon.
Definition: jade.simplex.hpp:174
jade::basic_simplex::log_args::log_args
log_args(const basic_simplex *const simplex_, const double second_, const size_t iteration_, void *const user_)
Initializes a new instance of the class.
Definition: jade.simplex.hpp:129
jade::basic_simplex::execute_args::user
void * user
User-supplied value.
Definition: jade.simplex.hpp:187
jade::basic_simplex::exit_condition::epsilon
@ epsilon
The minimum epsilon occurred.
Definition: jade.simplex.hpp:40
jade::basic_simplex::options
A data structure used to initialize the Nelder-Mead algorithm.
Definition: jade.simplex.hpp:303
jade::basic_simplex::operation::shrinkage
@ shrinkage
A shrinkage.
Definition: jade.simplex.hpp:84
jade::basic_simplex::execute_args::no_max_iterations
static constexpr auto no_max_iterations
The value assigned for no maximum iterations.
Definition: jade.simplex.hpp:162
jade::basic_simplex::exit_condition::timeout
@ timeout
The maximum timeout occurred.
Definition: jade.simplex.hpp:43
jade::basic_simplex::execute_args::min_epsilon
value_type min_epsilon
The minimum change in objval.
Definition: jade.simplex.hpp:185
jade::basic_simplex::execute_args::max_seconds
double max_seconds
The maximum seconds.
Definition: jade.simplex.hpp:183
jade::basic_simplex::log_args::user
void * user
User-supplied value.
Definition: jade.simplex.hpp:119
jade::basic_simplex::get_objval
const value_type & get_objval() const
Definition: jade.simplex.hpp:714
jade::basic_simplex::get_vertex
const container_type & get_vertex() const
Definition: jade.simplex.hpp:734
jade::basic_simplex::execute_args::is_min_delta_assigned
bool is_min_delta_assigned() const
Definition: jade.simplex.hpp:230
jade::basic_simplex::stats::contractions_out
size_t contractions_out
The number of outside contractions that have occurred.
Definition: jade.simplex.hpp:445
jade::basic_simplex::execute_args::max_iterations
size_t max_iterations
The maximum iterations.
Definition: jade.simplex.hpp:182
jade::basic_simplex::basic_simplex
basic_simplex(const TObjfunc objfunc, const options &opts)
Initializes a new instance of the class based on the specified options.
Definition: jade.simplex.hpp:510
jade::basic_simplex::operation::type
type
The type of operation.
Definition: jade.simplex.hpp:79
jade::basic_simplex::execute_args::logfunc
logfunc_type logfunc
The logging function.
Definition: jade.simplex.hpp:181
jade::basic_simplex::options::vertex
container_type vertex
A vertex in the initial formation of the simplex.
Definition: jade.simplex.hpp:307
jade::basic_simplex::stats
Statistics about the behavior of the algorithm.
Definition: jade.simplex.hpp:426
jade::basic_simplex::exit_condition_type
exit_condition::type exit_condition_type
The exit condition type.
Definition: jade.simplex.hpp:68
jade::basic_simplex::execute_args::is_max_iterations_assigned
bool is_max_iterations_assigned() const
Definition: jade.simplex.hpp:214
jade::basic_simplex::exit_condition::type
type
The exit condition.
Definition: jade.simplex.hpp:38
jade::basic_simplex::get_length
value_type get_length() const
Definition: jade.simplex.hpp:690
jade::basic_simplex::exit_condition::str
static const char * str(const type value)
Definition: jade.simplex.hpp:49
jade::basic_simplex::stats::str
std::string str() const
Definition: jade.simplex.hpp:479
jade::basic_simplex::execute_args::is_max_seconds_assigned
bool is_max_seconds_assigned() const
Definition: jade.simplex.hpp:222
jade::basic_simplex::execute
exit_condition_type execute(const TObjfunc objfunc, const execute_args &exe_args)
Calls the iterate method until an exit condition is reached.
Definition: jade.simplex.hpp:567
jade::basic_simplex::operation
An operation performed during an iteration.
Definition: jade.simplex.hpp:74
jade::basic_simplex::execute_args::str
std::string str() const
Definition: jade.simplex.hpp:254
jade::basic_simplex::execute_args::min_delta
value_type min_delta
The minimum delta.
Definition: jade.simplex.hpp:184
jade::basic_simplex::exit_condition
An indication of what caused the execute to temrinate.
Definition: jade.simplex.hpp:33
jade::basic_simplex::execute_args::is_logfunc_assigned
bool is_logfunc_assigned() const
Definition: jade.simplex.hpp:206
jade::basic_simplex::basic_simplex
basic_simplex(const TObjfunc objfunc, const size_t n)
Initializes a new instance of the class based on the specified required values.
Definition: jade.simplex.hpp:498
jade::basic_simplex::get_vertex
const container_type & get_vertex(const size_t index) const
Definition: jade.simplex.hpp:743
jade::basic_simplex::options::unit
value_type unit
A scaling coefficient used to construct the unit vectors in each dimension of the simplex,...
Definition: jade.simplex.hpp:336
jade::basic_simplex::execute_args::no_max_seconds
static constexpr auto no_max_seconds
The value assigned for no maximum seconds.
Definition: jade.simplex.hpp:166
jade::basic_simplex::execute_args::no_min_length
static constexpr auto no_min_length
The value assigned for no minimum length.
Definition: jade.simplex.hpp:178
jade::basic_simplex::get_options
const options & get_options() const
Definition: jade.simplex.hpp:698
jade::basic_simplex::stats::evaluations
size_t evaluations
The number of evaluations of the objective function.
Definition: jade.simplex.hpp:435
jade::basic_simplex::operation::reflection
@ reflection
A reflection.
Definition: jade.simplex.hpp:83
jade::basic_simplex::exit_condition::delta
@ delta
The minimum delta occurred.
Definition: jade.simplex.hpp:39
jade::basic_simplex::stats::contractions_in
size_t contractions_in
The number of inside contractions that have occurred.
Definition: jade.simplex.hpp:440
jade::basic_simplex::exit_condition::iteration
@ iteration
The maximum iteration occurred.
Definition: jade.simplex.hpp:41
jade::basic_simplex::options::rho
value_type rho
The reflection coefficient, which must be greater than 0.0.
Definition: jade.simplex.hpp:324
jade::basic_simplex::log_args::simplex
const basic_simplex * simplex
The simplex instance.
Definition: jade.simplex.hpp:118
jade::basic_simplex::operation::expansion
@ expansion
An expansion.
Definition: jade.simplex.hpp:80
jade::basic_simplex::get_delta
value_type get_delta() const
Definition: jade.simplex.hpp:624
jade::basic_simplex::options::str
std::string str() const
Definition: jade.simplex.hpp:372
jade::basic_simplex::log_args::iteration
size_t iteration
The completed iteration.
Definition: jade.simplex.hpp:116