source: branches/dev/Algorithm/IpBacktrackingLineSearch.hpp @ 542

Last change on this file since 542 was 542, checked in by andreasw, 14 years ago
  • cleaned up line search to allow for alternative globalization scheme
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.5 KB
Line 
1// Copyright (C) 2004,2005 International Business Machines and others.
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// $Id: IpBacktrackingLineSearch.hpp 542 2005-10-13 22:43:08Z andreasw $
6//
7// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
8//           Andreas Waechter                 IBM    2005-10-13
9//               derived file from IpFilterLineSearch.hpp
10
11#ifndef __IPBACKTRACKINGLINESEARCH_HPP__
12#define __IPBACKTRACKINGLINESEARCH_HPP__
13
14#include "IpLineSearch.hpp"
15#include "IpBacktrackingLSAcceptor.hpp"
16#include "IpRestoPhase.hpp"
17#include "IpConvCheck.hpp"
18
19namespace Ipopt
20{
21
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).
35   */
36  class BacktrackingLineSearch : public LineSearch
37  {
38  public:
39    /**@name Constructors/Destructors */
40    //@{
41    /** Constructor.  The acceptor implements the acceptance test for
42     *  the line search. The PDSystemSolver object only needs to be
43     *  provided (i.e. not NULL) if second order correction is to be
44     *  used.  The ConvergenceCheck object is used to determine
45     *  whether the current iterate is acceptable (for example, the
46     *  restoration phase is not started if the acceptability level
47     *  has been reached).  If conv_check is NULL, we assume that the
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                          );
54
55    /** Default destructor */
56    virtual ~BacktrackingLineSearch();
57    //@}
58
59    /** InitializeImpl - overloaded from AlgorithmStrategyObject */
60    virtual bool InitializeImpl(const OptionsList& options,
61                                const std::string& prefix);
62
63    /** Perform the line search.  It is assumed that the search
64     *  direction is computed in the data object.
65     */
66    virtual void FindAcceptableTrialPoint();
67
68    /** Reset the line search.
69     *  This function should be called if all previous information
70     *  should be discarded when the line search is performed the
71     *  next time.  For example, this method should be called if
72     *  the barrier parameter is changed.
73     */
74    virtual void Reset();
75
76    /** Set flag indicating whether a very rigorous line search should
77     *  be performed.  If this flag is set to true, the line search
78     *  algorithm might decide to abort the line search and not to
79     *  accept a new iterate.  If the line search decided not to
80     *  accept a new iterate, the return value of
81     *  CheckSkippedLineSearch() is true at the next call.  For
82     *  example, in the non-monotone barrier parameter update
83     *  procedure, the filter algorithm should not switch to the
84     *  restoration phase in the free mode; instead, the algorithm
85     *  should swtich to the fixed mode.
86     */
87    virtual void SetRigorousLineSearch(bool rigorous)
88    {
89      rigorous_ = rigorous;
90    }
91
92    /** Check if the line search procedure didn't accept a new iterate
93     *  during the last call of FindAcceptableTrialPoint().
94     * 
95     */
96    virtual bool CheckSkippedLineSearch()
97    {
98      return skipped_line_search_;
99    }
100
101    /** Methods for OptionsList */
102    //@{
103    static void RegisterOptions(SmartPtr<RegisteredOptions> roptions);
104    //@}
105
106  private:
107    /**@name Default Compiler Generated Methods
108     * (Hidden to avoid implicit creation/calling).
109     * These methods are not implemented and
110     * we do not want the compiler to implement
111     * them for us, so we declare them private
112     * and do not define them. This ensures that
113     * they will not be implicitly created/called. */
114    //@{
115    /** Copy Constructor */
116    BacktrackingLineSearch(const BacktrackingLineSearch&);
117
118    /** Overloaded Equals Operator */
119    void operator=(const BacktrackingLineSearch&);
120    //@}
121
122    /** Method performing the backtracking line search.  The return
123     *  value indicates if the step acceptance criteria are met.  If
124     *  the watchdog is active, only one trial step is performed (and
125     *  the trial values are set accordingly). */
126    bool DoBacktrackingLineSearch(bool skip_first_trial_point,
127                                  Number& alpha_primal,
128                                  bool& corr_taken,
129                                  bool& soc_taken,
130                                  Index& n_steps,
131                                  bool& evaluation_error,
132                                  SmartPtr<IteratesVector>& actual_delta);
133
134    /** Method for starting the watch dog.  Set all appropriate fields
135     *  accordingly */
136    void StartWatchDog();
137
138    /** Method for stopping the watch dog.  Set all appropriate fields
139     *  accordingly. */
140    void StopWatchDog(SmartPtr<IteratesVector>& actual_delta);
141
142    /** Method for checking if current trial point is acceptable.
143     *  It is assumed that the delta information in ip_data is the
144     *  search direction used in criteria.  The primal trial point has
145     *  to be set before the call.
146     */
147    bool CheckAcceptabilityOfTrialPoint(Number alpha_primal);
148
149    /** Check comparison "lhs <= rhs", using machine precision based on BasVal */
150    //ToDo This should probably not be a static member function if we want to
151    //     allow for different relaxation parameters values
152    static bool Compare_le(Number lhs, Number rhs, Number BasVal);
153
154    /** Method for setting the dual variables in the trial fields in
155     *  IpData, given the search direction.  The step size for the
156     *  bound multipliers is alpha_dual (the fraction-to-the-boundary
157     *  step size), and the step size for the equality constraint
158     *  multipliers depends on the choice of alpha_for_y. */
159    void PerformDualStep(Number alpha_primal,
160                         Number alpha_dual,
161                         SmartPtr<IteratesVector>& delta);
162
163    /** Try a step for the soft restoration phase and check if it is
164     *  acceptable.  The step size is identical for all variables.  A
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. */
172    bool TrySoftRestoStep(SmartPtr<IteratesVector>& actual_delta,
173                          bool &satisfies_original_criterion);
174
175    /** Try a second order correction for the constraints.  If the
176     *  first trial step (with incoming alpha_primal) has been reject,
177     *  this tries up to max_soc_ second order corrections for the
178     *  constraints.  Here, alpha_primal_test is the step size that
179     *  has to be used in the filter acceptance tests.  On output
180     *  actual_delta_... has been set to the steps including the
181     *  second order correction if it has been accepted, otherwise it
182     *  is unchanged.  If the SOC step has been accepted, alpha_primal
183     *  has the fraction-to-the-boundary value for the SOC step on output.
184     *  The return value is true, if an SOC step has been accepted.
185     */
186    bool TrySecondOrderCorrection(Number alpha_primal_test,
187                                  Number& alpha_primal,
188                                  SmartPtr<IteratesVector>& actual_delta);
189
190    /** Try higher order corrector (for fast local convergence).  In
191     *  contrast to a second order correction step, which tries to
192     *  make an unacceptable point acceptable by improving constraint
193     *  violation, this corrector step is tried even if the regular
194     *  primal-dual step is acceptable.
195     */
196    bool TryCorrector(Number alpha_primal_test,
197                      Number& alpha_primal,
198                      SmartPtr<IteratesVector>& actual_delta);
199
200    /** Perform magic steps.  Take the current values of the slacks in
201     *  trial and replace them by better ones that lead to smaller
202     *  values of the barrier function and less constraint
203     *  violation. */
204    void PerformMagicStep();
205
206    /** Detect if the search direction is too small.  This should be
207     *  true if the search direction is so small that if makes
208     *  numerically no difference. */
209    bool DetectTinyStep();
210
211    /** Store current iterate as acceptable point */
212    void StoreAcceptablePoint();
213
214    /** Restore acceptable point into the current fields of IpData if
215     *  found. Returns true if such as point is available. */
216    bool RestoreAcceptablePoint();
217
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. */
222    bool CurrentIsAcceptable();
223
224    /** @name Parameters for the filter algorithm.  Names as in the paper */
225    //@{
226    /** factor by which search direction is to be shortened if trial
227     *  point is rejected. */
228    Number alpha_red_factor_;
229
230    /** enumeration for the different alpha_for_y_ settings */
231    enum AlphaForYEnum {
232      PRIMAL_ALPHA_FOR_Y=0,
233      DUAL_ALPHA_FOR_Y,
234      MIN_ALPHA_FOR_Y,
235      MAX_ALPHA_FOR_Y,
236      FULL_STEP_FOR_Y,
237      MIN_DUAL_INFEAS_ALPHA_FOR_Y,
238      SAFE_MIN_DUAL_INFEAS_ALPHA_FOR_Y
239    };
240    /** Flag indicating whether the dual step size is to be used for
241     *  the equality constraint multipliers. If 0, the primal step
242     *  size is used, if 1 the dual step size, and if 2, the minimum
243     *  of both. */
244    AlphaForYEnum alpha_for_y_;
245
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
251    /** Flag indicating whether magic steps should be used. */
252    bool magic_steps_;
253    /** Flag indicating whether the line search should always accept
254     *  the full (fraction-to-the-boundary) step. */
255    bool accept_every_trial_step_;
256    /** Indicates whether problem can be expected to be infeasible.
257     *  This will trigger requesting a tighter reduction in
258     *  infeasibility the first time the restoration phase is
259     *  called. */
260    bool expect_infeasible_problem_;
261    /** Tolerance on constraint violation for
262     *  expect_infeasible_problem heuristic.  If the constraint
263     *  violation becomes that than this value, the heuristic is
264     *  disabled for the rest of the optimization run. */
265    Number expect_infeasible_problem_ctol_;
266
267    /** Tolerance for detecting tiny steps. */
268    Number tiny_step_tol_;
269
270    /** Number of watch dog trial steps. */
271    Index watchdog_trial_iter_max_;
272    /** Number of shortened iterations that trigger the watchdog. */
273    Index watchdog_shortened_iter_trigger_;
274
275    /** Indicates whether the algorithm should start directly with the
276     *  restoratin phase */
277    bool start_with_resto_;
278    //@}
279
280    /** @name Information related to watchdog procedure */
281    //@{
282    /** Flag indicating if the watchdog is active */
283    bool in_watchdog_;
284    /** Counter for shortened iterations. */
285    Index watchdog_shortened_iter_;
286    /** Counter for watch dog iterations */
287    Index watchdog_trial_iter_;
288    /** Step size for Armijo test in watch dog */
289    Number watchdog_alpha_primal_test_;
290    /** Watchdog reference iterate */
291    SmartPtr<const IteratesVector> watchdog_iterate_;
292    /** Watchdog search direction at reference point */
293    SmartPtr<const IteratesVector> watchdog_delta_;
294    //@}
295
296    /** @name Storage for last iterate that satisfies the acceptable
297     *  level of optimality error. */
298    //@{
299    SmartPtr<const IteratesVector> acceptable_iterate_;
300    //@}
301
302    /** Flag indicating whether the line search is to be performed
303     * robust (usually this is true, unless SetRigorousLineSearch is
304     * called with false).
305     */
306    bool rigorous_;
307
308    /** Flag indicating whether no acceptable trial point was found
309     *  during last line search. */
310    bool skipped_line_search_;
311
312    /** Flag indicating whether we are currently in the "soft"
313     *  restoration phase mode, in which steps are accepted if they
314     *  reduce the optimality error (see
315     *  soft_resto_pderror_reduction_factor) */
316    bool in_soft_resto_phase_;
317
318    /** Counter for the number of successive iterations in which the
319     *  full step was not accepted. */
320    Index count_successive_shortened_steps_;
321
322    /** Flag indicating if a tiny step was detected in previous
323     *  iteration */
324    bool tiny_step_last_iteration_;
325
326    /** @name Strategy objective that are used */
327    //@{
328    SmartPtr<BacktrackingLSAcceptor> acceptor_;
329    SmartPtr<RestorationPhase> resto_phase_;
330    SmartPtr<ConvergenceCheck> conv_check_;
331    //@}
332  };
333
334} // namespace Ipopt
335
336#endif
Note: See TracBrowser for help on using the repository browser.