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

Last change on this file since 485 was 485, checked in by andreasw, 14 years ago
  • added option print_info_string, and fit regular output into 80 columns
  • ran astyle
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.2 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 485 2005-08-24 15:20:56Z andreasw $
6//
7// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
8
9#ifndef __IPFILTERLINESEARCH_HPP__
10#define __IPFILTERLINESEARCH_HPP__
11
12#include "IpFilter.hpp"
13#include "IpLineSearch.hpp"
14#include "IpRestoPhase.hpp"
15#include "IpPDSystemSolver.hpp"
16#include "IpConvCheck.hpp"
17
18namespace Ipopt
19{
20
21  /** Filter line search.  This class implements the filter line
22   *  search procedure.
23   */
24  class FilterLineSearch : public LineSearch
25  {
26  public:
27    /**@name Constructors/Destructors */
28    //@{
29    /** 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                    );
40
41    /** Default destructor */
42    virtual ~FilterLineSearch();
43    //@}
44
45    /** InitializeImpl - overloaded from AlgorithmStrategyObject */
46    virtual bool InitializeImpl(const OptionsList& options,
47                                const std::string& prefix);
48
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.
55     *  This function should be called if all previous information
56     *  should be discarded when the line search is performed the
57     *  next time.  For example, this method should be called if
58     *  the barrier parameter is changed.
59     */
60    virtual void Reset();
61
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    }
86
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
100    /** Methods for OptionsList */
101    //@{
102    static void RegisterOptions(SmartPtr<RegisteredOptions> roptions);
103    //@}
104
105  private:
106    /**@name Default Compiler Generated Methods
107     * (Hidden to avoid implicit creation/calling).
108     * These methods are not implemented and
109     * we do not want the compiler to implement
110     * them for us, so we declare them private
111     * and do not define them. This ensures that
112     * they will not be implicitly created/called. */
113    //@{
114    /** Copy Constructor */
115    FilterLineSearch(const FilterLineSearch&);
116
117    /** 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();
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);
179
180    /** Check comparison "lhs <= rhs", using machine precision based on BasVal */
181    //ToDo This should probably not be a static member function if we want to
182    //     allow for different relaxation parameters values
183    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();
251
252    /** @name Parameters for the filter algorithm.  Names as in the paper */
253    //@{
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_;
268    /** factor by which search direction is to be shortened if trial
269     *  point is rejected. */
270    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_;
282
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_;
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_;
309    /** Flag indicating whether the line search should always accept
310     *  the full (fraction-to-the-boundary) step. */
311    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_;
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_;
347    //@}
348
349    /** @name Information related to watchdog procedure */
350    //@{
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_;
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_;
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_;
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_;
384    //@}
385
386    /** Filter with entries */
387    Filter filter_;
388
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
413    /** @name Strategy objective that are used */
414    //@{
415    SmartPtr<RestorationPhase> resto_phase_;
416    SmartPtr<PDSystemSolver> pd_solver_;
417    SmartPtr<ConvergenceCheck> conv_check_;
418    //@}
419  };
420
421} // namespace Ipopt
422
423#endif
Note: See TracBrowser for help on using the repository browser.