46 #include "ConstrainedOptPack_DirectLineSearchArmQuad_Strategy.hpp"
47 #include "ConstrainedOptPack_MeritFuncCalc1D.hpp"
50 namespace ConstrainedOptPack {
51 inline value_type min(value_type v1, value_type v2) {
52 return (v1 < v2) ? v1 : v2;
54 inline value_type max(value_type v1, value_type v2) {
55 return (v1 > v2) ? v1 : v2;
70 ,max_out_iter_(max_out_iter)
90 , value_type* alpha_k, value_type* phi_kp1
97 throw std::logic_error(
"DirectLineSearchArmQuad_Strategy::do_line_search(): "
98 "alpha_k can't start out less than 0.0" );
101 validate_parameters();
107 prec_saved = out->precision();
108 *out << std::setprecision(prec)
109 <<
"\nStarting Armijo Quadratic interpolation linesearch ...\n";
114 const value_type Dphi_k = phi.
deriv();
119 *out <<
"\nmax_out_iter == true, maxing out the number of iterations!";
120 *out <<
"\nDphi_k = " << Dphi_k
121 <<
"\nphi_k = " << phi_k <<
"\n\n"
123 << setw(w) <<
"alpha_k"
124 << setw(w) <<
"phi_kp1"
125 << setw(w) <<
"phi_kp1-frac_phi\n"
127 << setw(w) <<
"----------------"
128 << setw(w) <<
"----------------"
129 << setw(w) <<
"----------------\n";
134 "DirectLineSearchArmQuad_Strategy::do_line_search(): "
135 "The given d_k is not a descent direction for the given "
136 "phi (phi.deriv() is >= 0)" );
139 value_type best_alpha = *alpha_k, best_phi = *phi_kp1;
142 bool success =
false;
143 for( num_iter_ = 0; num_iter_ < max_iter(); ++num_iter_ ) {
147 value_type frac_phi = phi_k + eta() * (*alpha_k) * Dphi_k;
149 *out << setw(5) << num_iter_
150 << setw(w) << *alpha_k
151 << setw(w) << *phi_kp1
152 << setw(w) << ((*phi_kp1)-frac_phi) << endl;
155 if( RTOp_is_nan_inf( *phi_kp1 ) ) {
157 *alpha_k = min_frac()*(*alpha_k);
164 if( *phi_kp1 < frac_phi ) {
167 if( !max_out_iter() || ( max_out_iter() && num_iter_ == max_iter() - 1 ) )
179 value_type alpha_quad = ( -0.5 * Dphi_k * (*alpha_k) * (*alpha_k) )
180 / ( (*phi_kp1) - phi_k - (*alpha_k) * Dphi_k );
182 *alpha_k = min( max(min_frac()*(*alpha_k),alpha_quad), max_frac()*(*alpha_k) );
188 *phi_kp1 = phi(*alpha_k);
191 if(*phi_kp1 < best_phi) {
193 best_alpha = *alpha_k;
200 out->precision(prec_saved);
209 *alpha_k = best_alpha;
210 *phi_kp1 = phi(best_alpha);
215 std::ostream& out,
const std::string& L)
const
218 << L <<
"*** start line search using the Armijo cord test and quadratic interpolation of alpha\n"
219 << L <<
"default: max_ls_iter = " << max_iter() << std::endl
220 << L <<
" eta = " << eta() << std::endl
221 << L <<
" min_frac = " << min_frac() << std::endl
222 << L <<
" max_frac = " << max_frac() << std::endl
223 << L <<
" max_out_iter = " << max_out_iter() << std::endl
224 << L <<
"Dphi_k = phi.deriv()\n"
225 << L <<
"if Dphi_k >= 0\n"
226 << L <<
" throw not_descent_direction\n"
227 << L <<
" end line search\n"
229 << L <<
"best_alpha = alpha_k\n"
230 << L <<
"best_phi = phi_kp1\n"
231 << L <<
"for num_iter = 0... max_ls_iter\n"
232 << L <<
" frac_phi = phi_k + eta * alpha_k * Dphi_k\n"
233 << L <<
" print iteration\n"
234 << L <<
" if phi_kp1 is not a valid number then\n"
235 << L <<
" *** Cut back the step so the NLP's functions\n"
236 << L <<
" *** will hopefully be defined.\n"
237 << L <<
" alpha_k = min_frac * alpha_k\n"
238 << L <<
" best_alpha = 0\n"
239 << L <<
" best_phi = phi_k\n"
241 << L <<
" if ( phi_kp1 < frac_phi ) then\n"
242 << L <<
" *** We have found an acceptable point\n"
243 << L <<
" if( !max_out_iter || max_out_iter && num_iter == max_ls_iter - 1 ) )\n"
244 << L <<
" end line search\n"
247 << L <<
" *** Use a quadratic interpoation to minimize phi(alpha)\n"
248 << L <<
" alpha_quad = (-0.5 * Dphi_k * alpha_k^2) / ( phi_kp1 - phi_k - alpha_k*Dphi_k )\n"
249 << L <<
" alpha_k = min( max( min_frac*alpha_k, alpha_quad ), max_frac*alpha_k )\n"
251 << L <<
" phi_kp1 = phi(alpha_k)\n"
252 << L <<
" if phi_kp1 < best_phi\n"
253 << L <<
" best_phi = phi_kp1\n"
254 << L <<
" best_alpha = alpha_k\n"
257 << L <<
"*** If you get there the line search failed.\n"
258 << L <<
"alpha_k = best_alpha\n"
259 << L <<
"phi_kp1 = phi(alpha_k)\n"
260 << L <<
"linesearch_failure = true\n";
263 void ConstrainedOptPack::DirectLineSearchArmQuad_Strategy::validate_parameters()
const
265 if( eta() < 0.0 || 1.0 < eta() ) {
266 std::ostringstream omsg;
268 <<
"DirectLineSearchArmQuad_Strategy::validate_parameters() : "
269 <<
"Error, eta = " << eta() <<
" is not in the range [0, 1]";
270 throw std::invalid_argument( omsg.str() );
272 if( min_frac() < 0.0 || 1.0 < min_frac() ) {
273 std::ostringstream omsg;
275 <<
"DirectLineSearchArmQuad_Strategy::validate_parameters() : "
276 <<
"Error, min_frac = " << min_frac() <<
" is not in the range [0, 1]";
277 throw std::invalid_argument( omsg.str() );
279 if( max_frac() < 0.0 || ( !max_out_iter() && 1.0 < max_frac() ) ) {
280 std::ostringstream omsg;
282 <<
"DirectLineSearchArmQuad_Strategy::validate_parameters() : "
283 <<
"Error, max_frac = " << max_frac() <<
" is not in the range [0, 1]";
284 throw std::invalid_argument( omsg.str() );
286 if( max_frac() < min_frac() ) {
287 std::ostringstream omsg;
289 <<
"DirectLineSearchArmQuad_Strategy::validate_parameters() : "
290 <<
"Error, max_frac = " << max_frac()
291 <<
" < min_frac = " << min_frac();;
292 throw std::invalid_argument( omsg.str() );
Abstracts a 1D merit function {abstract}.
bool do_line_search(const MeritFuncCalc1D &phi, value_type phi_k, value_type *alpha_k, value_type *phi_kp1, std::ostream *out)
Performs the following line search:
void set_max_iter(int max_iter)
void print_algorithm(std::ostream &out, const std::string &leading_str) const
Thrown if the direction vector d_k is not a descent direction for the merit funciton.
virtual value_type deriv() const =0
Return the derivative of the merit function at alpha = 0.
int num_iterations() const
DirectLineSearchArmQuad_Strategy(int max_iter=20, value_type eta=1.0e-4, value_type min_frac=0.1, value_type max_frac=0.5, bool max_out_iter=false)
Constructs with default settings.