MoochoPack : Framework for Large-Scale Optimization Algorithms Version of the Day
MoochoPack_LineSearchFilter_Step.hpp
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
00005 //                  Copyright (2003) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00038 // 
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 #ifndef LINE_SEARCH_FILTER_STEP_H
00043 #define LINE_SEARCH_FILTER_STEP_H
00044 
00045 #include <list>
00046 
00047 #include "MoochoPack_Types.hpp"
00048 #include "IterationPack_AlgorithmStep.hpp"
00049 #include "IterationPack_CastIQMember.hpp"
00050 #include "Teuchos_StandardCompositionMacros.hpp"
00051 #include "Teuchos_StandardMemberCompositionMacros.hpp"
00052 
00053 #include "IterationPack_AlgorithmState.hpp"
00054 
00055 namespace MoochoPack {
00056  
00057 // structure for storing filter points 
00058 class FilterEntry 
00059 {
00060 public:
00061   FilterEntry( value_type new_f, value_type new_theta, int new_iter)
00062     : f(new_f), theta(new_theta), iter(new_iter) {}
00063     
00064   value_type f;
00065   value_type theta;
00066   int iter;
00067 };
00068 
00069 // It is critical that an std::list be used because of the way iterators are
00070 // used!
00071 typedef std::list< FilterEntry > Filter_T;
00072 
00073 const std::string FILTER_IQ_STRING = "LS_FilterEntries";
00074 
00079 class LineSearchFilter_Step
00080   : public IterationPack::AlgorithmStep // doxygen needs full path
00081 {
00082 public:
00083     
00086 
00088   static value_type F_MIN_UNBOUNDED;
00089   
00091   
00094   
00099   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, gamma_theta );
00100 
00105   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, gamma_f );
00106 
00113   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, f_min );
00114 
00119   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, gamma_alpha );
00120 
00125   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, delta );
00126   
00131   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, s_f );
00132 
00137   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, s_theta );
00138 
00144   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, theta_small_fact );
00145 
00150   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, theta_max );
00151 
00156   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, eta_f );
00157 
00162   STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, back_track_frac );
00163 
00166   LineSearchFilter_Step(
00167     Teuchos::RCP<NLPInterfacePack::NLP> nlp
00168     ,const std::string         obj_iq_name      = "f"
00169     ,const std::string         grad_obj_iq_name = "Gf"
00170     ,const value_type          &gamma_theta      = 1e-5
00171     ,const value_type          &gamma_f          = 1e-5
00172     ,const value_type          &f_min            = F_MIN_UNBOUNDED
00173     ,const value_type          &gamma_alpha      = 5e-2
00174     ,const value_type          &delta            = 1e-4
00175     ,const value_type          &s_theta          = 1.1
00176     ,const value_type          &s_f              = 2.3
00177     ,const value_type          &theta_small_fact = 1e-4 
00178     ,const value_type          &theta_max        = 1e10
00179     ,const value_type          &eta_f            = 1e-4
00180     ,const value_type          &back_track_frac  = 0.5
00181     );
00182 
00184   
00187   ~LineSearchFilter_Step();
00188 
00190 
00194   bool do_step( Algorithm& algo, poss_type step_poss,
00195                 IterationPack::EDoStepType type,
00196                 poss_type assoc_step_poss);
00198   void print_step( const Algorithm& algo, poss_type step_poss,
00199                    IterationPack::EDoStepType type,
00200                    poss_type assoc_step_poss, std::ostream& out,
00201                    const std::string& leading_str ) const;
00203 
00204 private:
00205 
00206   // /////////////////////////////
00207   // Private data members
00208 
00209   // Private Data
00210   CastIQMember<Filter_T> filter_;
00211 
00213   CastIQMember<value_type> obj_f_;
00214 
00216   CastIQMember<VectorMutable> grad_obj_f_;
00217 
00218   // nlp to use for calculations
00219   Teuchos::RCP<NLPInterfacePack::NLP> nlp_;
00220 
00221   // /////////////////////////////
00222   // Private member functions
00223 
00224   // Validate input parameters - fix if possible
00225   bool ValidatePoint(
00226     const IterQuantityAccess<VectorMutable>& x,
00227     const IterQuantityAccess<value_type>& f,
00228     const IterQuantityAccess<VectorMutable>* c,
00229     const IterQuantityAccess<VectorMutable>* h,
00230     const bool throw_excpt
00231     ) const;
00232 
00233   // Check that new point is not within taboo region of filter
00234   bool CheckFilterAcceptability(
00235     const value_type f, 
00236     const value_type theta,
00237     const AlgorithmState& s
00238     ) const;
00239   
00240   // Check the Armijo condition on f
00241   bool CheckArmijo(
00242     const value_type Gf_t_dk, 
00243     const value_type alpha_k, 
00244     const IterQuantityAccess<value_type>& f_iq
00245     ) const;
00246 
00247   // Check if f or c has sufficient reduction
00248   bool CheckFractionalReduction(
00249     const IterQuantityAccess<value_type>& f_iq,
00250     const value_type gamma_f_used,
00251     const value_type theta_kp1, 
00252     const value_type theta_k
00253     ) const;
00254 
00255   // Calculate the new point given d and alpha
00256   void UpdatePoint(
00257     const VectorMutable& d,
00258     value_type alpha, 
00259     IterQuantityAccess<VectorMutable>& x,
00260     IterQuantityAccess<value_type>& f,
00261     IterQuantityAccess<VectorMutable>* c,
00262     IterQuantityAccess<VectorMutable>* h,
00263     NLP& nlp
00264     ) const;
00265 
00266   // Calculate the minimum alpha before hitting restoration phase
00267   value_type CalculateAlphaMin(
00268     const value_type gamma_f_used,
00269     const value_type Gf_t_dk, 
00270     const value_type theta_k,
00271     const value_type theta_small
00272     ) const;
00273 
00274   // Calculate the constraint norm
00275   value_type CalculateTheta_k(
00276     const IterQuantityAccess<VectorMutable>* c,
00277     const IterQuantityAccess<VectorMutable>* h,
00278     int k
00279     ) const;
00280 
00281   // Calculate the value of gamma_k to use
00282   value_type CalculateGammaFUsed(
00283     const IterQuantityAccess<value_type> &f,
00284     const value_type theta_k,
00285     const EJournalOutputLevel olevel,
00286     std::ostream &out
00287     ) const;
00288 
00289   // decide if we should switch to Armijo for objective
00290   bool ShouldSwitchToArmijo(
00291     const value_type Gf_t_dk,
00292     const value_type alpha_k,
00293     const value_type theta_k,
00294     const value_type theta_small
00295     ) const;
00296 
00297   // Update the filter from the last iteration
00298   void UpdateFilter( IterationPack::AlgorithmState& s ) const;
00299 
00300   // Update the filter from the last iteration and Augment it with
00301   // the new point
00302   void AugmentFilter(
00303     const value_type gamma_f_used,
00304     const value_type f_with_boundary,
00305     const value_type theta_with_boundary,
00306     IterationPack::AlgorithmState& s,
00307     const EJournalOutputLevel olevel,
00308     std::ostream &out
00309     ) const;
00310     
00311 };  // end class LineSearchFilter_Step
00312 
00313 } // end namespace MoochoPack 
00314 
00315 #endif  // LINE_SEARCH_FILTER_STEP_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends