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

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