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 moved

Legend:

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

    r541 r542  
    1 // Copyright (C) 2004,2005 International Business Machines and others.
     1// Copyright (C) 2005 International Business Machines and others.
    22// All Rights Reserved.
    33// This code is published under the Common Public License.
     
    55// $Id$
    66//
    7 // Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
    8 
    9 #ifndef __IPFILTERLINESEARCH_HPP__
    10 #define __IPFILTERLINESEARCH_HPP__
     7// Authors:  Andreas Waechter                 IBM    2005-10-13
     8//               derived file from IpFilterLineSearch.hpp
     9
     10#ifndef __IPFILTERLSACCEPTOR_HPP__
     11#define __IPFILTERLSACCEPTOR_HPP__
    1112
    1213#include "IpFilter.hpp"
    13 #include "IpLineSearch.hpp"
    14 #include "IpRestoPhase.hpp"
     14#include "IpBacktrackingLSAcceptor.hpp"
    1515#include "IpPDSystemSolver.hpp"
    16 #include "IpConvCheck.hpp"
    1716
    1817namespace Ipopt
     
    2221   *  search procedure.
    2322   */
    24   class FilterLineSearch : public LineSearch
     23  class FilterLSAcceptor : public BacktrackingLSAcceptor
    2524  {
    2625  public:
     
    2827    //@{
    2928    /** Constructor.  The PDSystemSolver object only needs to be
    30      *  provided (i.e. not NULL) if second order correction is to be
    31      *  used.  The ConvergenceCheck object is used to determine
    32      *  whether the current iterate is acceptable (for example, the
    33      *  restoration phase is not started if the acceptability level
    34      *  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                     );
     29     *  provided (i.e. not NULL) if second order correction or
     30     *  corrector steps are to be used. */
     31    FilterLSAcceptor(const SmartPtr<PDSystemSolver>& pd_solver);
    4032
    4133    /** Default destructor */
    42     virtual ~FilterLineSearch();
     34    virtual ~FilterLSAcceptor();
    4335    //@}
    4436
     
    4739                                const std::string& prefix);
    4840
    49     /** Perform the line search.  It is assumed that the search
    50      *  direction is computed in the data object.
    51      */
    52     virtual void FindAcceptableTrialPoint();
    53 
    54     /** Reset the line search.
     41    /** Reset the acceptor.
    5542     *  This function should be called if all previous information
    5643     *  should be discarded when the line search is performed the
     
    6047    virtual void Reset();
    6148
    62     /** Set flag indicating whether a very rigorous line search should
    63      *  be performed.  If this flag is set to true, the line search
    64      *  algorithm might decide to abort the line search and not to
    65      *  accept a new iterate.  If the line search decided not to
    66      *  accept a new iterate, the return value of
    67      *  CheckSkippedLineSearch() is true at the next call.  For
    68      *  example, in the non-monotone barrier parameter update
    69      *  procedure, the filter algorithm should not switch to the
    70      *  restoration phase in the free mode; instead, the algorithm
    71      *  should swtich to the fixed mode.
    72      */
    73     virtual void SetRigorousLineSearch(bool rigorous)
    74     {
    75       rigorous_ = rigorous;
    76     }
    77 
    78     /** Check if the line search procedure didn't accept a new iterate
    79      *  during the last call of FindAcceptableTrialPoint().
    80      * 
    81      */
    82     virtual bool CheckSkippedLineSearch()
    83     {
    84       return skipped_line_search_;
    85     }
     49    /** Initialization for the next line search.  The flag in_watchdog
     50     *  indicates if we are currently in an active watchdog
     51     *  procedure. */
     52    virtual void InitThisLineSearch(bool in_watchdog);
     53
     54    /** Method that is called before the restoration phase is called.
     55     *  Here, we can set up things that are required in the
     56     *  termination test for the restoration phase, such as augmenting
     57     *  a filter. */
     58    virtual void PrepareRestoPhaseStart();
     59
     60    /** Method returning the lower bound on the trial step sizes.  If
     61     *  the backtracking procedure encounters a trial step size below
     62     *  this value after the first trial set, it swtiches to the
     63     *  (soft) restoration phase. */
     64    virtual Number CalculateAlphaMin();
     65
     66    /** Method for checking if current trial point is acceptable.
     67     *  It is assumed that the delta information in ip_data is the
     68     *  search direction used in criteria.  The primal trial point has
     69     *  to be set before the call.
     70     */
     71    virtual bool CheckAcceptabilityOfTrialPoint(Number alpha_primal);
     72
     73    /** Try a second order correction for the constraints.  If the
     74     *  first trial step (with incoming alpha_primal) has been reject,
     75     *  this tries up to max_soc_ second order corrections for the
     76     *  constraints.  Here, alpha_primal_test is the step size that
     77     *  has to be used in the filter acceptance tests.  On output
     78     *  actual_delta_ has been set to the step including the
     79     *  second order correction if it has been accepted, otherwise it
     80     *  is unchanged.  If the SOC step has been accepted, alpha_primal
     81     *  has the fraction-to-the-boundary value for the SOC step on output.
     82     *  The return value is true, if a SOC step has been accepted.
     83     */
     84    virtual bool TrySecondOrderCorrection(Number alpha_primal_test,
     85                                          Number& alpha_primal,
     86                                          SmartPtr<IteratesVector>& actual_delta);
     87
     88    /** Try higher order corrector (for fast local convergence).  In
     89     *  contrast to a second order correction step, which tries to
     90     *  make an unacceptable point acceptable by improving constraint
     91     *  violation, this corrector step is tried even if the regular
     92     *  primal-dual step is acceptable.
     93     */
     94    virtual bool TryCorrector(Number alpha_primal_test,
     95                              Number& alpha_primal,
     96                              SmartPtr<IteratesVector>& actual_delta);
     97
     98    /** Method for ending the current line search.  When it is called,
     99     *  the internal data should be updates, e.g., the filter might be
     100     *  augmented.  alpha_primal_test is the value of alpha that has
     101     *  been used for in the acceptence test ealier. */
     102    virtual char UpdateForNextIteration(Number alpha_primal_test);
     103
     104    /** Method for setting internal data if the watchdog procedure is
     105     *  started. */
     106    virtual void StartWatchDog();
     107
     108    /** Method for setting internal data if the watchdog procedure is
     109     *  stopped. */
     110    virtual void StopWatchDog();
    86111
    87112    /**@name Trial Point Accepting Methods. Used internally to check certain
     
    113138    //@{
    114139    /** Copy Constructor */
    115     FilterLineSearch(const FilterLineSearch&);
     140    FilterLSAcceptor(const FilterLSAcceptor&);
    116141
    117142    /** Overloaded Equals Operator */
    118     void operator=(const FilterLineSearch&);
     143    void operator=(const FilterLSAcceptor&);
    119144    //@}
    120145
     
    142167    bool ArmijoHolds(Number alpha_primal_test);
    143168
    144     /** Method to calculate alpha_min (minimum alpha before going to
    145      *  restoration
    146      */
    147     Number CalculateAlphaMin();
    148 
    149169    /** Augment the filter used on the current values of the barrier
    150170     *  objective function and the contraint violation */
    151171    void AugmentFilter();
    152 
    153     /** Method performing the backtracking line search.  The return
    154      *  value indicates if the step acceptance criteria are met.  If
    155      *  the watchdog is active, only one trial step is performed (and
    156      *  the trial values are set accordingly). */
    157     bool DoBacktrackingLineSearch(bool skip_first_trial_point,
    158                                   Number& alpha_primal,
    159                                   bool& corr_taken,
    160                                   bool& soc_taken,
    161                                   Index& n_steps,
    162                                   bool& evaluation_error,
    163                                   SmartPtr<IteratesVector>& actual_delta);
    164 
    165     /** Method for starting the watch dog.  Set all appropriate fields
    166      *  accordingly */
    167     void StartWatchDog();
    168 
    169     /** Method for stopping the watch dog.  Set all appropriate fields
    170      *  accordingly. */
    171     void StopWatchDog(SmartPtr<IteratesVector>& actual_delta);
    172 
    173     /** Method for checking if current trial point is acceptable.
    174      *  It is assumed that the delta information in ip_data is the
    175      *  search direction used in criteria.  The primal trial point has
    176      *  to be set before the call.
    177      */
    178     bool CheckAcceptabilityOfTrialPoint(Number alpha_primal);
    179172
    180173    /** Check comparison "lhs <= rhs", using machine precision based on BasVal */
     
    182175    //     allow for different relaxation parameters values
    183176    static bool Compare_le(Number lhs, Number rhs, Number BasVal);
    184 
    185     /** Method for setting the dual variables in the trial fields in
    186      *  IpData, given the search direction.  The step size for the
    187      *  bound multipliers is alpha_dual (the fraction-to-the-boundary
    188      *  step size), and the step size for the equality constraint
    189      *  multipliers depends on the choice of alpha_for_y. */
    190     void PerformDualStep(Number alpha_primal,
    191                          Number alpha_dual,
    192                          SmartPtr<IteratesVector>& delta);
    193 
    194     /** Try a step for the soft restoration phase and check if it is
    195      *  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. */
    201     bool TrySoftRestoStep(SmartPtr<IteratesVector>& actual_delta,
    202                           bool &satisfies_original_filter);
    203 
    204     /** Try a second order correction for the constraints.  If the
    205      *  first trial step (with incoming alpha_primal) has been reject,
    206      *  this tries up to max_soc_ second order corrections for the
    207      *  constraints.  Here, alpha_primal_test is the step size that
    208      *  has to be used in the filter acceptance tests.  On output
    209      *  actual_delta_... has been set to the steps including the
    210      *  second order correction if it has been accepted, otherwise it
    211      *  is unchanged.  If the SOC step has been accepted, alpha_primal
    212      *  has the fraction-to-the-boundary value for the SOC step on output.
    213      *  The return value is true, if an SOC step has been accepted.
    214      */
    215     bool TrySecondOrderCorrection(Number alpha_primal_test,
    216                                   Number& alpha_primal,
    217                                   SmartPtr<IteratesVector>& actual_delta);
    218 
    219     /** Try higher order corrector (for fast local convergence).  In
    220      *  contrast to a second order correction step, which tries to
    221      *  make an unacceptable point acceptable by improving constraint
    222      *  violation, this corrector step is tried even if the regular
    223      *  primal-dual step is acceptable.
    224      */
    225     bool TryCorrector(Number alpha_primal_test,
    226                       Number& alpha_primal,
    227                       SmartPtr<IteratesVector>& actual_delta);
    228 
    229     /** Perform magic steps.  Take the current values of the slacks in
    230      *  trial and replace them by better ones that lead to smaller
    231      *  values of the barrier function and less constraint
    232      *  violation. */
    233     void PerformMagicStep();
    234 
    235     /** Detect if the search direction is too small.  This should be
    236      *  true if the search direction is so small that if makes
    237      *  numerically no difference. */
    238     bool DetectTinyStep();
    239 
    240     /** Store current iterate as acceptable point */
    241     void StoreAcceptablePoint();
    242 
    243     /** Restore acceptable point into the current fields of IpData if
    244      *  found. Returns true if such as point is available. */
    245     bool RestoreAcceptablePoint();
    246 
    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. */
    250     bool CurrentIsAcceptable();
    251177
    252178    /** @name Parameters for the filter algorithm.  Names as in the paper */
     
    266192    /** \f$ \gamma_{\alpha} \f$ */
    267193    Number alpha_min_frac_;
    268     /** factor by which search direction is to be shortened if trial
    269      *  point is rejected. */
    270     Number alpha_red_factor_;
    271194    /** Maximal number of second order correction steps */
    272195    Index max_soc_;
     
    281204    Number obj_max_inc_;
    282205
    283     /** enumeration for the different alpha_for_y_ settings */
    284     enum AlphaForYEnum {
    285       PRIMAL_ALPHA_FOR_Y=0,
    286       DUAL_ALPHA_FOR_Y,
    287       MIN_ALPHA_FOR_Y,
    288       MAX_ALPHA_FOR_Y,
    289       FULL_STEP_FOR_Y,
    290       MIN_DUAL_INFEAS_ALPHA_FOR_Y,
    291       SAFE_MIN_DUAL_INFEAS_ALPHA_FOR_Y
    292     };
    293     /** Flag indicating whether the dual step size is to be used for
    294      *  the equality constraint multipliers. If 0, the primal step
    295      *  size is used, if 1 the dual step size, and if 2, the minimum
    296      *  of both. */
    297     AlphaForYEnum alpha_for_y_;
    298 
    299     /** Flag indicating whether magic steps should be used. */
    300     bool magic_steps_;
    301206    /** enumeration for the corrector type */
    302207    enum CorrectorTypeEnum {
     
    307212    /** Type of corrector steps that should be tried. */
    308213    CorrectorTypeEnum corrector_type_;
    309     /** Flag indicating whether the line search should always accept
    310      *  the full (fraction-to-the-boundary) step. */
    311     bool accept_every_trial_step_;
    312214    /** parameter in heurstic that determines whether corrector step
    313215    should be tried. */
     
    319221     *  the monotone mu mode. */
    320222    bool skip_corr_in_monotone_mode_;
    321     /** Indicates whether problem can be expected to be infeasible.
    322      *  This will trigger requesting a tighter reduction in
    323      *  infeasibility the first time the restoration phase is
    324      *  called. */
    325     bool expect_infeasible_problem_;
    326     /** Tolerance on constraint violation for
    327      *  expect_infeasible_problem heuristic.  If the constraint
    328      *  violation becomes that than this value, the heuristic is
    329      *  disabled for the rest of the optimization run. */
    330     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_;
    335 
    336     /** Tolerance for detecting tiny steps. */
    337     Number tiny_step_tol_;
    338 
    339     /** Number of watch dog trial steps. */
    340     Index watchdog_trial_iter_max_;
    341     /** Number of shortened iterations that trigger the watchdog. */
    342     Index watchdog_shortened_iter_trigger_;
    343 
    344     /** Indicates whether the algorithm should start directly with the
    345      *  restoratin phase */
    346     bool start_with_resto_;
    347223    //@}
    348224
     
    358234     *  respect to which progress is to be made */
    359235    Number reference_gradBarrTDelta_;
    360     /** Flag indicating if the watchdog is active */
    361     bool in_watchdog_;
    362     /** Counter for shortened iterations. */
    363     Index watchdog_shortened_iter_;
    364     /** Counter for watch dog iterations */
    365     Index watchdog_trial_iter_;
    366     /** Step size for Armijo test in watch dog */
    367     Number watchdog_alpha_primal_test_;
    368236    /** Constraint violation at reference point */
    369237    Number watchdog_theta_;
     
    372240    /** Barrier gradient transpose search direction at reference point */
    373241    Number watchdog_gradBarrTDelta_;
    374     /** Watchdog reference iterate */
    375     SmartPtr<const IteratesVector> watchdog_iterate_;
    376     /** Watchdog search direction at reference point */
    377     SmartPtr<const IteratesVector> watchdog_delta_;
    378     //@}
    379 
    380     /** @name Storage for last iterate that satisfies the acceptable
    381      *  level of optimality error. */
    382     //@{
    383     SmartPtr<const IteratesVector> acceptable_iterate_;
    384242    //@}
    385243
     
    387245    Filter filter_;
    388246
    389     /** Flag indicating whether the line search is to be performed
    390      * robust (usually this is true, unless SetRigorousLineSearch is
    391      * called with false).
    392      */
    393     bool rigorous_;
    394 
    395     /** Flag indicating whether no acceptable trial point was found
    396      *  during last line search. */
    397     bool skipped_line_search_;
    398 
    399     /** Flag indicating whether we are currently in the "soft"
    400      *  restoration phase mode, in which steps are accepted if they
    401      *  reduce the optimality error (see
    402      *  soft_resto_pderror_reduction_factor) */
    403     bool in_soft_resto_phase_;
    404 
    405     /** Counter for the number of successive iterations in which the
    406      *  full step was not accepted. */
    407     Index count_successive_shortened_steps_;
    408 
    409     /** Flag indicating if a tiny step was detected in previous
    410      *  iteration */
    411     bool tiny_step_last_iteration_;
    412 
    413247    /** @name Strategy objective that are used */
    414248    //@{
    415     SmartPtr<RestorationPhase> resto_phase_;
    416249    SmartPtr<PDSystemSolver> pd_solver_;
    417     SmartPtr<ConvergenceCheck> conv_check_;
    418250    //@}
    419251  };
Note: See TracChangeset for help on using the changeset viewer.