Users:Structural Optimization/Optimization Algorithms/Line Search

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:

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.

• 

  Passed Armijo Test

• 

  Failed Armijo Test

Input Parameters:

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

• 

  Line Minimum Outside Search Region

• 

  Line Minimum Inside Search Region

Input Parameters:

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:

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:

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:

Example of a complete input block:

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