CppAD: A C++ Algorithmic Differentiation Package  20130918
solve.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 # ifndef CPPAD_SOLVE_INCLUDED
00003 # define CPPAD_SOLVE_INCLUDED
00004 /* --------------------------------------------------------------------------
00005 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-14 Bradley M. Bell
00006 
00007 CppAD is distributed under multiple licenses. This distribution is under
00008 the terms of the 
00009                     Eclipse Public License Version 1.0.
00010 
00011 A copy of this license is included in the COPYING file of this distribution.
00012 Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
00013 -------------------------------------------------------------------------- */
00014 /*
00015 $begin ipopt_solve$$
00016 $spell
00017      Jacobian
00018      Jacobians
00019      retape
00020      Bvector
00021      bool
00022      infeasibility
00023      const
00024      cpp
00025      cppad
00026      doesn't
00027      ADvector
00028      eval
00029      fg
00030      gl
00031      gu
00032      hpp
00033      inf
00034      ipopt
00035      maxiter
00036      naninf
00037      nf
00038      ng
00039      nx
00040      obj
00041      optimizer
00042      std
00043      xi
00044      xl
00045      xu
00046      zl
00047      zu
00048 $$
00049 
00050 $section Use Ipopt to Solve a Nonlinear Programming Problem$$
00051 
00052 $head Syntax$$
00053 $codei%# include <cppad/ipopt/solve.hpp>
00054 %$$
00055 $codei%ipopt::solve(
00056      %options%, %xi%, %xl%, %xu%, %gl%, %gu%, %fg_eval%, %solution%
00057 )%$$
00058 
00059 $head Purpose$$
00060 The function $code ipopt::solve$$ solves nonlinear programming
00061 problems of the form
00062 $latex \[
00063 \begin{array}{rll}
00064 {\rm minimize}      & f (x) 
00065 \\
00066 {\rm subject \; to} & gl \leq g(x) \leq gu
00067 \\
00068                     & xl  \leq x   \leq xu
00069 \end{array}
00070 \] $$
00071 This is done using 
00072 $href%
00073      http://www.coin-or.org/projects/Ipopt.xml%
00074      Ipopt
00075 %$$
00076 optimizer and CppAD for the derivative and sparsity calculations. 
00077 
00078 $head Include File$$
00079 Currently, this routine 
00080 $cref/ipopt::solve/ipopt_solve/$$ is not included by the command
00081 $codei%
00082      # include <cppad/cppad.hpp>
00083 %$$
00084 (Doing so would require the ipopt library to link
00085 the corresponding program (even if $code ipopt::solve$$) was not used.)
00086 For this reason, 
00087 if you are using $code ipopt::solve$$ you should use
00088 $codei%
00089      # include <cppad/ipopt/solve.hpp>
00090 %$$
00091 which in turn will also include $code <cppad/cppad.hpp>$$.
00092 
00093 $head Bvector$$
00094 The type $icode Bvector$$ must be a $cref SimpleVector$$ class with
00095 $cref/elements of type/SimpleVector/Elements of Specified Type/$$ 
00096 $code bool$$.
00097 
00098 $head Dvector$$
00099 The type $icode DVector$$ must be a $cref SimpleVector$$ class with
00100 $cref/elements of type/SimpleVector/Elements of Specified Type/$$ 
00101 $code double$$.
00102 
00103 $head options$$
00104 The argument $icode options$$ has prototype
00105 $codei%
00106      const std::string %options%
00107 %$$
00108 It contains a list of options.
00109 Each option, including the last option, 
00110 is terminated by the $code '\n'$$ character.
00111 Each line consists of two or three tokens separated by one or more spaces.
00112 
00113 $subhead Retape$$
00114 You can set the retape flag with the following syntax:
00115 $codei%
00116      Retape %value%
00117 %$$
00118 If the value is $code true$$, $code ipopt::solve$$ with retape the
00119 $cref/operation sequence/glossary/Operation/Sequence/$$ for each
00120 new value of $icode x$$.
00121 If the value is $code false$$, $code ipopt::solve$$
00122 will tape the operation sequence at the value
00123 of $icode xi$$ and use that sequence for the entire optimization process.  
00124 The default value is $code false$$.
00125 
00126 $subhead Sparse$$
00127 You can set the sparse Jacobian and Hessian flag with the following syntax:
00128 $codei%
00129      Sparse %value% %direction%
00130 %$$
00131 If the value is $code true$$, $code ipopt::solve$$ will use a sparse
00132 matrix representation for the computation of Jacobians and Hessians.
00133 Otherwise, it will use a full matrix representation for 
00134 these calculations.
00135 The default for $icode value$$ is $code false$$.
00136 If sparse is true, retape must be false.
00137 $pre
00138 
00139 $$
00140 It is unclear if $cref sparse_jacobian$$ would be faster user
00141 forward or reverse mode so you are able to choose the direction.
00142 If  
00143 $codei%
00144      %value% == true && %direction% == forward
00145 %$$
00146 the Jacobians will be calculated using $code SparseJacobianForward$$. 
00147 If 
00148 $codei%
00149      %value% == true && %direction% == reverse
00150 %$$
00151 the Jacobians will be calculated using $code SparseJacobianReverse$$. 
00152 
00153 $subhead String$$
00154 You can set any Ipopt string option using a line with the following syntax:
00155 $codei%
00156      String %name% %value%
00157 %$$
00158 Here $icode name$$ is any valid Ipopt string option 
00159 and $icode value$$ is its setting.
00160 
00161 $subhead Numeric$$
00162 You can set any Ipopt numeric option using a line with the following syntax:
00163 $codei%
00164      Numeric %name% %value%
00165 %$$
00166 Here $icode name$$ is any valid Ipopt numeric option 
00167 and $icode value$$ is its setting.
00168 
00169 $subhead Integer$$
00170 You can set any Ipopt integer option using a line with the following syntax:
00171 $codei%
00172      Integer %name% %value%
00173 %$$
00174 Here $icode name$$ is any valid Ipopt integer option 
00175 and $icode value$$ is its setting.
00176 
00177 $head xi$$
00178 The argument $icode xi$$ has prototype
00179 $codei%
00180      const %Vector%& %xi%
00181 %$$
00182 and its size is equal to $icode nx$$.
00183 It specifies the initial point where Ipopt starts the optimization process.
00184 
00185 $head xl$$
00186 The argument $icode xl$$ has prototype
00187 $codei%
00188      const %Vector%& %xl%
00189 %$$
00190 and its size is equal to $icode nx$$.
00191 It specifies the lower limits for the argument in the optimization problem.
00192 
00193 $head xu$$
00194 The argument $icode xu$$ has prototype
00195 $codei%
00196      const %Vector%& %xu%
00197 %$$
00198 and its size is equal to $icode nx$$.
00199 It specifies the upper limits for the argument in the optimization problem.
00200 
00201 $head gl$$
00202 The argument $icode gl$$ has prototype
00203 $codei%
00204      const %Vector%& %gl%
00205 %$$
00206 and its size is equal to $icode ng$$.
00207 It specifies the lower limits for the constraints in the optimization problem.
00208 
00209 $head gu$$
00210 The argument $icode gu$$ has prototype
00211 $codei%
00212      const %Vector%& %gu%
00213 %$$
00214 and its size is equal to $icode ng$$.
00215 It specifies the upper limits for the constraints in the optimization problem.
00216 
00217 $head fg_eval$$
00218 The argument $icode fg_eval$$ has prototype
00219 $codei%
00220      %FG_eval% %fg_eval%
00221 %$$
00222 where the class $icode FG_eval$$ is unspecified except for the fact that
00223 it supports the syntax
00224 $codei%
00225      %FG_eval%::ADvector
00226      %fg_eval%(%fg%, %x%)
00227 %$$
00228 The type $icode ADvector$$
00229 and the arguments to $icode fg$$, $icode x$$ have the following meaning:
00230 
00231 $subhead ADvector$$
00232 The type $icode%FG_eval%::ADvector%$$ must be a $cref SimpleVector$$ class with
00233 $cref/elements of type/SimpleVector/Elements of Specified Type/$$ 
00234 $code AD<double>$$.
00235 
00236 $subhead x$$
00237 The $icode fg_eval$$ argument $icode x$$ has prototype
00238 $codei%
00239      const %ADvector%& %x%
00240 %$$
00241 where $icode%nx% = %x%.size()%$$.
00242 
00243 $subhead fg$$
00244 The $icode fg_eval$$ argument $icode fg$$ has prototype
00245 $codei%
00246      %ADvector%& %fg%
00247 %$$
00248 where $codei%1 + %ng% = %fg%.size()%$$.
00249 The input value of the elements of $icode fg$$ does not matter.
00250 Upon return from $icode fg_eval$$,
00251 $codei%
00252      %fg%[0] =%$$ $latex f (x)$$ $codei%
00253 %$$
00254 and   for $latex i = 0, \ldots , ng-1$$,
00255 $codei%
00256      %fg%[1 + %i%] =%$$ $latex g_i (x)$$
00257 
00258 $head solution$$
00259 The argument $icode solution$$ has prototype
00260 $codei%
00261      ipopt::solve_result<%Dvector%>& %solution%
00262 %$$
00263 After the optimization process is completed, $icode solution$$ contains
00264 the following information:
00265 
00266 $subhead status$$
00267 The $icode status$$ field of $icode solution$$ has prototype
00268 $codei%
00269      ipopt::solve_result<%Dvector%>::status_type %solution%.status
00270 %$$
00271 It is the final Ipopt status for the optimizer. 
00272 Here is a list of the possible values for the status:
00273 
00274 $table
00275 $icode status$$ $cnext Meaning
00276 $rnext
00277 not_defined $cnext
00278 The optimizer did not return a final status for this problem.
00279 $rnext
00280 unknown $cnext
00281 The status returned by the optimizer is not defined in the Ipopt
00282 documentation for $code finalize_solution$$.
00283 $rnext
00284 success $cnext
00285 Algorithm terminated successfully at a point satisfying the convergence 
00286 tolerances (see Ipopt options).
00287 $rnext
00288 maxiter_exceeded $cnext
00289 The maximum number of iterations was exceeded (see Ipopt options).
00290 $rnext
00291 stop_at_tiny_step $cnext
00292 Algorithm terminated because progress was very slow.
00293 $rnext
00294 stop_at_acceptable_point $cnext
00295 Algorithm stopped at a point that was converged, 
00296 not to the 'desired' tolerances, but to 'acceptable' tolerances 
00297 (see Ipopt options).
00298 $rnext
00299 local_infeasibility $cnext
00300 Algorithm converged to a non-feasible point
00301 (problem may have no solution).
00302 $rnext
00303 user_requested_stop $cnext
00304 This return value should not happen.
00305 $rnext
00306 diverging_iterates $cnext
00307 It the iterates are diverging.
00308 $rnext
00309 restoration_failure $cnext
00310 Restoration phase failed, algorithm doesn't know how to proceed.
00311 $rnext
00312 error_in_step_computation $cnext
00313 An unrecoverable error occurred while Ipopt tried to 
00314 compute the search direction.
00315 $rnext
00316 invalid_number_detected $cnext
00317 Algorithm received an invalid number (such as $code nan$$ or $code inf$$) 
00318 from the users function $icode%fg_info%.eval%$$ or from the CppAD evaluations
00319 of its derivatives
00320 (see the Ipopt option $code check_derivatives_for_naninf$$).
00321 $rnext
00322 internal_error $cnext
00323 An unknown Ipopt internal error occurred.
00324 Contact the Ipopt authors through the mailing list.
00325 $tend
00326 
00327 $subhead x$$
00328 The $code x$$ field of $icode solution$$ has prototype
00329 $codei%
00330      %Vector% %solution%.x
00331 %$$
00332 and its size is equal to $icode nx$$.
00333 It is the final $latex x$$ value for the optimizer.
00334 
00335 $subhead zl$$
00336 The $code zl$$ field of $icode solution$$ has prototype
00337 $codei%
00338      %Vector% %solution%.zl
00339 %$$
00340 and its size is equal to $icode nx$$.
00341 It is the final Lagrange multipliers for the 
00342 lower bounds on $latex x$$.
00343 
00344 $subhead zu$$
00345 The $code zu$$ field of $icode solution$$ has prototype
00346 $codei%
00347      %Vector% %solution%.zu
00348 %$$
00349 and its size is equal to $icode nx$$.
00350 It is the final Lagrange multipliers for the 
00351 upper bounds on $latex x$$.
00352 
00353 $subhead g$$
00354 The $code g$$ field of $icode solution$$ has prototype
00355 $codei%
00356      %Vector% %solution%.g
00357 %$$
00358 and its size is equal to $icode ng$$.
00359 It is the final value for the constraint function $latex g(x)$$.
00360 
00361 $subhead lambda$$
00362 The $code lambda$$ field of $icode solution$$ has prototype
00363 $codei%
00364      %Vector%> %solution%.lambda
00365 %$$
00366 and its size is equal to $icode ng$$.
00367 It is the final value for the 
00368 Lagrange multipliers corresponding to the constraint function.
00369 
00370 $subhead obj_value$$
00371 The $code obj_value$$ field of $icode solution$$ has prototype
00372 $codei%
00373      double %solution%.obj_value
00374 %$$
00375 It is the final value of the objective function $latex f(x)$$.
00376 
00377 $children%
00378      example/ipopt_solve/get_started.cpp%
00379      example/ipopt_solve/retape.cpp%
00380      example/ipopt_solve/ode_inverse.cpp
00381 %$$
00382 $head Example$$
00383 All the examples return true if it succeeds and false otherwise.
00384 
00385 $subhead get_started$$
00386 The file
00387 $cref%example/ipopt_solve/get_started.cpp%ipopt_solve_get_started.cpp%$$
00388 is an example and test of $code ipopt::solve$$
00389 taken from the Ipopt manual.
00390 
00391 $subhead retape$$
00392 The file
00393 $cref%example/ipopt_solve/retape.cpp%ipopt_solve_retape.cpp%$$
00394 demonstrates when it is necessary to specify
00395 $cref/retape/ipopt_solve/options/Retape/$$ as true.
00396 
00397 $subhead ode_inverse$$
00398 The file
00399 $cref%example/ipopt_solve/ode_inverse.cpp%ipopt_solve_ode_inverse.cpp%$$
00400 demonstrates using Ipopt to solve for parameters in an ODE model.
00401      
00402 $end
00403 -------------------------------------------------------------------------------
00404 */
00405 # include <cppad/ipopt/solve_callback.hpp>
00406 
00407 namespace CppAD { // BEGIN_CPPAD_NAMESPACE
00408 namespace ipopt {
00409 /*!
00410 \file solve.hpp
00411 \brief Implement the ipopt::solve Nonlinear Programming Solver 
00412 */
00413 
00414 /*!
00415 Use Ipopt to Solve a Nonlinear Programming Problem
00416 
00417 \tparam Bvector
00418 simple vector class with elements of type bool.
00419 
00420 \tparam Dvector
00421 simple vector class with elements of type double.
00422 
00423 \tparam FG_eval
00424 function object used to evaluate f(x) and g(x); see fg_eval below.
00425 It must also support
00426 \code
00427      FG_eval::ADvector
00428 \endcode
00429 to dentify the type used for the arguments to fg_eval.
00430 
00431 \param options
00432 list of options, one for each line. 
00433 Ipopt options (are optional) and have one of the following forms
00434 \code
00435      String   name  value
00436      Numeric  name  value
00437      Integer  name  value
00438 \endcode
00439 The following other possible options are listed below:
00440 \code
00441      Retape   value
00442 \endcode
00443 
00444 
00445 \param xi
00446 initial argument value to start optimization procedure at.
00447 
00448 \param xl
00449 lower limit for argument during optimization
00450 
00451 \param xu
00452 upper limit for argument during optimization
00453 
00454 \param gl
00455 lower limit for g(x) during optimization.
00456 
00457 \param gu
00458 upper limit for g(x) during optimization.
00459 
00460 \param fg_eval
00461 function that evaluates the objective and constraints using the syntax
00462 \code
00463      fg_eval(fg, x)
00464 \endcode
00465 
00466 \param solution
00467 structure that holds the solution of the optimization.
00468 */
00469 template <class Dvector, class FG_eval>
00470 void solve(
00471      const std::string&                   options   ,
00472      const Dvector&                       xi        , 
00473      const Dvector&                       xl        ,
00474      const Dvector&                       xu        , 
00475      const Dvector&                       gl        , 
00476      const Dvector&                       gu        , 
00477      FG_eval&                             fg_eval   , 
00478      ipopt::solve_result<Dvector>&        solution  )
00479 {    bool ok = true;
00480 
00481      typedef typename FG_eval::ADvector ADvector;
00482 
00483      CPPAD_ASSERT_KNOWN(
00484           xi.size() == xl.size() && xi.size() == xu.size() ,
00485           "ipopt::solve: size of xi, xl, and xu are not all equal."
00486      );
00487      CPPAD_ASSERT_KNOWN(
00488           gl.size() == gu.size() ,
00489           "ipopt::solve: size of gl and gu are not equal."
00490      );
00491      size_t nx = xi.size();
00492      size_t ng = gl.size();
00493 
00494      // Create an IpoptApplication
00495      using Ipopt::IpoptApplication;
00496      Ipopt::SmartPtr<IpoptApplication> app = new IpoptApplication();
00497 
00498      // process the options argument
00499      size_t begin_1, end_1, begin_2, end_2, begin_3, end_3;
00500      begin_1     = 0;
00501      bool retape          = false;
00502      bool sparse_forward  = false;
00503      bool sparse_reverse  = false;
00504      while( begin_1 < options.size() )
00505      {    // split this line into tokens
00506           while( options[begin_1] == ' ')
00507                begin_1++;
00508           end_1   = options.find_first_of(" \n", begin_1);
00509           begin_2 = end_1;
00510           while( options[begin_2] == ' ')
00511                begin_2++;
00512           end_2   = options.find_first_of(" \n", begin_2);
00513           begin_3 = end_2;
00514           while( options[begin_3] == ' ')
00515                begin_3++;
00516           end_3   = options.find_first_of(" \n", begin_3);
00517 
00518           // check for errors
00519           CPPAD_ASSERT_KNOWN( 
00520                (end_1 != std::string::npos)  & 
00521                (end_2 != std::string::npos)  & 
00522                (end_3 != std::string::npos)  ,
00523                "ipopt::solve: missing '\\n' at end of an option line"
00524           );
00525           CPPAD_ASSERT_KNOWN( 
00526                (end_1 > begin_1) & (end_2 > begin_2) ,
00527                "ipopt::solve: an option line does not have two tokens"
00528           );
00529 
00530           // get first two tokens
00531           std::string tok_1 = options.substr(begin_1, end_1 - begin_1);
00532           std::string tok_2 = options.substr(begin_2, end_2 - begin_2);
00533 
00534           // get third token
00535           std::string tok_3;
00536           bool three_tok = false;
00537           three_tok |= tok_1 == "Sparse";
00538           three_tok |= tok_1 == "String";
00539           three_tok |= tok_1 == "Numeric";
00540           three_tok |= tok_1 == "Integer";
00541           if( three_tok ) 
00542           {    CPPAD_ASSERT_KNOWN( 
00543                     (end_3 > begin_3) ,
00544                     "ipopt::solve: a Sparse, String, Numeric, or Integer\n"
00545                     "option line does not have three tokens."
00546                );
00547                tok_3 = options.substr(begin_3, end_3 - begin_3);
00548           }
00549 
00550           // switch on option type
00551           if( tok_1 == "Retape" )
00552           {    CPPAD_ASSERT_KNOWN(
00553                     (tok_2 == "true") | (tok_2 == "false") ,
00554                     "ipopt::solve: Retape value is not true or false"
00555                );
00556                retape = (tok_2 == "true");
00557           }
00558           else if( tok_1 == "Sparse" )
00559           {    CPPAD_ASSERT_KNOWN(
00560                     (tok_2 == "true") | (tok_2 == "false") ,
00561                     "ipopt::solve: Sparse value is not true or false"
00562                );
00563                CPPAD_ASSERT_KNOWN(
00564                     (tok_3 == "forward") | (tok_3 == "reverse") ,
00565                     "ipopt::solve: Sparse direction is not forward or reverse"
00566                );
00567                if( tok_2 == "false" )
00568                {    sparse_forward = false;
00569                     sparse_reverse = false;
00570                }
00571                else
00572                {    sparse_forward = tok_3 == "forward";
00573                     sparse_reverse = tok_3 == "reverse";
00574                }
00575           }
00576           else if ( tok_1 == "String" )
00577                app->Options()->SetStringValue(tok_2.c_str(), tok_3.c_str());
00578           else if ( tok_1 == "Numeric" )
00579           {    Ipopt::Number value = std::atof( tok_3.c_str() ); 
00580                app->Options()->SetNumericValue(tok_2.c_str(), value);
00581           }
00582           else if ( tok_1 == "Integer" )
00583           {    Ipopt::Index value = std::atoi( tok_3.c_str() );  
00584                app->Options()->SetIntegerValue(tok_2.c_str(), value);
00585           }
00586           else CPPAD_ASSERT_KNOWN(
00587                false,
00588                "ipopt::solve: First token is not one of\n"
00589                "Retape, Sparse, String, Numeric, Integer"
00590           );
00591 
00592           begin_1 = end_3;
00593           while( options[begin_1] == ' ')
00594                begin_1++;
00595           if( options[begin_1] != '\n' ) CPPAD_ASSERT_KNOWN(
00596                false,
00597                "ipopt::solve: either more than three tokens "
00598                "or no '\\n' at end of a line"
00599           );
00600           begin_1++;
00601      }
00602      CPPAD_ASSERT_KNOWN( 
00603           ! ( retape & (sparse_forward | sparse_reverse) ) ,
00604           "ipopt::solve: retape and sparse both true is not supported."
00605      );
00606 
00607      // Initialize the IpoptApplication and process the options
00608      Ipopt::ApplicationReturnStatus status = app->Initialize();
00609      ok    &= status == Ipopt::Solve_Succeeded;
00610      if( ! ok )
00611      {    solution.status = solve_result<Dvector>::unknown; 
00612           return;
00613      }
00614 
00615      // Create an interface from Ipopt to this specific problem.
00616      // Note the assumption here that ADvector is same as cppd_ipopt::ADvector
00617      size_t nf = 1;
00618      Ipopt::SmartPtr<Ipopt::TNLP> cppad_nlp = 
00619      new CppAD::ipopt::solve_callback<Dvector, ADvector, FG_eval>(
00620           nf, 
00621           nx, 
00622           ng, 
00623           xi, 
00624           xl, 
00625           xu, 
00626           gl, 
00627           gu, 
00628           fg_eval, 
00629           retape, 
00630           sparse_forward, 
00631           sparse_reverse, 
00632           solution
00633      );
00634 
00635      // Run the IpoptApplication
00636      app->OptimizeTNLP(cppad_nlp);
00637 
00638      return;
00639 }
00640 
00641 } // end ipopt namespace
00642 } // END_CPPAD_NAMESPACE
00643 # endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines