Users:Structural Optimization/Optimization Algorithms/Line 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.
Passed Armijo Test
Failed Armijo Test
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).
Line Minimum Outside Search Region
Line Minimum Inside Search Region
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 |
