- Main Page
- Namespaces
- Classes
- Files

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# Ipopt::BacktrackingLineSearch Class Reference

General implementation of a backtracking line search. More...

`#include <IpBacktrackingLineSearch.hpp>`

Inheritance diagram for Ipopt::BacktrackingLineSearch:

[legend]
Collaboration diagram for Ipopt::BacktrackingLineSearch:

[legend]
List of all members.

## Parameters for the filter algorithm. Names as in the paper
enum | AlphaForYEnum { PRIMAL_ALPHA_FOR_Y = 0, DUAL_ALPHA_FOR_Y, MIN_ALPHA_FOR_Y, MAX_ALPHA_FOR_Y, FULL_STEP_FOR_Y, MIN_DUAL_INFEAS_ALPHA_FOR_Y, SAFE_MIN_DUAL_INFEAS_ALPHA_FOR_Y }
| enumeration for the different alpha_for_y_ settings More...
Number | alpha_red_factor_
| factor by which search direction is to be shortened if trial point is rejected.
AlphaForYEnum | alpha_for_y_
| Flag indicating whether the dual step size is to be used for the equality constraint multipliers.
Number | soft_resto_pderror_reduction_factor_
| Reduction factor for the restoration phase that accepts steps reducing the optimality error ("soft restoration phase").
Index | max_soft_resto_iters_
| Maximal number of iterations that can be done in the soft iteration phase before the algorithm reverts to the regular restoration phase.
bool | magic_steps_
| Flag indicating whether magic steps should be used.
bool | accept_every_trial_step_
| Flag indicating whether the line search should always accept the full (fraction-to-the-boundary) step.
bool | expect_infeasible_problem_
| Indicates whether problem can be expected to be infeasible.
Number | expect_infeasible_problem_ctol_
| Tolerance on constraint violation for expect_infeasible_problem heuristic.
Number | tiny_step_tol_
| Tolerance for detecting tiny steps.
Number | tiny_step_y_tol_
| Tolerance for y variables for the tiny step stopping heuristic.
Index | watchdog_trial_iter_max_
| Number of watch dog trial steps.
Index | watchdog_shortened_iter_trigger_
| Number of shortened iterations that trigger the watchdog.
bool | start_with_resto_
| Indicates whether the algorithm should start directly with the restoratin phase.
## Public Member Functions
virtual bool | InitializeImpl (const OptionsList &options, const std::string &prefix)
| InitializeImpl - overloaded from AlgorithmStrategyObject.
virtual void | FindAcceptableTrialPoint ()
| Perform the line search.
virtual void | Reset ()
| Reset the line search.
virtual void | SetRigorousLineSearch (bool rigorous)
| Set flag indicating whether a very rigorous line search should be performed.
virtual bool | CheckSkippedLineSearch ()
| Check if the line search procedure didn't accept a new iterate during the last call of FindAcceptableTrialPoint().
virtual bool | ActivateFallbackMechanism ()
| Activate fallback mechanism.
Constructors/Destructors
| BacktrackingLineSearch (const SmartPtr< BacktrackingLSAcceptor > &acceptor, const SmartPtr< RestorationPhase > &resto_phase, const SmartPtr< ConvergenceCheck > &conv_check)
| Constructor.
virtual | ~BacktrackingLineSearch ()
| Default destructor.
## Static Public Member Functions
static void | RegisterOptions (SmartPtr< RegisteredOptions > roptions)
| Methods for OptionsList.
## Private Member Functions
bool | DoBacktrackingLineSearch (bool skip_first_trial_point, Number &alpha_primal, bool &corr_taken, bool &soc_taken, Index &n_steps, bool &evaluation_error, SmartPtr< IteratesVector > &actual_delta)
| Method performing the backtracking line search.
void | StartWatchDog ()
| Method for starting the watch dog.
void | StopWatchDog (SmartPtr< IteratesVector > &actual_delta)
| Method for stopping the watch dog.
bool | CheckAcceptabilityOfTrialPoint (Number alpha_primal)
| Method for checking if current trial point is acceptable.
void | PerformDualStep (Number alpha_primal, Number alpha_dual, SmartPtr< IteratesVector > &delta)
| Method for setting the dual variables in the trial fields in IpData, given the search direction.
bool | TrySoftRestoStep (SmartPtr< IteratesVector > &actual_delta, bool &satisfies_original_criterion)
| Try a step for the soft restoration phase and check if it is acceptable.
bool | TrySecondOrderCorrection (Number alpha_primal_test, Number &alpha_primal, SmartPtr< IteratesVector > &actual_delta)
| Try a second order correction for the constraints.
bool | TryCorrector (Number alpha_primal_test, Number &alpha_primal, SmartPtr< IteratesVector > &actual_delta)
| Try higher order corrector (for fast local convergence).
void | PerformMagicStep ()
| Perform magic steps.
bool | DetectTinyStep ()
| Detect if the search direction is too small.
void | StoreAcceptablePoint ()
| Store current iterate as acceptable point.
bool | RestoreAcceptablePoint ()
| Restore acceptable point into the current fields of IpData if found.
bool | CurrentIsAcceptable ()
| Method for determining if the current iterate is acceptable (in the sense of the acceptable_tol options).
Default Compiler Generated Methods
(Hidden to avoid implicit creation/calling). These methods are not implemented and we do not want the compiler to implement them for us, so we declare them private and do not define them. This ensures that they will not be implicitly created/called.
| BacktrackingLineSearch (const BacktrackingLineSearch &)
| Copy Constructor.
void | operator= (const BacktrackingLineSearch &)
| Overloaded Equals Operator.
## Static Private Member Functions
static bool | Compare_le (Number lhs, Number rhs, Number BasVal)
| Check comparison "lhs <= rhs", using machine precision based on BasVal.
## Private Attributes
bool | fallback_activated_
| Flag indicating whether the algorithm has asked to immediately switch to the fallback mechanism (restoration phase).
bool | rigorous_
| Flag indicating whether the line search is to be performed robust (usually this is true, unless SetRigorousLineSearch is called with false).
bool | skipped_line_search_
| Flag indicating whether no acceptable trial point was found during last line search.
bool | in_soft_resto_phase_
| Flag indicating whether we are currently in the "soft" restoration phase mode, in which steps are accepted if they reduce the optimality error (see soft_resto_pderror_reduction_factor).
Index | soft_resto_counter_
| Counter for iteration performed in soft restoration phase in a row.
Index | count_successive_shortened_steps_
| Counter for the number of successive iterations in which the full step was not accepted.
bool | tiny_step_last_iteration_
| Flag indicating if a tiny step was detected in previous iteration.
Information related to watchdog procedure
bool | in_watchdog_
| Flag indicating if the watchdog is active.
Index | watchdog_shortened_iter_
| Counter for shortened iterations.
Index | watchdog_trial_iter_
| Counter for watch dog iterations.
Number | watchdog_alpha_primal_test_
| Step size for Armijo test in watch dog.
SmartPtr< const IteratesVector > | watchdog_iterate_
| Watchdog reference iterate.
SmartPtr< const IteratesVector > | watchdog_delta_
| Watchdog search direction at reference point.
Number | last_mu_
| Barrier parameter value during last line search.
Storage for last iterate that satisfies the acceptable
level of optimality error.
SmartPtr< const IteratesVector > | acceptable_iterate_
Index | acceptable_iteration_number_
Strategy objective that are used
SmartPtr< BacktrackingLSAcceptor > | acceptor_
SmartPtr< RestorationPhase > | resto_phase_
SmartPtr< ConvergenceCheck > | conv_check_

