CppAD: A C++ Algorithmic Differentiation Package  20171217
solve.hpp
Go to the documentation of this file.
1 // $Id: solve.hpp 3804 2016-03-20 15:08:46Z bradbell$
2 # ifndef CPPAD_IPOPT_SOLVE_HPP
3 # define CPPAD_IPOPT_SOLVE_HPP
4 /* --------------------------------------------------------------------------
5 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-16 Bradley M. Bell
6
8 the terms of the
9  Eclipse Public License Version 1.0.
10
11 A copy of this license is included in the COPYING file of this distribution.
13 -------------------------------------------------------------------------- */
14 /*
15 $begin ipopt_solve$$16 spell 17 Jacobian 18 Jacobians 19 retape 20 Bvector 21 bool 22 infeasibility 23 const 24 cpp 25 cppad 26 doesn't 27 ADvector 28 eval 29 fg 30 gl 31 gu 32 hpp 33 inf 34 ipopt 35 maxiter 36 naninf 37 nf 38 ng 39 nx 40 obj 41 optimizer 42 std 43 xi 44 xl 45 xu 46 zl 47 zu 48$$ 49 50$section Use Ipopt to Solve a Nonlinear Programming Problem$$51 52 head Syntax$$
53 $codei%# include <cppad/ipopt/solve.hpp> 54 %$$55 codei%ipopt::solve( 56 %options%, %xi%, %xl%, %xu%, %gl%, %gu%, %fg_eval%, %solution% 57 )%$$ 58 59$head Purpose$$60 The function code ipopt::solve$$ solves nonlinear programming
61 problems of the form
62 $latex $63 \begin{array}{rll} 64 {\rm minimize} & f (x) 65 \\ 66 {\rm subject \; to} & gl \leq g(x) \leq gu 67 \\ 68 & xl \leq x \leq xu 69 \end{array} 70$ $$71 This is done using 72 href% 73 http://www.coin-or.org/projects/Ipopt.xml% 74 Ipopt 75 %$$ 76 optimizer and CppAD for the derivative and sparsity calculations. 77 78$head Include File$$79 Currently, this routine 80 cref/ipopt::solve/ipopt_solve/$$ is not included by the command
81 $codei% 82 # include <cppad/cppad.hpp> 83 %$$84 (Doing so would require the ipopt library to link 85 the corresponding program (even if code ipopt::solve$$) was not used.) 86 For this reason, 87 if you are using$code ipopt::solve$$you should use 88 codei% 89 # include <cppad/ipopt/solve.hpp> 90 %$$
91 which in turn will also include $code <cppad/cppad.hpp>$$. 92 93 head Bvector$$ 94 The type$icode Bvector$$must be a cref SimpleVector$$ class with
95 $cref/elements of type/SimpleVector/Elements of Specified Type/$$96 code bool$$. 97 98$head Dvector$$99 The type icode DVector$$ must be a $cref SimpleVector$$class with 100 cref/elements of type/SimpleVector/Elements of Specified Type/$$ 101$code double$$. 102 103 head options$$
104 The argument $icode options$$has prototype 105 codei% 106 const std::string %options% 107 %$$ 108 It contains a list of options. 109 Each option, including the last option, 110 is terminated by the$code '\n'$$character. 111 Each line consists of two or three tokens separated by one or more spaces. 112 113 subhead Retape$$
114 You can set the retape flag with the following syntax:
115 $codei% 116 Retape %value% 117 %$$118 If the value is code true$$,$code ipopt::solve$$with retape the 119 cref/operation sequence/glossary/Operation/Sequence/$$ for each
120 new value of $icode x$$. 121 If the value is code false$$,$code ipopt::solve$$122 will tape the operation sequence at the value 123 of icode xi$$ and use that sequence for the entire optimization process.
124 The default value is $code false$$. 125 126 subhead Sparse$$ 127 You can set the sparse Jacobian and Hessian flag with the following syntax: 128$codei%
129  Sparse %value% %direction%
130 %$$131 If the value is code true$$, $code ipopt::solve$$will use a sparse 132 matrix representation for the computation of Jacobians and Hessians. 133 Otherwise, it will use a full matrix representation for 134 these calculations. 135 The default for icode value$$ is$code false$$. 136 If sparse is true, retape must be false. 137 pre 138 139$$
140 It is unclear if $cref sparse_jacobian$$would be faster user 141 forward or reverse mode so you are able to choose the direction. 142 If 143 codei% 144 %value% == true && %direction% == forward 145 %$$ 146 the Jacobians will be calculated using$code SparseJacobianForward$$. 147 If 148 codei% 149 %value% == true && %direction% == reverse 150 %$$
151 the Jacobians will be calculated using $code SparseJacobianReverse$$. 152 153 subhead String$$ 154 You can set any Ipopt string option using a line with the following syntax: 155$codei%
156  String %name% %value%
157 %$$158 Here icode name$$ is any valid Ipopt string option
159 and $icode value$$is its setting. 160 161 subhead Numeric$$ 162 You can set any Ipopt numeric option using a line with the following syntax: 163$codei%
164  Numeric %name% %value%
165 %$$166 Here icode name$$ is any valid Ipopt numeric option
167 and $icode value$$is its setting. 168 169 subhead Integer$$ 170 You can set any Ipopt integer option using a line with the following syntax: 171$codei%
172  Integer %name% %value%
173 %$$174 Here icode name$$ is any valid Ipopt integer option
175 and $icode value$$is its setting. 176 177 head xi$$ 178 The argument$icode xi$$has prototype 179 codei% 180 const %Vector%& %xi% 181 %$$
182 and its size is equal to $icode nx$$. 183 It specifies the initial point where Ipopt starts the optimization process. 184 185 head xl$$ 186 The argument$icode xl$$has prototype 187 codei% 188 const %Vector%& %xl% 189 %$$
190 and its size is equal to $icode nx$$. 191 It specifies the lower limits for the argument in the optimization problem. 192 193 head xu$$ 194 The argument$icode xu$$has prototype 195 codei% 196 const %Vector%& %xu% 197 %$$
198 and its size is equal to $icode nx$$. 199 It specifies the upper limits for the argument in the optimization problem. 200 201 head gl$$ 202 The argument$icode gl$$has prototype 203 codei% 204 const %Vector%& %gl% 205 %$$
206 and its size is equal to $icode ng$$. 207 It specifies the lower limits for the constraints in the optimization problem. 208 209 head gu$$ 210 The argument$icode gu$$has prototype 211 codei% 212 const %Vector%& %gu% 213 %$$
214 and its size is equal to $icode ng$$. 215 It specifies the upper limits for the constraints in the optimization problem. 216 217 head fg_eval$$ 218 The argument$icode fg_eval$$has prototype 219 codei% 220 %FG_eval% %fg_eval% 221 %$$
222 where the class $icode FG_eval$$is unspecified except for the fact that 223 it supports the syntax 224 codei% 225 %FG_eval%::ADvector 226 %fg_eval%(%fg%, %x%) 227 %$$ 228 The type$icode ADvector$$229 and the arguments to icode fg$$, $icode x$$have the following meaning: 230 231 subhead ADvector$$ 232 The type$icode%FG_eval%::ADvector%$$must be a cref SimpleVector$$ class with
233 $cref/elements of type/SimpleVector/Elements of Specified Type/$$234 code AD<double>$$. 235 236$subhead x$$237 The icode fg_eval$$ argument $icode x$$has prototype 238 codei% 239 const %ADvector%& %x% 240 %$$ 241 where$icode%nx% = %x%.size()%$$. 242 243 subhead fg$$
244 The $icode fg_eval$$argument icode fg$$ has prototype 245$codei%
247 %$$248 where codei%1 + %ng% = %fg%.size()%$$.
249 The input value of the elements of $icode fg$$does not matter. 250 Upon return from icode fg_eval$$, 251$codei%
252  %fg%[0] =%$$latex f (x)$$ $codei% 253 %$$254 and for latex i = 0, \ldots , ng-1$$, 255$codei%
256  %fg%[1 + %i%] =%$$latex g_i (x)$$
257
258 $head solution$$259 The argument icode solution$$ has prototype 260$codei%
261  ipopt::solve_result<%Dvector%>& %solution%
262 %$$263 After the optimization process is completed, icode solution$$ contains
264 the following information:
265
266 $subhead status$$267 The icode status$$ field of$icode solution$$has prototype 268 codei% 269 ipopt::solve_result<%Dvector%>::status_type %solution%.status 270 %$$
271 It is the final Ipopt status for the optimizer.
272 Here is a list of the possible values for the status:
273
274 $table 275$icode status$$cnext Meaning 276 rnext 277 not_defined cnext 278 The optimizer did not return a final status for this problem. 279 rnext 280 unknown cnext 281 The status returned by the optimizer is not defined in the Ipopt 282 documentation for code finalize_solution$$.
283 $rnext 284 success$cnext
285 Algorithm terminated successfully at a point satisfying the convergence
286 tolerances (see Ipopt options).
287 $rnext 288 maxiter_exceeded$cnext
289 The maximum number of iterations was exceeded (see Ipopt options).
290 $rnext 291 stop_at_tiny_step$cnext
292 Algorithm terminated because progress was very slow.
293 $rnext 294 stop_at_acceptable_point$cnext
295 Algorithm stopped at a point that was converged,
296 not to the 'desired' tolerances, but to 'acceptable' tolerances
297 (see Ipopt options).
298 $rnext 299 local_infeasibility$cnext
300 Algorithm converged to a non-feasible point
301 (problem may have no solution).
302 $rnext 303 user_requested_stop$cnext
304 This return value should not happen.
305 $rnext 306 diverging_iterates$cnext
307 It the iterates are diverging.
308 $rnext 309 restoration_failure$cnext
310 Restoration phase failed, algorithm doesn't know how to proceed.
311 $rnext 312 error_in_step_computation$cnext
313 An unrecoverable error occurred while Ipopt tried to
314 compute the search direction.
315 $rnext 316 invalid_number_detected$cnext
317 Algorithm received an invalid number (such as $code nan$$or code inf$$) 318 from the users function$icode%fg_info%.eval%$$or from the CppAD evaluations 319 of its derivatives 320 (see the Ipopt option code check_derivatives_for_naninf$$).
321 $rnext 322 internal_error$cnext
323 An unknown Ipopt internal error occurred.
324 Contact the Ipopt authors through the mailing list.
325 $tend 326 327$subhead x$$328 The code x$$ field of $icode solution$$has prototype 329 codei% 330 %Vector% %solution%.x 331 %$$ 332 and its size is equal to$icode nx$$. 333 It is the final latex x$$ value for the optimizer.
334
335 $subhead zl$$336 The code zl$$ field of$icode solution$$has prototype 337 codei% 338 %Vector% %solution%.zl 339 %$$
340 and its size is equal to $icode nx$$. 341 It is the final Lagrange multipliers for the 342 lower bounds on latex x$$. 343 344$subhead zu$$345 The code zu$$ field of $icode solution$$has prototype 346 codei% 347 %Vector% %solution%.zu 348 %$$ 349 and its size is equal to$icode nx$$. 350 It is the final Lagrange multipliers for the 351 upper bounds on latex x$$.
352
353 $subhead g$$354 The code g$$ field of$icode solution$$has prototype 355 codei% 356 %Vector% %solution%.g 357 %$$
358 and its size is equal to $icode ng$$. 359 It is the final value for the constraint function latex g(x)$$. 360 361$subhead lambda$$362 The code lambda$$ field of $icode solution$$has prototype 363 codei% 364 %Vector%> %solution%.lambda 365 %$$ 366 and its size is equal to$icode ng$$. 367 It is the final value for the 368 Lagrange multipliers corresponding to the constraint function. 369 370 subhead obj_value$$
371 The $code obj_value$$field of icode solution$$ has prototype 372$codei%
373  double %solution%.obj_value
374 %$$375 It is the final value of the objective function latex f(x)$$.
376
377 $children% 378 example/ipopt_solve/get_started.cpp% 379 example/ipopt_solve/retape.cpp% 380 example/ipopt_solve/ode_inverse.cpp 381 %$$382 head Example$$ 383 All the examples return true if it succeeds and false otherwise. 384 385$subhead get_started$$386 The file 387 cref%example/ipopt_solve/get_started.cpp%ipopt_solve_get_started.cpp%$$
388 is an example and test of $code ipopt::solve$$389 taken from the Ipopt manual. 390 391 subhead retape$$ 392 The file 393$cref%example/ipopt_solve/retape.cpp%ipopt_solve_retape.cpp%$$394 demonstrates when it is necessary to specify 395 cref/retape/ipopt_solve/options/Retape/$$ as true.
396
397 $subhead ode_inverse$$398 The file 399 cref%example/ipopt_solve/ode_inverse.cpp%ipopt_solve_ode_inverse.cpp%$$ 400 demonstrates using Ipopt to solve for parameters in an ODE model. 401 402$end
403 -------------------------------------------------------------------------------
404 */
406
408 namespace ipopt {
409 /*!
410 \file solve.hpp
411 \brief Implement the ipopt::solve Nonlinear Programming Solver
412 */
413
414 /*!
415 Use Ipopt to Solve a Nonlinear Programming Problem
416
417 \tparam Bvector
418 simple vector class with elements of type bool.
419
420 \tparam Dvector
421 simple vector class with elements of type double.
422
423 \tparam FG_eval
424 function object used to evaluate f(x) and g(x); see fg_eval below.
425 It must also support
426 \code
428 \endcode
429 to dentify the type used for the arguments to fg_eval.
430
431 \param options
432 list of options, one for each line.
433 Ipopt options (are optional) and have one of the following forms
434 \code
435  String name value
436  Numeric name value
437  Integer name value
438 \endcode
439 The following other possible options are listed below:
440 \code
441  Retape value
442 \endcode
443
444
445 \param xi
446 initial argument value to start optimization procedure at.
447
448 \param xl
449 lower limit for argument during optimization
450
451 \param xu
452 upper limit for argument during optimization
453
454 \param gl
455 lower limit for g(x) during optimization.
456
457 \param gu
458 upper limit for g(x) during optimization.
459
460 \param fg_eval
461 function that evaluates the objective and constraints using the syntax
462 \code
463  fg_eval(fg, x)
464 \endcode
465
466 \param solution
467 structure that holds the solution of the optimization.
468 */
469 template <class Dvector, class FG_eval>
470 void solve(
471  const std::string& options ,
472  const Dvector& xi ,
473  const Dvector& xl ,
474  const Dvector& xu ,
475  const Dvector& gl ,
476  const Dvector& gu ,
477  FG_eval& fg_eval ,
478  ipopt::solve_result<Dvector>& solution )
479 { bool ok = true;
480
482
484  xi.size() == xl.size() && xi.size() == xu.size() ,
485  "ipopt::solve: size of xi, xl, and xu are not all equal."
486  );
488  gl.size() == gu.size() ,
489  "ipopt::solve: size of gl and gu are not equal."
490  );
491  size_t nx = xi.size();
492  size_t ng = gl.size();
493
494  // Create an IpoptApplication
495  using Ipopt::IpoptApplication;
496  Ipopt::SmartPtr<IpoptApplication> app = new IpoptApplication();
497
498  // process the options argument
499  size_t begin_1, end_1, begin_2, end_2, begin_3, end_3;
500  begin_1 = 0;
501  bool retape = false;
502  bool sparse_forward = false;
503  bool sparse_reverse = false;
504  while( begin_1 < options.size() )
505  { // split this line into tokens
506  while( options[begin_1] == ' ')
507  begin_1++;
508  end_1 = options.find_first_of(" \n", begin_1);
509  begin_2 = end_1;
510  while( options[begin_2] == ' ')
511  begin_2++;
512  end_2 = options.find_first_of(" \n", begin_2);
513  begin_3 = end_2;
514  while( options[begin_3] == ' ')
515  begin_3++;
516  end_3 = options.find_first_of(" \n", begin_3);
517
518  // check for errors
520  (end_1 != std::string::npos) &
521  (end_2 != std::string::npos) &
522  (end_3 != std::string::npos) ,
523  "ipopt::solve: missing '\\n' at end of an option line"
524  );
526  (end_1 > begin_1) & (end_2 > begin_2) ,
527  "ipopt::solve: an option line does not have two tokens"
528  );
529
530  // get first two tokens
531  std::string tok_1 = options.substr(begin_1, end_1 - begin_1);
532  std::string tok_2 = options.substr(begin_2, end_2 - begin_2);
533
534  // get third token
535  std::string tok_3;
536  bool three_tok = false;
537  three_tok |= tok_1 == "Sparse";
538  three_tok |= tok_1 == "String";
539  three_tok |= tok_1 == "Numeric";
540  three_tok |= tok_1 == "Integer";
541  if( three_tok )
543  (end_3 > begin_3) ,
544  "ipopt::solve: a Sparse, String, Numeric, or Integer\n"
545  "option line does not have three tokens."
546  );
547  tok_3 = options.substr(begin_3, end_3 - begin_3);
548  }
549
550  // switch on option type
551  if( tok_1 == "Retape" )
553  (tok_2 == "true") | (tok_2 == "false") ,
554  "ipopt::solve: Retape value is not true or false"
555  );
556  retape = (tok_2 == "true");
557  }
558  else if( tok_1 == "Sparse" )
560  (tok_2 == "true") | (tok_2 == "false") ,
561  "ipopt::solve: Sparse value is not true or false"
562  );
564  (tok_3 == "forward") | (tok_3 == "reverse") ,
565  "ipopt::solve: Sparse direction is not forward or reverse"
566  );
567  if( tok_2 == "false" )
568  { sparse_forward = false;
569  sparse_reverse = false;
570  }
571  else
572  { sparse_forward = tok_3 == "forward";
573  sparse_reverse = tok_3 == "reverse";
574  }
575  }
576  else if ( tok_1 == "String" )
577  app->Options()->SetStringValue(tok_2.c_str(), tok_3.c_str());
578  else if ( tok_1 == "Numeric" )
579  { Ipopt::Number value = std::atof( tok_3.c_str() );
580  app->Options()->SetNumericValue(tok_2.c_str(), value);
581  }
582  else if ( tok_1 == "Integer" )
583  { Ipopt::Index value = std::atoi( tok_3.c_str() );
584  app->Options()->SetIntegerValue(tok_2.c_str(), value);
585  }
587  false,
588  "ipopt::solve: First token is not one of\n"
589  "Retape, Sparse, String, Numeric, Integer"
590  );
591
592  begin_1 = end_3;
593  while( options[begin_1] == ' ')
594  begin_1++;
595  if( options[begin_1] != '\n' ) CPPAD_ASSERT_KNOWN(
596  false,
597  "ipopt::solve: either more than three tokens "
598  "or no '\\n' at end of a line"
599  );
600  begin_1++;
601  }
603  ! ( retape & (sparse_forward | sparse_reverse) ) ,
604  "ipopt::solve: retape and sparse both true is not supported."
605  );
606
607  // Initialize the IpoptApplication and process the options
608  Ipopt::ApplicationReturnStatus status = app->Initialize();
609  ok &= status == Ipopt::Solve_Succeeded;
610  if( ! ok )
612  return;
613  }
614
615  // Create an interface from Ipopt to this specific problem.
616  // Note the assumption here that ADvector is same as cppd_ipopt::ADvector
617  size_t nf = 1;
618  Ipopt::SmartPtr<Ipopt::TNLP> cppad_nlp =
620  nf,
621  nx,
622  ng,
623  xi,
624  xl,
625  xu,
626  gl,
627  gu,
628  fg_eval,
629  retape,
630  sparse_forward,
631  sparse_reverse,
632  solution
633  );
634
635  // Run the IpoptApplication
637
638  return;
639 }
640
641 } // end ipopt namespace
642 } // END_CPPAD_NAMESPACE
643 # endif