source: branches/dev/Algorithm/IpFilterLineSearch.hpp @ 395

Last change on this file since 395 was 395, checked in by andreasw, 14 years ago

fixed bug in alpha_for_y option

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.1 KB
Line 
1// Copyright (C) 2004, International Business Machines and others.
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// $Id: IpFilterLineSearch.hpp 395 2005-07-21 15:31:04Z andreasw $
6//
7// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
8
9#ifndef __IPFILTERLINESEARCH_HPP__
10#define __IPFILTERLINESEARCH_HPP__
11
12#include "IpUtils.hpp"
13#include "IpFilter.hpp"
14#include "IpLineSearch.hpp"
15#include "IpRestoPhase.hpp"
16#include "IpPDSystemSolver.hpp"
17#include "IpIpoptType.hpp"
18
19namespace Ipopt
20{
21
22  DeclareIpoptType(FilterLineSearch);
23
24  /** Filter line search.  This class implements the filter line
25   *  search procedure.
26   */
27  class FilterLineSearch : public LineSearch
28  {
29  public:
30    /**@name Constructors/Destructors */
31    //@{
32    /** Constructor.  The PDSystemSolver object only needs to be
33     *  provided (i.e. not NULL) if second order correction is to be
34     *  used. */
35    FilterLineSearch(const SmartPtr<RestorationPhase>& resto_phase,
36                     const SmartPtr<PDSystemSolver>& pd_solver
37                    );
38
39    /** Default destructor */
40    virtual ~FilterLineSearch();
41    //@}
42
43    /** InitializeImpl - overloaded from AlgorithmStrategyObject */
44    virtual bool InitializeImpl(const OptionsList& options,
45                                const std::string& prefix);
46
47    /** Perform the line search.  It is assumed that the search
48     *  direction is computed in the data object.
49     */
50    virtual void FindAcceptableTrialPoint();
51
52    /** Reset the line search.
53     *  This function should be called if all previous information
54     *  should be discarded when the line search is performed the
55     *  next time.  For example, this method should be called if
56     *  the barrier parameter is changed.
57     */
58    virtual void Reset();
59
60    /** Set flag indicating whether a very rigorous line search should
61     *  be performed.  If this flag is set to true, the line search
62     *  algorithm might decide to abort the line search and not to
63     *  accept a new iterate.  If the line search decided not to
64     *  accept a new iterate, the return value of
65     *  CheckSkippedLineSearch() is true at the next call.  For
66     *  example, in the non-monotone barrier parameter update
67     *  procedure, the filter algorithm should not switch to the
68     *  restoration phase in the free mode; instead, the algorithm
69     *  should swtich to the fixed mode.
70     */
71    virtual void SetRigorousLineSearch(bool rigorous)
72    {
73      rigorous_ = rigorous;
74    }
75
76    /** Check if the line search procedure didn't accept a new iterate
77     *  during the last call of FindAcceptableTrialPoint().
78     * 
79     */
80    virtual bool CheckSkippedLineSearch()
81    {
82      return skipped_line_search_;
83    }
84
85    /**@name Trial Point Accepting Methods. Used internally to check certain
86     * acceptability criteria and used externally (by the restoration phase
87     * convergence check object, for instance)
88     */
89    //@{
90    /** Checks if a trial point is acceptable to the current iterate */
91    bool IsAcceptableToCurrentIterate(Number trial_barr, Number trial_theta,
92                                      bool called_from_restoration=false) const;
93
94    /** Checks if a trial point is acceptable to the current filter */
95    bool IsAcceptableToCurrentFilter(Number trial_barr, Number trial_theta) const;
96    //@}
97
98    /** Methods for IpoptType */
99    //@{
100    static void RegisterOptions(SmartPtr<RegisteredOptions> roptions);
101    //@}
102
103  private:
104    /**@name Default Compiler Generated Methods
105     * (Hidden to avoid implicit creation/calling).
106     * These methods are not implemented and
107     * we do not want the compiler to implement
108     * them for us, so we declare them private
109     * and do not define them. This ensures that
110     * they will not be implicitly created/called. */
111    //@{
112    /** Copy Constructor */
113    FilterLineSearch(const FilterLineSearch&);
114
115    /** Overloaded Equals Operator */
116    void operator=(const FilterLineSearch&);
117    //@}
118
119    /** @name Filter information */
120    //@{
121    /** Upper bound on infeasibility */
122    Number theta_max_;
123    Number theta_max_fact_;
124
125    /** Infeasibility switching bound */
126    Number theta_min_;
127    Number theta_min_fact_;
128    //@}
129
130    /** Method for checking if the current step size satisfies the
131     *  f-type switching condition.  Here, we use the search direction
132     *  stored in ip_data
133     */
134    bool IsFtype(Number alpha_primal_test);
135
136    /** Method for checking the Armijo condition, given a trial step
137     *  size.  The test uses the search direction stored in ip_data,
138     *  and the values of the functions at the trial point in ip_data.
139     */
140    bool ArmijoHolds(Number alpha_primal_test);
141
142    /** Method to calculate alpha_min (minimum alpha before going to
143     *  restoration
144     */
145    Number CalculateAlphaMin();
146
147    /** Augment the filter used on the current values of the barrier
148     *  objective function and the contraint violation */
149    void AugmentFilter();
150
151    /** Method performing the backtracking line search.  The return
152     *  value indicates if the step acceptance criteria are met.  If
153     *  the watchdog is active, only one trial step is performed (and
154     *  the trial values are set accordingly). */
155    bool DoBacktrackingLineSearch(bool skip_first_trial_point,
156                                  Number& alpha_primal,
157                                  bool& corr_taken,
158                                  bool& soc_taken,
159                                  Index& n_steps,
160                                  bool& evaluation_error,
161                                  SmartPtr<IteratesVector>& actual_delta);
162
163    /** Method for starting the watch dog.  Set all appropriate fields
164     *  accordingly */
165    void StartWatchDog();
166
167    /** Method for stopping the watch dog.  Set all appropriate fields
168     *  accordingly. */
169    void StopWatchDog(SmartPtr<IteratesVector>& actual_delta);
170
171    /** Method for checking if current trial point is acceptable.
172     *  It is assumed that the delta information in ip_data is the
173     *  search direction used in criteria.  The primal trial point has
174     *  to be set before the call.
175     */
176    bool CheckAcceptabilityOfTrialPoint(Number alpha_primal);
177
178    /** Check comparison "lhs <= rhs", using machine precision based on BasVal */
179    //ToDo This should probably not be a static member function if we want to
180    //     allow for different relaxation parameters values
181    static bool Compare_le(Number lhs, Number rhs, Number BasVal);
182
183    /** Method for setting the dual variables in the trial fields in
184     *  IpData, given the search direction.  The step size for the
185     *  bound multipliers is alpha_dual (the fraction-to-the-boundary
186     *  step size), and the step size for the equality constraint
187     *  multipliers depends on the choice of alpha_for_y. */
188    void PerformDualStep(Number alpha_primal,
189                         Number alpha_dual,
190                         SmartPtr<IteratesVector>& delta);
191
192    /** Try a step for the soft restoration phase and check if it is
193     *  acceptable.  The step size is identical for all variables.  A
194     *  point is accepted if it is acceptable for the original filter
195     *  (in which case satisfies_original_filter = true on return), or
196     *  if the primal-dual system error was decrease by at least the
197     *  factor soft_resto_pderror_reduction_factor_.  The return value is
198     *  true, if the trial point was acceptable. */
199    bool TrySoftRestoStep(SmartPtr<IteratesVector>& actual_delta,
200                          bool &satisfies_original_filter);
201
202    /** Try a second order correction for the constraints.  If the
203     *  first trial step (with incoming alpha_primal) has been reject,
204     *  this tries up to max_soc_ second order corrections for the
205     *  constraints.  Here, alpha_primal_test is the step size that
206     *  has to be used in the filter acceptance tests.  On output
207     *  actual_delta_... has been set to the steps including the
208     *  second order correction if it has been accepted, otherwise it
209     *  is unchanged.  If the SOC step has been accepted, alpha_primal
210     *  has the fraction-to-the-boundary value for the SOC step on output.
211     *  The return value is true, if an SOC step has been accepted.
212     */
213    bool TrySecondOrderCorrection(Number alpha_primal_test,
214                                  Number& alpha_primal,
215                                  SmartPtr<IteratesVector>& actual_delta);
216
217    /** Try higher order corrector (for fast local convergence).  In
218     *  contrast to a second order correction step, which tries to
219     *  make an unacceptable point acceptable by improving constraint
220     *  violation, this corrector step is tried even if the regular
221     *  primal-dual step is acceptable.
222     */
223    bool TryCorrector(Number alpha_primal_test,
224                      Number& alpha_primal,
225                      SmartPtr<IteratesVector>& actual_delta);
226
227    /** Perform magic steps.  Take the current values of the slacks in
228     *  trial and replace them by better ones that lead to smaller
229     *  values of the barrier function and less constraint
230     *  violation. */
231    void PerformMagicStep();
232
233    /** Detect if the search direction is too small.  This should be
234     *  true if the search direction is so small that if makes
235     *  numerically no difference. */
236    bool DetectTinyStep();
237
238    /** Store current iterate as acceptable point */
239    void StoreAcceptablePoint();
240
241    /** Restore acceptable point into the current fields of IpData if
242     *  found. Returns true if such as point is available. */
243    bool RestoreAcceptablePoint();
244
245    /** @name Parameters for the filter algorithm.  Names as in the paper */
246    //@{
247    /** \f$ \eta_{\varphi} \f$ */
248    Number eta_phi_;
249    /** \f$ \delta \f$ */
250    Number delta_;
251    /** \f$ s_{\varphi} \f$ */
252    Number s_phi_;
253    /** \f$ s_{\Theta} \f$ */
254    Number s_theta_;
255    /** \f$ \gamma_{\varphi} \f$ */
256    Number gamma_phi_;
257    /** \f$ \gamma_{\Theta} \f$ */
258    Number gamma_theta_;
259    /** \f$ \gamma_{\alpha} \f$ */
260    Number alpha_min_frac_;
261    /** factor by which search direction is to be shortened if trial
262     *  point is rejected. */
263    Number alpha_red_factor_;
264    /** Maximal number of second order correction steps */
265    Index max_soc_;
266    /** Required reduction in constraint violation before trying
267     *  multiple second order correction steps \f$ \kappa_{soc}\f$.
268     */
269    Number kappa_soc_;
270    /** Maximal increase in objective function in orders of magnitute
271     *  (log10).  If the log10(barrier objective function) is
272     *  increased more than this compared to the current point, the
273     *  trial point is rejected. */
274    Number obj_max_inc_;
275
276    /** enumeration for the different alpha_for_y_ settings */
277    enum AlphaForYEnum {
278      PRIMAL_ALPHA_FOR_Y=0,
279      DUAL_ALPHA_FOR_Y,
280      MIN_ALPHA_FOR_Y,
281      MAX_ALPHA_FOR_Y,
282      FULL_STEP_FOR_Y,
283      MIN_DUAL_INFEAS_ALPHA_FOR_Y,
284      SAFE_MIN_DUAL_INFEAS_ALPHA_FOR_Y
285    };
286    /** Flag indicating whether the dual step size is to be used for
287     *  the equality constraint multipliers. If 0, the primal step
288     *  size is used, if 1 the dual step size, and if 2, the minimum
289     *  of both. */
290    AlphaForYEnum alpha_for_y_;
291
292    /** Flag indicating whether magic steps should be used. */
293    bool magic_steps_;
294    /** enumeration for the corrector type */
295    enum CorrectorTypeEnum {
296      NO_CORRECTOR=0,
297      AFFINE_CORRECTOR,
298      PRIMAL_DUAL_CORRECTOR
299    };
300    /** Type of corrector steps that should be tried. */
301    CorrectorTypeEnum corrector_type_;
302    /** Flag indicating whether the line search should always accept
303     *  the full (fraction-to-the-boundary) step. */
304    bool accept_every_trial_step_;
305    /** parameter in heurstic that determines whether corrector step
306    should be tried. */
307    Number corrector_compl_avrg_red_fact_;
308    /** Flag indicating whether the corrector should be skipped in an
309     *  iteration in which negative curvature is detected */
310    bool skip_corr_if_neg_curv_;
311    /** Flag indicating whether the corrector should be skipped during
312     *  the monotone mu mode. */
313    bool skip_corr_in_monotone_mode_;
314    /** Indicates whether problem can be expected to be infeasible.
315     *  This will trigger requesting a tighter reduction in
316     *  infeasibility the first time the restoration phase is
317     *  called. */
318    bool expect_infeasible_problem_;
319    /** Tolerance on constraint violation for
320     *  expect_infeasible_problem heuristic.  If the constraint
321     *  violation becomes that than this value, the heuristic is
322     *  disabled for the rest of the optimization run. */
323    Number expect_infeasible_problem_ctol_;
324    /** Reduction factor for the restoration phase that accepts steps
325     *  reducing the optimality error ("soft restoration phase"). If
326     *  0., then this restoration phase is not enabled. */
327    Number soft_resto_pderror_reduction_factor_;
328
329    /** Tolerance for detecting tiny steps. */
330    Number tiny_step_tol_;
331
332    /** Number of watch dog trial steps. */
333    Index watchdog_trial_iter_max_;
334    /** Number of shortened iterations that trigger the watchdog. */
335    Index watchdog_shortened_iter_trigger_;
336
337    /** Acceptable tolerance for the problem to terminate earlier if
338     *  algorithm seems stuck or cycling */
339    Number acceptable_tol_;
340    /** Maximum number of iterations with acceptable level of accuracy
341     *  and full steps, after which the algorithm terminates.  If 0,
342     *  this heuristic is disabled. */
343    Index acceptable_iter_max_;
344
345    /** Indicates whether the algorithm should start directly with the
346     *  restoratin phase */
347    bool start_with_resto_;
348    //@}
349
350    /** @name Information related to watchdog procedure */
351    //@{
352    /** Constraint violation at the point with respect to which
353     *  progress is to be made */
354    Number reference_theta_;
355    /** Barrier objective function at the point with respect to which
356     *  progress is to be made */
357    Number reference_barr_;
358    /** Barrier gradient transpose search direction at the point with
359     *  respect to which progress is to be made */
360    Number reference_gradBarrTDelta_;
361    /** Flag indicating if the watchdog is active */
362    bool in_watchdog_;
363    /** Counter for shortened iterations. */
364    Index watchdog_shortened_iter_;
365    /** Counter for watch dog iterations */
366    Index watchdog_trial_iter_;
367    /** Step size for Armijo test in watch dog */
368    Number watchdog_alpha_primal_test_;
369    /** Constraint violation at reference point */
370    Number watchdog_theta_;
371    /** Barrier objective function at reference point */
372    Number watchdog_barr_;
373    /** Barrier gradient transpose search direction at reference point */
374    Number watchdog_gradBarrTDelta_;
375    /** Watchdog reference iterate */
376    SmartPtr<const IteratesVector> watchdog_iterate_;
377    /** Watchdog search direction at reference point */
378    SmartPtr<const IteratesVector> watchdog_delta_;
379    //@}
380
381    /** @name Storage for last iterate that satisfies the acceptable
382     *  level of optimality error. */
383    //@{
384    SmartPtr<const IteratesVector> acceptable_iterate_;
385    //@}
386
387    /** Filter with entries */
388    Filter filter_;
389
390    /** Flag indicating whether the line search is to be performed
391     * robust (usually this is true, unless SetRigorousLineSearch is
392     * called with false).
393     */
394    bool rigorous_;
395
396    /** Flag indicating whether no acceptable trial point was found
397     *  during last line search. */
398    bool skipped_line_search_;
399
400    /** Flag indicating whether we are currently in the "soft"
401     *  restoration phase mode, in which steps are accepted if they
402     *  reduce the optimality error (see
403     *  soft_resto_pderror_reduction_factor) */
404    bool in_soft_resto_phase_;
405
406    /** Counter for the number of successive iterations in which the
407     *  full step was not accepted. */
408    Index count_successive_shortened_steps_;
409
410    /** Counter for the number of successive iterations in which the
411     *  nlp error was below the acceptable tolerance and a full step
412     *  was accepted. */
413    Index count_acceptable_iter_;
414
415    /** Flag indicating if a tiny step was detected in previous
416     *  iteration */
417    bool tiny_step_last_iteration_;
418
419    SmartPtr<RestorationPhase> resto_phase_;
420    SmartPtr<PDSystemSolver> pd_solver_;
421  };
422
423} // namespace Ipopt
424
425#endif
Note: See TracBrowser for help on using the repository browser.