## Detailed Description

General implementation of a backtracking line search.

This class can be used to perform the filter line search procedure or other procedures. The BacktrackingLSAcceptor is used to determine whether trial points are acceptable (e.g., based on a filter or other methods).

This backtracking line search knows of a restoration phase (which is called when the trial step size becomes too small or no search direction could be computed). It also has the notion of a "soft restoration phase," which uses the regular steps but decides on the acceptability based on other measures than the regular ones (e.g., reduction of the PD error instead of acceptability to a filter mechanism).

Definition at line 36 of file IpBacktrackingLineSearch.hpp.

## Member Enumeration Documentation

enum Ipopt::BacktrackingLineSearch::AlphaForYEnum`[private]`

enumeration for the different alpha_for_y_ settings

Enumerator:

  PRIMAL_ALPHA_FOR_Y |
  DUAL_ALPHA_FOR_Y |
  MIN_ALPHA_FOR_Y |
  MAX_ALPHA_FOR_Y |
  FULL_STEP_FOR_Y |
  MIN_DUAL_INFEAS_ALPHA_FOR_Y |
  SAFE_MIN_DUAL_INFEAS_ALPHA_FOR_Y |

Definition at line 235 of file IpBacktrackingLineSearch.hpp.

## Constructor & Destructor Documentation

