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

#include <IpBacktrackingLineSearch.hpp>

Inheritance diagram for Ipopt::BacktrackingLineSearch:

Public Member Functions
virtual bool	InitializeImpl (const OptionsList &options, const std::string &prefix)
	InitializeImpl - overloaded from AlgorithmStrategyObject. More...

virtual void	FindAcceptableTrialPoint ()
	Perform the line search. More...

virtual void	Reset ()
	Reset the line search. More...

virtual void	SetRigorousLineSearch (bool rigorous)
	Set flag indicating whether a very rigorous line search should be performed. More...

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

virtual bool	ActivateFallbackMechanism ()
	Activate fallback mechanism. More...

Constructors/Destructors
	BacktrackingLineSearch (const SmartPtr< BacktrackingLSAcceptor > &acceptor, const SmartPtr< RestorationPhase > &resto_phase, const SmartPtr< ConvergenceCheck > &conv_check)
	Constructor. More...

virtual	~BacktrackingLineSearch ()
	Default destructor. More...

Public Member Functions inherited from Ipopt::LineSearch
	LineSearch ()
	Default Constructor. More...

virtual	~LineSearch ()
	Default destructor. More...

Public Member Functions inherited from Ipopt::AlgorithmStrategyObject
bool	Initialize (const Journalist &jnlst, IpoptNLP &ip_nlp, IpoptData &ip_data, IpoptCalculatedQuantities &ip_cq, const OptionsList &options, const std::string &prefix)
	This method is called every time the algorithm starts again - it is used to reset any internal state. More...

bool	ReducedInitialize (const Journalist &jnlst, const OptionsList &options, const std::string &prefix)
	Reduced version of the Initialize method, which does not require special Ipopt information. More...

	AlgorithmStrategyObject ()
	Default Constructor. More...

virtual	~AlgorithmStrategyObject ()
	Default Destructor. More...

Public Member Functions inherited from Ipopt::ReferencedObject
	ReferencedObject ()

virtual	~ReferencedObject ()

Index	ReferenceCount () const

void	AddRef (const Referencer *referencer) const

void	ReleaseRef (const Referencer *referencer) const

Static Public Member Functions

static void	RegisterOptions (SmartPtr< RegisteredOptions > roptions)
	Methods for OptionsList. More...

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. More...

void	StartWatchDog ()
	Method for starting the watch dog. More...

void	StopWatchDog (SmartPtr< IteratesVector > &actual_delta)
	Method for stopping the watch dog. More...

bool	CheckAcceptabilityOfTrialPoint (Number alpha_primal)
	Method for checking if current trial point is acceptable. More...

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. More...

bool	TrySoftRestoStep (SmartPtr< IteratesVector > &actual_delta, bool &satisfies_original_criterion)
	Try a step for the soft restoration phase and check if it is acceptable. More...

bool	TrySecondOrderCorrection (Number alpha_primal_test, Number &alpha_primal, SmartPtr< IteratesVector > &actual_delta)
	Try a second order correction for the constraints. More...

bool	TryCorrector (Number alpha_primal_test, Number &alpha_primal, SmartPtr< IteratesVector > &actual_delta)
	Try higher order corrector (for fast local convergence). More...

void	PerformMagicStep ()
	Perform magic steps. More...

bool	DetectTinyStep ()
	Detect if the search direction is too small. More...

void	StoreAcceptablePoint ()
	Store current iterate as acceptable point. More...

bool	RestoreAcceptablePoint ()
	Restore acceptable point into the current fields of IpData if found. More...

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

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. More...

void	operator= (const BacktrackingLineSearch &)
	Overloaded Equals Operator. More...

Private Attributes
bool	fallback_activated_
	Flag indicating whether the algorithm has asked to immediately switch to the fallback mechanism (restoration phase) More...

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

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

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) More...

Index	soft_resto_counter_
	Counter for iteration performed in soft restoration phase in a row. More...

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

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

Information related to watchdog procedure
bool	in_watchdog_
	Flag indicating if the watchdog is active. More...

Index	watchdog_shortened_iter_
	Counter for shortened iterations. More...

Index	watchdog_trial_iter_
	Counter for watch dog iterations. More...

