Users:Structural Optimization/Optimization Algorithms/Line Search

From Carat++ Public Wiki
< Users:Structural Optimization | Optimization Algorithms
Revision as of 14:36, 30 August 2010 by Michi (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Contents

Motivation

Each optimization strategy computes a search direction s according to a specified algorithm. The line search specifies a suitable step length parameter α that minimizes the objective if the design is changed according to the search direction. The final design update is then computed by α * s.

Line Search Methods

The following line search methods are actually implemented in Carat++.

Fixed step length

This method uses a fixed step length parameter (MAX_STEP_LENGTH) for the whole optimization problem. It is the most simple line search method. The fixed step length method just needs one function evaluation per optimization step.

Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : FIXED ID and identifier of line search method
MAX_STEP_LENGTH float fixed step length

Example of a complete input block:

OPT-LINE_SEARCH 1 : FIXED
  MAX_STEP_LENGTH = 0.5

Armijo test

Strictly speaking the Armijo test is not a line search procedure. The Armijo test simply checks if the objective could be decreased by a specified value. If not, the Armijo test fails. The minimum objective improvement is computed by ARMIJO_PARAMETER * f(x_i). Whenever the new design evaluation f(x_i+1) < f(x_i) - ARMIJO_PARAMETER * f(x_i) the test is passed, c.f. figures below. The Armijo just needs one function evaluation per step and is therefore extremely cheap.


Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : ARMIJO ID and identifier of line search method
MAX_STEP_LENGTH float fixed step length
ARMIJO_PARAMETER float Quantity of the actual objective that has to be decreased in the actual optimization step to pass the test.

Example of a complete input block:

OPT-LINE_SEARCH 1 : ARMIJO
  MAX_STEP_LENGTH = 0.5
  ARMIJO_PARAMETER = 0.025

3 Point Line Search

The 3 point line search computes the minimum of a quadratic function which is established between 3 points, denoted by P1, P2 and P3. Point P1 is the current design. P2 is computed by by a design update with 0.5 * MAX_STEP_LENGTH * search direction. P3 follows by 1.0 * MAX_STEP_LENGTH * search direction. The 3 point line search needs at least two function evaluations for the points P2 and P3. Whenever the optimal step length is between 0 and MAX_STEP_LENGTH, a third function evaluation becomes necessary (P_opt). It is important to note that the 3 Point Line Search does not extrapolate. The maximum allowable step length is in any case equals MAX_STEP_LENGTH. Whenever the computed minimum is outside the search region, point P3 is treated as new design. In this case only 2 design evaluations where necessary (P2 and P3).

Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : 3-POINT ID and identifier of line search method
MAX_STEP_LENGTH float fixed step length

Example of a complete input block:

OPT-LINE_SEARCH 1 : 3-POINT
  MAX_STEP_LENGTH = 0.5

Adaptive 3 Point Line Search

This method is based on the 3 Point Line Search. In general, the search distance for the actual step is computed by search_distance = 2.0 * old_step_length. The valid region for the new step length is defined by MIN_STEP_LENGTH <= new_step_length <= MAX_STEP_LENGTH. The adaptive 3 point line search needs at least two function evaluations. This line search is the most precise one.

Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : 3-POINT_ADAPTIVE ID and identifier of line search method
MAX_STEP_LENGTH float fixed maximum step length
MIN_STEP_LENGTH float fixed minimum step length

Example of a complete input block:

OPT-LINE_SEARCH 1 : 3-POINT_ADAPTIVE
  MAX_STEP_LENGTH = 0.5
  MIN_STEP_LENGTH = 0.1

Armijo 3 Point Adaptive

This line search is a combination of the Armijo test and the adaptive 3 point line search. As long as the Armijo test is fulfilled the step length parameter is chosen according to the specified maximum value. As soon as the Armijo test failes for the first time, the further optimization steps use the adaptive 3 point line search for the step length estimation. This combination requires only a minimum number of function evaluations and ensures good accuracy.

Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : ARMIJO_3-POINT_ADAPTIVE ID and identifier of line search method
MAX_STEP_LENGTH float fixed maximum step length
MIN_STEP_LENGTH float fixed minimum step length
ARMIJO_PARAMETER float Quantity of the actual objective that has to be decreased in the actual optimization step to pass the test.

Example of a complete input block:

OPT-LINE_SEARCH 1 : ARMIJO_3-POINT_ADAPTIVE
  MAX_STEP_LENGTH = 0.5
  MIN_STEP_LENGTH = 0.1
  ARMIJO_PARAMETER = 0.025

Feasible Design Search and 3 Point Adaptive

This line search is a combination of the Fixed Line Search and the 3 Point Adaptive Line Search. The step length is computed according to the specified maximum value until the feasible domain is reached. As soon as the design is feasible, the further optimization steps use the adaptive 3 point line search for the step length estimation.


Input Parameters:

Compulsory Parameters
Parameter Values, Default(*) Description
OPT-LINE_SEARCH int : FDS_3-POINT_ADAPTIVE ID and identifier of line search method
MAX_STEP_LENGTH float fixed maximum step length
MIN_STEP_LENGTH float fixed minimum step length

Example of a complete input block:

OPT-LINE_SEARCH 1 : FDS_3-POINT_ADAPTIVE
  MAX_STEP_LENGTH = 0.5
  MIN_STEP_LENGTH = 0.1




Whos here now:   Members 0   Guests 0   Bots & Crawlers 1
 
Personal tools
Content for Developers