Ipopt::BacktrackingLineSearch::BacktrackingLineSearch | ( | const SmartPtr< BacktrackingLSAcceptor > & | acceptor,
|  | const SmartPtr< RestorationPhase > & | resto_phase,
|  | const SmartPtr< ConvergenceCheck > & | conv_check |
| ) |  |  |

Constructor.

The acceptor implements the acceptance test for the line search. The PDSystemSolver object only needs to be provided (i.e. not NULL) if second order correction is to be used. The ConvergenceCheck object is used to determine whether the current iterate is acceptable (for example, the restoration phase is not started if the acceptability level has been reached). If conv_check is NULL, we assume that the current iterate is not acceptable (in the sense of the acceptable_tol option).

virtual Ipopt::BacktrackingLineSearch::~BacktrackingLineSearch | ( |  | ) | `[virtual]`

Default destructor.

Ipopt::BacktrackingLineSearch::BacktrackingLineSearch | ( | const BacktrackingLineSearch & |  | ) | `[private]`

Copy Constructor.

## Member Function Documentation

virtual bool Ipopt::BacktrackingLineSearch::InitializeImpl | ( | const OptionsList & | options,
|  | const std::string & | prefix |
| ) |  |  | `[virtual]`

InitializeImpl - overloaded from AlgorithmStrategyObject.

Implements Ipopt::AlgorithmStrategyObject.

virtual void Ipopt::BacktrackingLineSearch::FindAcceptableTrialPoint | ( |  | ) | `[virtual]`

Perform the line search.

It is assumed that the search direction is computed in the data object.

Implements Ipopt::LineSearch.

virtual void Ipopt::BacktrackingLineSearch::Reset | ( |  | ) | `[virtual]`

Reset the line search.

This function should be called if all previous information should be discarded when the line search is performed the next time. For example, this method should be called if the barrier parameter is changed.

Implements Ipopt::LineSearch.

virtual void Ipopt::BacktrackingLineSearch::SetRigorousLineSearch | ( | bool | rigorous | ) | `[inline, virtual]`

Set flag indicating whether a very rigorous line search should be performed.

If this flag is set to true, the line search algorithm might decide to abort the line search and not to accept a new iterate. If the line search decided not to accept a new iterate, the return value of CheckSkippedLineSearch() is true at the next call. For example, in the non-monotone barrier parameter update procedure, the filter algorithm should not switch to the restoration phase in the free mode; instead, the algorithm should swtich to the fixed mode.

Implements Ipopt::LineSearch.

Definition at line 87 of file IpBacktrackingLineSearch.hpp.

References rigorous_.

virtual bool Ipopt::BacktrackingLineSearch::CheckSkippedLineSearch | ( |  | ) | `[inline, virtual]`

Check if the line search procedure didn't accept a new iterate during the last call of FindAcceptableTrialPoint().

Implements Ipopt::LineSearch.

Definition at line 96 of file IpBacktrackingLineSearch.hpp.

References skipped_line_search_.

virtual bool Ipopt::BacktrackingLineSearch::ActivateFallbackMechanism | ( |  | ) | `[virtual]`

Activate fallback mechanism.

Return false, if that is not possible.

Implements Ipopt::LineSearch.

static void Ipopt::BacktrackingLineSearch::RegisterOptions | ( | SmartPtr< RegisteredOptions > | roptions | ) | `[static]`

Methods for OptionsList.

void Ipopt::BacktrackingLineSearch::operator= | ( | const BacktrackingLineSearch & |  | ) | `[private]`

Overloaded Equals Operator.

bool Ipopt::BacktrackingLineSearch::DoBacktrackingLineSearch | ( | bool | skip_first_trial_point,
|  | Number & | alpha_primal,
|  | bool & | corr_taken,
|  | bool & | soc_taken,
|  | Index & | n_steps,
|  | bool & | evaluation_error,
|  | SmartPtr< IteratesVector > & | actual_delta |
| ) |  |  | `[private]`

Method performing the backtracking line search.

The return value indicates if the step acceptance criteria are met. If the watchdog is active, only one trial step is performed (and the trial values are set accordingly).

void Ipopt::BacktrackingLineSearch::StartWatchDog | ( |  | ) | `[private]`

Method for starting the watch dog.

Set all appropriate fields accordingly

void Ipopt::BacktrackingLineSearch::StopWatchDog | ( | SmartPtr< IteratesVector > & | actual_delta | ) | `[private]`

Method for stopping the watch dog.

Set all appropriate fields accordingly.

