CppAD: A C++ Algorithmic Differentiation Package
20130918
|
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