Number	watchdog_alpha_primal_test_
	Step size for Armijo test in watch dog. More...

SmartPtr< const IteratesVector >	watchdog_iterate_
	Watchdog reference iterate. More...

SmartPtr< const IteratesVector >	watchdog_delta_
	Watchdog search direction at reference point. More...

Number	last_mu_
	Barrier parameter value during last line search. More...

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. More...

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

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

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

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. More...

bool	magic_steps_
	Flag indicating whether magic steps should be used. More...

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

Index	accept_after_max_steps_
	Maximal number of trial steps before we blindly accept trial point. More...

bool	expect_infeasible_problem_
	Indicates whether problem can be expected to be infeasible. More...

Number	expect_infeasible_problem_ctol_
	Tolerance on constraint violation for expect_infeasible_problem heuristic. More...

Number	expect_infeasible_problem_ytol_
	Trigger tolerance on constraint multipliers. More...

Number	tiny_step_tol_
	Tolerance for detecting tiny steps. More...

Number	tiny_step_y_tol_
	Tolerance for y variables for the tiny step stopping heuristic. More...

Index	watchdog_trial_iter_max_
	Number of watch dog trial steps. More...

Index	watchdog_shortened_iter_trigger_
	Number of shortened iterations that trigger the watchdog. More...

bool	start_with_resto_
	Indicates whether the algorithm should start directly with the restoratin phase. More...

Additional Inherited Members
Protected Member Functions inherited from Ipopt::AlgorithmStrategyObject
const Journalist &	Jnlst () const

IpoptNLP &	IpNLP () const

IpoptData &	IpData () const

IpoptCalculatedQuantities &	IpCq () const

bool	HaveIpData () const

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 228 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 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 )

inlinevirtual

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

virtual bool Ipopt::BacktrackingLineSearch::CheckSkippedLineSearch ( )

inlinevirtual

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

Implements Ipopt::LineSearch.

Definition at line 94 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.

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.

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 225 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 245 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 249 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 254 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 258 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::magic_steps_

private

Flag indicating whether magic steps should be used.

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

Index Ipopt::BacktrackingLineSearch::accept_after_max_steps_

private

Maximal number of trial steps before we blindly accept trial point.

If set to value other than -1, we accept a trial point even if it is not satisfying acceptance criteria.

Definition at line 268 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 273 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 278 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::expect_infeasible_problem_ytol_

private

Trigger tolerance on constraint multipliers.

If expect_infeasible_problem is chosen, and the multipliers become larger in max-norm than this value, the restoration phase is triggered.

Definition at line 283 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::tiny_step_tol_

private

Tolerance for detecting tiny steps.

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

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_max_

private

Number of watch dog trial steps.

Definition at line 295 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_trigger_

private

Number of shortened iterations that trigger the watchdog.

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

bool Ipopt::BacktrackingLineSearch::in_watchdog_

private

Flag indicating if the watchdog is active.

Definition at line 307 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_shortened_iter_

private

Counter for shortened iterations.

Definition at line 309 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::watchdog_trial_iter_

private

Counter for watch dog iterations.

Definition at line 311 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::watchdog_alpha_primal_test_

private

Step size for Armijo test in watch dog.

Definition at line 313 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::watchdog_iterate_

private

Watchdog reference iterate.

Definition at line 315 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::watchdog_delta_

private

Watchdog search direction at reference point.

Definition at line 317 of file IpBacktrackingLineSearch.hpp.

Number Ipopt::BacktrackingLineSearch::last_mu_

private

Barrier parameter value during last line search.

Definition at line 319 of file IpBacktrackingLineSearch.hpp.

SmartPtr<const IteratesVector> Ipopt::BacktrackingLineSearch::acceptable_iterate_

private

Definition at line 325 of file IpBacktrackingLineSearch.hpp.

Index Ipopt::BacktrackingLineSearch::acceptable_iteration_number_

private

Definition at line 326 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 331 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 337 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 341 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 347 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 351 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 355 of file IpBacktrackingLineSearch.hpp.

bool Ipopt::BacktrackingLineSearch::tiny_step_last_iteration_

private

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