bool Ipopt::BacktrackingLineSearch::CheckAcceptabilityOfTrialPoint | ( | Number | alpha_primal | ) | `[private]`

Method for checking if current trial point is acceptable.

It is assumed that the delta information in ip_data is the search direction used in criteria. The primal trial point has to be set before the call.

static bool Ipopt::BacktrackingLineSearch::Compare_le | ( | Number | lhs,
|  | Number | rhs,
|  | Number | BasVal |
| ) |  |  | `[static, private]`

Check comparison "lhs <= rhs", using machine precision based on BasVal.

void Ipopt::BacktrackingLineSearch::PerformDualStep | ( | Number | alpha_primal,
|  | Number | alpha_dual,
|  | SmartPtr< IteratesVector > & | delta |
| ) |  |  | `[private]`

Method for setting the dual variables in the trial fields in IpData, given the search direction.

The step size for the bound multipliers is alpha_dual (the fraction-to-the-boundary step size), and the step size for the equality constraint multipliers depends on the choice of alpha_for_y.

bool Ipopt::BacktrackingLineSearch::TrySoftRestoStep | ( | SmartPtr< IteratesVector > & | actual_delta,
|  | bool & | satisfies_original_criterion |
| ) |  |  | `[private]`

Try a step for the soft restoration phase and check if it is acceptable.

The step size is identical for all variables. A point is accepted if it is acceptable for the original acceptability criterion (in which case satisfies_original_criterion = true on return), or if the primal-dual system error was decrease by at least the factor soft_resto_pderror_reduction_factor_. The return value is true, if the trial point was acceptable for the soft restoration phase.

bool Ipopt::BacktrackingLineSearch::TrySecondOrderCorrection | ( | Number | alpha_primal_test,
|  | Number & | alpha_primal,
|  | SmartPtr< IteratesVector > & | actual_delta |
| ) |  |  | `[private]`

Try a second order correction for the constraints.

If the first trial step (with incoming alpha_primal) has been reject, this tries up to max_soc_ second order corrections for the constraints. Here, alpha_primal_test is the step size that has to be used in the filter acceptance tests. On output actual_delta_... has been set to the steps including the second order correction if it has been accepted, otherwise it is unchanged. If the SOC step has been accepted, alpha_primal has the fraction-to-the-boundary value for the SOC step on output. The return value is true, if an SOC step has been accepted.

bool Ipopt::BacktrackingLineSearch::TryCorrector | ( | Number | alpha_primal_test,
|  | Number & | alpha_primal,
|  | SmartPtr< IteratesVector > & | actual_delta |
| ) |  |  | `[private]`

Try higher order corrector (for fast local convergence).

In contrast to a second order correction step, which tries to make an unacceptable point acceptable by improving constraint violation, this corrector step is tried even if the regular primal-dual step is acceptable.

void Ipopt::BacktrackingLineSearch::PerformMagicStep | ( |  | ) | `[private]`

Perform magic steps.

Take the current values of the slacks in trial and replace them by better ones that lead to smaller values of the barrier function and less constraint violation.

bool Ipopt::BacktrackingLineSearch::DetectTinyStep | ( |  | ) | `[private]`

Detect if the search direction is too small.

This should be true if the search direction is so small that if makes numerically no difference.

void Ipopt::BacktrackingLineSearch::StoreAcceptablePoint | ( |  | ) | `[private]`

Store current iterate as acceptable point.

bool Ipopt::BacktrackingLineSearch::RestoreAcceptablePoint | ( |  | ) | `[private]`

Restore acceptable point into the current fields of IpData if found.

Returns true if such as point is available.

bool Ipopt::BacktrackingLineSearch::CurrentIsAcceptable | ( |  | ) | `[private]`

Method for determining if the current iterate is acceptable (in the sense of the acceptable_tol options).

This is a wrapper for same method from ConvergenceCheck, but returns false, if no ConvergenceCheck object is provided.

## Member Data Documentation

Number Ipopt::BacktrackingLineSearch::alpha_red_factor_`[private]`

factor by which search direction is to be shortened if trial point is rejected.

Definition at line 232 of file IpBacktrackingLineSearch.hpp.

AlphaForYEnum Ipopt::BacktrackingLineSearch::alpha_for_y_`[private]`

Flag indicating whether the dual step size is to be used for the equality constraint multipliers.

If 0, the primal step size is used, if 1 the dual step size, and if 2, the minimum of both.

Definition at line 248 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::soft_resto_pderror_reduction_factor_`[private]`

Reduction factor for the restoration phase that accepts steps reducing the optimality error ("soft restoration phase").

