Ignore:
Timestamp:
Oct 13, 2005 6:43:08 PM (14 years ago)
Author:
andreasw
Message:
  • cleaned up line search to allow for alternative globalization scheme
File:
1 copied

Legend:

Unmodified
Added
Removed
  • branches/dev/Algorithm/IpBacktrackingLineSearch.hpp

    r541 r542  
    66//
    77// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
    8 
    9 #ifndef __IPFILTERLINESEARCH_HPP__
    10 #define __IPFILTERLINESEARCH_HPP__
    11 
    12 #include "IpFilter.hpp"
     8//           Andreas Waechter                 IBM    2005-10-13
     9//               derived file from IpFilterLineSearch.hpp
     10
     11#ifndef __IPBACKTRACKINGLINESEARCH_HPP__
     12#define __IPBACKTRACKINGLINESEARCH_HPP__
     13
    1314#include "IpLineSearch.hpp"
     15#include "IpBacktrackingLSAcceptor.hpp"
    1416#include "IpRestoPhase.hpp"
    15 #include "IpPDSystemSolver.hpp"
    1617#include "IpConvCheck.hpp"
    1718
     
    1920{
    2021
    21   /** Filter line search.  This class implements the filter line
    22    *  search procedure.
     22  /** General implementation of a backtracking line search.  This
     23   *  class can be used to perform the filter line search procedure or
     24   *  other procedures.  The BacktrackingLSAcceptor is used to
     25   *  determine whether trial points are acceptable (e.g., based on a
     26   *  filter or other methods).
     27   *
     28   *  This backtracking line search knows of a restoration phase
     29   *  (which is called when the trial step size becomes too small or
     30   *  no search direction could be computed).  It also has the notion
     31   *  of a "soft restoration phase," which uses the regular steps but
     32   *  decides on the acceptability based on other measures than the
     33   *  regular ones (e.g., reduction of the PD error instead of
     34   *  acceptability to a filter mechanism).
    2335   */
    24   class FilterLineSearch : public LineSearch
     36  class BacktrackingLineSearch : public LineSearch
    2537  {
    2638  public:
    2739    /**@name Constructors/Destructors */
    2840    //@{
    29     /** Constructor.  The PDSystemSolver object only needs to be
     41    /** Constructor.  The acceptor implements the acceptance test for
     42     *  the line search. The PDSystemSolver object only needs to be
    3043     *  provided (i.e. not NULL) if second order correction is to be
    3144     *  used.  The ConvergenceCheck object is used to determine
     
    3346     *  restoration phase is not started if the acceptability level
    3447     *  has been reached).  If conv_check is NULL, we assume that the
    35      *  current iterate is not acceptable. */
    36     FilterLineSearch(const SmartPtr<RestorationPhase>& resto_phase,
    37                      const SmartPtr<PDSystemSolver>& pd_solver,
    38                      const SmartPtr<ConvergenceCheck>& conv_check
    39                     );
     48     *  current iterate is not acceptable (in the sense of the
     49     *  acceptable_tol option). */
     50    BacktrackingLineSearch(const SmartPtr<BacktrackingLSAcceptor>& acceptor,
     51                           const SmartPtr<RestorationPhase>& resto_phase,
     52                           const SmartPtr<ConvergenceCheck>& conv_check
     53                          );
    4054
    4155    /** Default destructor */
    42     virtual ~FilterLineSearch();
     56    virtual ~BacktrackingLineSearch();
    4357    //@}
    4458
     
    8599    }
    86100
    87     /**@name Trial Point Accepting Methods. Used internally to check certain
    88      * acceptability criteria and used externally (by the restoration phase
    89      * convergence check object, for instance)
    90      */
    91     //@{
    92     /** Checks if a trial point is acceptable to the current iterate */
    93     bool IsAcceptableToCurrentIterate(Number trial_barr, Number trial_theta,
    94                                       bool called_from_restoration=false) const;
    95 
    96     /** Checks if a trial point is acceptable to the current filter */
    97     bool IsAcceptableToCurrentFilter(Number trial_barr, Number trial_theta) const;
    98     //@}
    99 
    100101    /** Methods for OptionsList */
    101102    //@{
     
    113114    //@{
    114115    /** Copy Constructor */
    115     FilterLineSearch(const FilterLineSearch&);
     116    BacktrackingLineSearch(const BacktrackingLineSearch&);
    116117
    117118    /** Overloaded Equals Operator */
    118     void operator=(const FilterLineSearch&);
    119     //@}
    120 
    121     /** @name Filter information */
    122     //@{
    123     /** Upper bound on infeasibility */
    124     Number theta_max_;
    125     Number theta_max_fact_;
    126 
    127     /** Infeasibility switching bound */
    128     Number theta_min_;
    129     Number theta_min_fact_;
    130     //@}
    131 
    132     /** Method for checking if the current step size satisfies the
    133      *  f-type switching condition.  Here, we use the search direction
    134      *  stored in ip_data
    135      */
    136     bool IsFtype(Number alpha_primal_test);
    137 
    138     /** Method for checking the Armijo condition, given a trial step
    139      *  size.  The test uses the search direction stored in ip_data,
    140      *  and the values of the functions at the trial point in ip_data.
    141      */
    142     bool ArmijoHolds(Number alpha_primal_test);
    143 
    144     /** Method to calculate alpha_min (minimum alpha before going to
    145      *  restoration
    146      */
    147     Number CalculateAlphaMin();
    148 
    149     /** Augment the filter used on the current values of the barrier
    150      *  objective function and the contraint violation */
    151     void AugmentFilter();
     119    void operator=(const BacktrackingLineSearch&);
     120    //@}
    152121
    153122    /** Method performing the backtracking line search.  The return
     
    194163    /** Try a step for the soft restoration phase and check if it is
    195164     *  acceptable.  The step size is identical for all variables.  A
    196      *  point is accepted if it is acceptable for the original filter
    197      *  (in which case satisfies_original_filter = true on return), or
    198      *  if the primal-dual system error was decrease by at least the
    199      *  factor soft_resto_pderror_reduction_factor_.  The return value is
    200      *  true, if the trial point was acceptable. */
     165     *  point is accepted if it is acceptable for the original
     166     *  acceptability criterion (in which case
     167     *  satisfies_original_criterion = true on return), or if the
     168     *  primal-dual system error was decrease by at least the factor
     169     *  soft_resto_pderror_reduction_factor_.  The return value is
     170     *  true, if the trial point was acceptable for the soft
     171     *  restoration phase. */
    201172    bool TrySoftRestoStep(SmartPtr<IteratesVector>& actual_delta,
    202                           bool &satisfies_original_filter);
     173                          bool &satisfies_original_criterion);
    203174
    204175    /** Try a second order correction for the constraints.  If the
     
    245216    bool RestoreAcceptablePoint();
    246217
    247     /** Method for determining if the current iterate is acceptable.
    248      *  This is a wrapper for same method from ConvergenceCheck, but
    249      *  returns false, if no ConvergenceCheck object is provided. */
     218    /** Method for determining if the current iterate is acceptable
     219     *  (in the sense of the acceptable_tol options).  This is a
     220     *  wrapper for same method from ConvergenceCheck, but returns
     221     *  false, if no ConvergenceCheck object is provided. */
    250222    bool CurrentIsAcceptable();
    251223
    252224    /** @name Parameters for the filter algorithm.  Names as in the paper */
    253225    //@{
    254     /** \f$ \eta_{\varphi} \f$ */
    255     Number eta_phi_;
    256     /** \f$ \delta \f$ */
    257     Number delta_;
    258     /** \f$ s_{\varphi} \f$ */
    259     Number s_phi_;
    260     /** \f$ s_{\Theta} \f$ */
    261     Number s_theta_;
    262     /** \f$ \gamma_{\varphi} \f$ */
    263     Number gamma_phi_;
    264     /** \f$ \gamma_{\Theta} \f$ */
    265     Number gamma_theta_;
    266     /** \f$ \gamma_{\alpha} \f$ */
    267     Number alpha_min_frac_;
    268226    /** factor by which search direction is to be shortened if trial
    269227     *  point is rejected. */
    270228    Number alpha_red_factor_;
    271     /** Maximal number of second order correction steps */
    272     Index max_soc_;
    273     /** Required reduction in constraint violation before trying
    274      *  multiple second order correction steps \f$ \kappa_{soc}\f$.
    275      */
    276     Number kappa_soc_;
    277     /** Maximal increase in objective function in orders of magnitute
    278      *  (log10).  If the log10(barrier objective function) is
    279      *  increased more than this compared to the current point, the
    280      *  trial point is rejected. */
    281     Number obj_max_inc_;
    282229
    283230    /** enumeration for the different alpha_for_y_ settings */
     
    297244    AlphaForYEnum alpha_for_y_;
    298245
     246    /** Reduction factor for the restoration phase that accepts steps
     247     *  reducing the optimality error ("soft restoration phase"). If
     248     *  0., then this restoration phase is not enabled. */
     249    Number soft_resto_pderror_reduction_factor_;
     250
    299251    /** Flag indicating whether magic steps should be used. */
    300252    bool magic_steps_;
    301     /** enumeration for the corrector type */
    302     enum CorrectorTypeEnum {
    303       NO_CORRECTOR=0,
    304       AFFINE_CORRECTOR,
    305       PRIMAL_DUAL_CORRECTOR
    306     };
    307     /** Type of corrector steps that should be tried. */
    308     CorrectorTypeEnum corrector_type_;
    309253    /** Flag indicating whether the line search should always accept
    310254     *  the full (fraction-to-the-boundary) step. */
    311255    bool accept_every_trial_step_;
    312     /** parameter in heurstic that determines whether corrector step
    313     should be tried. */
    314     Number corrector_compl_avrg_red_fact_;
    315     /** Flag indicating whether the corrector should be skipped in an
    316      *  iteration in which negative curvature is detected */
    317     bool skip_corr_if_neg_curv_;
    318     /** Flag indicating whether the corrector should be skipped during
    319      *  the monotone mu mode. */
    320     bool skip_corr_in_monotone_mode_;
    321256    /** Indicates whether problem can be expected to be infeasible.
    322257     *  This will trigger requesting a tighter reduction in
     
    329264     *  disabled for the rest of the optimization run. */
    330265    Number expect_infeasible_problem_ctol_;
    331     /** Reduction factor for the restoration phase that accepts steps
    332      *  reducing the optimality error ("soft restoration phase"). If
    333      *  0., then this restoration phase is not enabled. */
    334     Number soft_resto_pderror_reduction_factor_;
    335266
    336267    /** Tolerance for detecting tiny steps. */
     
    349280    /** @name Information related to watchdog procedure */
    350281    //@{
    351     /** Constraint violation at the point with respect to which
    352      *  progress is to be made */
    353     Number reference_theta_;
    354     /** Barrier objective function at the point with respect to which
    355      *  progress is to be made */
    356     Number reference_barr_;
    357     /** Barrier gradient transpose search direction at the point with
    358      *  respect to which progress is to be made */
    359     Number reference_gradBarrTDelta_;
    360282    /** Flag indicating if the watchdog is active */
    361283    bool in_watchdog_;
     
    366288    /** Step size for Armijo test in watch dog */
    367289    Number watchdog_alpha_primal_test_;
    368     /** Constraint violation at reference point */
    369     Number watchdog_theta_;
    370     /** Barrier objective function at reference point */
    371     Number watchdog_barr_;
    372     /** Barrier gradient transpose search direction at reference point */
    373     Number watchdog_gradBarrTDelta_;
    374290    /** Watchdog reference iterate */
    375291    SmartPtr<const IteratesVector> watchdog_iterate_;
     
    383299    SmartPtr<const IteratesVector> acceptable_iterate_;
    384300    //@}
    385 
    386     /** Filter with entries */
    387     Filter filter_;
    388301
    389302    /** Flag indicating whether the line search is to be performed
     
    413326    /** @name Strategy objective that are used */
    414327    //@{
     328    SmartPtr<BacktrackingLSAcceptor> acceptor_;
    415329    SmartPtr<RestorationPhase> resto_phase_;
    416     SmartPtr<PDSystemSolver> pd_solver_;
    417330    SmartPtr<ConvergenceCheck> conv_check_;
    418331    //@}
Note: See TracChangeset for help on using the changeset viewer.