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.

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_
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, PRIMAL_AND_FULL_ALPHA_FOR_Y, DUAL_AND_FULL_ALPHA_FOR_Y, LSACCEPTOR_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	alpha_for_y_tol_
	Tolerance for primal step to switch to full equality constraint multiplier steps.
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.

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
PRIMAL_AND_FULL_ALPHA_FOR_Y
DUAL_AND_FULL_ALPHA_FOR_Y
LSACCEPTOR_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.

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.

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.

Reimplemented from Ipopt::LineSearch.

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 252 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::alpha_for_y_tol_ [private]

Tolerance for primal step to switch to full equality constraint multiplier steps.

Definition at line 256 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 261 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 265 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::magic_steps_ [private]

Flag indicating whether magic steps should be used.

Definition at line 268 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 271 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 276 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 281 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::tiny_step_tol_ [private]

Tolerance for detecting tiny steps.

Definition at line 284 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 290 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_max_ [private]

Number of watch dog trial steps.

Definition at line 293 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_trigger_ [private]

Number of shortened iterations that trigger the watchdog.

Definition at line 295 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 299 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::in_watchdog_ [private]

Flag indicating if the watchdog is active.

Definition at line 305 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_ [private]

Counter for shortened iterations.

Definition at line 307 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_ [private]

Counter for watch dog iterations.

Definition at line 309 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::watchdog_alpha_primal_test_ [private]

Step size for Armijo test in watch dog.

Definition at line 311 of file IpBacktrackingLineSearch.hpp.

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

Watchdog reference iterate.

Definition at line 313 of file IpBacktrackingLineSearch.hpp.

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

Watchdog search direction at reference point.

Definition at line 315 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::last_mu_ [private]

Barrier parameter value during last line search.

Definition at line 317 of file IpBacktrackingLineSearch.hpp.

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

Definition at line 323 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::acceptable_iteration_number_ [private]

Definition at line 324 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 329 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 335 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::skipped_line_search_ [private]

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

Definition at line 339 of file IpBacktrackingLineSearch.hpp.

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 345 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 349 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 353 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 357 of file IpBacktrackingLineSearch.hpp.

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

Definition at line 361 of file IpBacktrackingLineSearch.hpp.