If 0., then this restoration phase is not enabled.

Definition at line 253 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::max_soft_resto_iters_`[private]`

Maximal number of iterations that can be done in the soft iteration phase before the algorithm reverts to the regular restoration phase.

Definition at line 257 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::magic_steps_`[private]`

Flag indicating whether magic steps should be used.

Definition at line 260 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::accept_every_trial_step_`[private]`

Flag indicating whether the line search should always accept the full (fraction-to-the-boundary) step.

Definition at line 263 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::expect_infeasible_problem_`[private]`

Indicates whether problem can be expected to be infeasible.

This will trigger requesting a tighter reduction in infeasibility the first time the restoration phase is called.

Definition at line 268 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::expect_infeasible_problem_ctol_`[private]`

Tolerance on constraint violation for expect_infeasible_problem heuristic.

If the constraint violation becomes that than this value, the heuristic is disabled for the rest of the optimization run.

Definition at line 273 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::tiny_step_tol_`[private]`

Tolerance for detecting tiny steps.

Definition at line 276 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::tiny_step_y_tol_`[private]`

Tolerance for y variables for the tiny step stopping heuristic.

If repeatedly a tiny step is detected and the step in the y_c and y_d variables is less than this threshold, we algorithm will stop.

Definition at line 282 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_max_`[private]`

Number of watch dog trial steps.

Definition at line 285 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_trigger_`[private]`

Number of shortened iterations that trigger the watchdog.

Definition at line 287 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::start_with_resto_`[private]`

Indicates whether the algorithm should start directly with the restoratin phase.

Definition at line 291 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::in_watchdog_`[private]`

Flag indicating if the watchdog is active.

Definition at line 297 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_`[private]`

Counter for shortened iterations.

Definition at line 299 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_`[private]`

Counter for watch dog iterations.

Definition at line 301 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::watchdog_alpha_primal_test_`[private]`

Step size for Armijo test in watch dog.

Definition at line 303 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::watchdog_iterate_`[private]`

Watchdog reference iterate.

Definition at line 305 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::watchdog_delta_`[private]`

Watchdog search direction at reference point.

Definition at line 307 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::last_mu_`[private]`

Barrier parameter value during last line search.

Definition at line 309 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::acceptable_iterate_`[private]`

Definition at line 315 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::acceptable_iteration_number_`[private]`

Definition at line 316 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::fallback_activated_`[private]`

Flag indicating whether the algorithm has asked to immediately switch to the fallback mechanism (restoration phase).

Definition at line 321 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::rigorous_`[private]`

Flag indicating whether the line search is to be performed robust (usually this is true, unless SetRigorousLineSearch is called with false).

Definition at line 327 of file IpBacktrackingLineSearch.hpp.

Referenced by SetRigorousLineSearch().

bool Ipopt::BacktrackingLineSearch::skipped_line_search_`[private]`

Flag indicating whether no acceptable trial point was found during last line search.

Definition at line 331 of file IpBacktrackingLineSearch.hpp.

Referenced by CheckSkippedLineSearch().

bool Ipopt::BacktrackingLineSearch::in_soft_resto_phase_`[private]`

Flag indicating whether we are currently in the "soft" restoration phase mode, in which steps are accepted if they reduce the optimality error (see soft_resto_pderror_reduction_factor).

Definition at line 337 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::soft_resto_counter_`[private]`

Counter for iteration performed in soft restoration phase in a row.

Definition at line 341 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::count_successive_shortened_steps_`[private]`

Counter for the number of successive iterations in which the full step was not accepted.

Definition at line 345 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::tiny_step_last_iteration_`[private]`

Flag indicating if a tiny step was detected in previous iteration.

Definition at line 349 of file IpBacktrackingLineSearch.hpp.

SmartPtr<BacktrackingLSAcceptor> Ipopt::BacktrackingLineSearch::acceptor_`[private]`

Definition at line 353 of file IpBacktrackingLineSearch.hpp.

SmartPtr<RestorationPhase> Ipopt::BacktrackingLineSearch::resto_phase_`[private]`

Definition at line 354 of file IpBacktrackingLineSearch.hpp.

SmartPtr<ConvergenceCheck> Ipopt::BacktrackingLineSearch::conv_check_`[private]`

Definition at line 355 of file IpBacktrackingLineSearch.hpp.

The documentation for this class was generated from the following file:

- /home/coin/SVN-release/Ipopt-3.2.1/Ipopt/src/Algorithm/IpBacktrackingLineSearch.hpp