Derivative free optimization

Author: Brian Holcomb (bh597), Alejandra Chaparro Ramirez (mac593), Brian Worts (blw87), Trenton Berardi (tnb38), Ifeloluwa Osilaja (io62) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Derivative-Free Optimization (DFO) is a collection of computational methods used to find optimal values in situations where traditional optimization techniques that rely on derivatives are impractical or impossible to apply and is a type of black box optimization (Audet, 2017). Instead of requiring derivatives of an objective function, DFO methods iteratively search through a set of evaluated points to approximate an optimal solution. This approach is especially useful for black-box models where derivatives are unavailable, noisy, or computationally expensive to compute, most commonly such as in simulations, machine learning applications, or physical system modeling (Audet, 2017).

The motivation behind DFO emerged from a need to solve complex optimization problems in fields like engineering, finance, and logistics, where objective functions are often opaque or inaccessible for differentiation (Conn, 2009). Since the early 20th century, methods like pattern search and genetic algorithms have evolved, providing researchers with tools to tackle optimization in high-dimensional, uncertain environments. In fact, until relatively recently computing derivatives was the single most common source of user error in applying optimization software(Conn, 2009). The primary goal of studying DFO is to enable efficient optimization when traditional methods fall short, particularly for models that are too complex or costly for gradient-based methods. DFO techniques have proven essential in areas like supply chain planning, engineering design, and financial modeling, where optimization can significantly impact operational efficiency and decision-making.

Algorithm Description

There are multiple methods of Derivative-Free Optimization that are available. While DFO algorithms do not require one to calculate the derivative of the objective function, they rely on the algorithm to narrow the examined range of the objective function over multiple iterations by selecting points along the objective function and determining if the local minimum exists between these points. Two of these methods include Golden Section Search and Successive Parabolic Interpolation. Both operate in a similar fashion by evaluating the relationship between three points selected along the objective function and making decisions in order to narrow the examination window along the objective function where the points are selected for the next iteration. The main difference is how these three points are selected and how they are evaluated.

Golden Section Search

Example of Golden Search Algorithm through three iterations on function $y=(x-1)^{3}-x+2$

Golden Section Search gets its name from the ratio of points selected along the objective function which aligns closely to the Golden Ratio.

Step 1: Identify a function, ${\textstyle f(x)}$, with the objective to find the minimum value over a given range.

Step 2: Select two points that are on both sides of the function’s minimum. The first point, ${\textstyle a}$, will be on the left side of the minimum and the second point, ${\textstyle b}$, will be on the right side of the minimum. The section of function, ${\textstyle f(x)}$, between points ${\textstyle a}$ and ${\textstyle b}$ will form the examination window.

Step 3: Select two more points named $x_{1}$ and $x_{2}$ as per the equations below. These will be spaced within the examination window between points ${\textstyle a}$ and ${\textstyle b}$ by the golden ratio as defined via constant $c$.

$c={\frac {-1+{\sqrt {5}}}{2}}$

$x_{1}=c\cdot a+(1-c)\cdot b$

$x_{2}=(1-c)\cdot a+c\cdot b$

Step 4: Evaluate and compare the objective function at $x_{1}$ and $x_{2}$.

Step 4a: If $f(x_{1})\leq f(x_{2})$, restrict the range of $x\in [a,x_{2}]$.

$b=x_{2}$

$x_{2}=x_{1}$

$f_{2}=f_{1}$

$x_{1}=c\cdot a+(1-c)\cdot b$

$f_{1}=f(x_{1})$

Step 4b: if $f(x_{1})>f(x_{2})$, restrict the range of $x\in [x_{1},b]$.

$a=x_{1}$

$x_{1}=x_{2}$

$f_{1}=f_{2}$

$x_{2}=(1-c)\cdot a+c\cdot b$

$f_{2}=f(x_{2})$

Step 5: Repeat step 3 and step 4 until one of the following criteria is met:

1. The number of iterations surpasses the target number, $n$.
2. The difference between variables $a$ and $b$ is a small number such as 1E-4.

Note: This algorithm will not produce the exact value for the function minimum. It will predict that the minimum will be between $a$ and $b$.

Figure 5. Flow Chart describing the Golden Ratio Algorithm

Successive Parabolic Interpolation

This algorithm leverages building a parabola defined by 3 points selected on a function $f(x)$. The shape of the parabola is used to narrow the examined range on the function to find where the function minimum is located. While the derivative of the objective function is not utilized, the derivative of the parabola is used.

Step 1: Identify a function, $f(x)$, with the objective to find the minimum value.

Step 2: Identify three points on the function, $x_{1}$,$x_{2}$,$x_{3}$. Two of the points will act as the outer bounds of the examination region and the third point will be in between these two.

Step 3: Form a parabola between the three points identified on function $f(x)$. The parabola can be defined using the Lagrange Interpolation Formula:

$p(x)=f(x_{1})*{\frac {(x-x_{2})(x-x_{3})}{(x_{1}-x_{2})(x_{1}-x_{3})}}+f(x_{2})*{\frac {(x-x_{1})(x-x_{3})}{(x_{2}-x_{1})(x_{2}-x_{3})}}+f(x_{3})*{\frac {(x-x_{1})(x-x_{2})}{(x_{3}-x_{1})(x_{2}-x_{2})}}$

Step 4: The minimum of the parabola function will be where the first derivative of the parabola function equals to 0 and will align towards where the minimum of the function, $f(x)$, is located.

$p'(x_{0})=0$

$x_{0}={\frac {x_{1}+x_{2}}{2}}-{\frac {{\bigl (}f(x_{2})-f(x_{1}){\bigr )}(x_{3}-x_{1})(x_{3}-x_{2})}{2{\Bigl (}(x_{2}-x_{2}){\bigl (}f(x_{3})-f(x_{2}){\bigr )}-{\bigl (}f(x_{2})-f(x_{1}){\bigr )}(x_{3}-x_{2}){\Bigr )}}}$

Step 5: Compare the value of $x_{0}$ to $x_{2}$ and determine the next step for iteration.

Step 5a: If $x_{0}\leq x_{2}$ then shrink the examination range to be $x\in [x_{1},x_{2}]$.

$x_{1}^{new}=x_{1}^{old}$

$x_{2}^{new}=x_{0}$

$x_{3}^{new}=x_{2}^{old}$

Step 5b: If $x_{0}>x_{2}$ then shrink the examination range to be $x\in [x_{2},x_{3}]$.

$x_{1}^{new}=x_{2}^{old}$

$x_{2}^{new}=x_{0}$

$x_{3}^{new}=x_{3}^{old}$

Step 6: Repeat step 4 and step 5 until one of the following criteria is met:

1. The number of iterations surpasses the target number, $n$.
2. The difference between variables $x_{1}$ and $x_{3}$ is a small number such as 1E-4.

Note: This algorithm will not produce the exact value for the function minimum. It will predict that the minimum will be between $x_{1}$ and $x_{2}$.

Flow Chart describing the Successive Parabolic Interpolation Algorithm

Numerical Examples

Example 1: Golden Section Search

Example of Golden Ratio Search on $f(x)=(x-2)^{2}+1$.

Suppose there is a function$f(x)=(x-2)^{2}+1$, and the aim is to find its minimum within the interval $[a,b]=[0,5]$.

Initial Setup:

Set $a=0$ and $b=0$

Define the golden ratio constant $c\approx 0.618$

Calculate two internal points within $[a,b]$

$x_{1}=c*a=(1-c)*b=0.618*0+(1-0618)*5\approx 1.91$

$x_{2}=(1-c)*a+c*b=(1-0.618)*0+0.618*5\approx 3.09$

Iterative Evaluation:

Evaluate $f(x_{1})=(1.91-2)^{2}+1\approx 1.01$ and $f(x_{2})=(3.09-2)^{2}+1\approx 2.19$

Since $f(x_{1})\leq f(x_{2})$, update the interval to $[a,x_{2}]=[0,3.09]$and set $b=x_{2}=3.09$

Recalculate:

New $x_{2}=x_{1}\approx 1.91$

New $x_{2}=c*a+(1=-c)*b\approx 1.18$

Convergence:

Repeat this process, recalculating $x_{1}$ and $x_{2}$ and updating the interval until the difference between $a$ and $b$ is less than 1E-4 .

After a few iterations, the interval narrows around $x=2$, the minimum of the function, where $f(x)=1$.

Example 2: Successive Parabolic Interpolation

Consider the same function $f(x)=(x-2)^{2}+1$ and aim to find its minimum within an interval. Start with initial points $x_{1}=0$, $x_{2}=2$, and $x_{3}=4$.

Initial Setup:

Select points: $x_{1}=0$, $x_{2}=2$, and $x_{3}=4$

Evaluate $f(x_{1})=5$, $f(x_{2})=1$, and $f(x_{3})=5$

Parabolic Interpolation:

Construct a parabola $p(x)$ through points $(x_{1},f(x_{1})),(x_{2},f(x_{2}))$, and $(x_{3},f(x_{3}))$.

Using the formula for $x_{0}$ where $p'(x)=0$, calculate: $x_{0}=x_{1}+x_{2}-\left({\frac {(f(x_{2})-f(x_{1}))(x_{3}-x_{1})(x_{3}-x_{2})}{2((x_{2}-x_{1})(f(x_{3})-f(x_{2}))-(f(x_{2})-f(x_{1}))(x_{3}-x_{2}))}}\right)$

Substituting values gives $x_{0}=2$, which is close to the minimum.

Updating the Interval:

Since $x_{0}\approx x_{2}$, shrink the interval to either $[x_{1},x_{2}]$or $[x_{2},x_{3}]$as needed.

Set new points: $x_{1}=1$, $x_{2}=x_{0}\approx 2$, $x_{3}=3$.

Convergence:

Repeat the iteration, adjusting points and recalculating 𝑥0 until the difference between $x_{1}$ and $x_{3}$ is less than 1E-4 .

The result converges around $x=2$, where the function minimum $f(x)=1$ is located.

Applications

Oil and Gas

Derivative-Free Optimization (DFO) has a number of real world applications, including in the oil industry since often the cost functions and constraints require simulations of fluid mechanics where the gradient information cannot be obtained efficiently. This is an important problem that needs to be solved since oil and natural gas make up a significant source of the world’s current energy supply, so maximizing efficiency has global implications to the global economy and environments (IEA, 2021). Specifically, DFO can be used, among other techniques, to optimize the production of oil. This is done by creating discretized simulations of very complex oil-water systems, using as many known variables as possible like fluid mechanics and seismic effects (Ciaurri, 2011). Thus, the minimization problem and its constraints become known and a search of the gradients becomes possible. Two such DFO methods are the generalized pattern search and the Hookes-Jeeves Direct Search (Hooke, 1961). The generalized pattern search is a search algorithm for “derivative-free unconstrained optimization” divided into “search” and “poll” phases (Audet, 2000). In the search phase, a finite number of points are evaluated to find a minimum on a mesh. The poll phase is then used to poll the neighboring points on the mesh to find a better minimum before the process is repeated using a more refined mesh or an iterated search. The Hookes-Jeeves Direct Search method is a “Compass-based pattern search method” with an exploratory mode and a pattern mode, similar to that of the generalized pattern search (Hooke, 1961). In the exploratory mode, the local area is searched to refine the optima estimate while the pattern phase is used to identify patterns in the exploratory phase moves, which results in a better guess in the direction of the optima (Hooke, 1961). Using these search methods to analyze their analysis results, the optimal control scheme to optimize oil production was determined. This was done by simulating using constraints for the water quantity, water to oil ratio, and resulting oil output while they searched for the optimal water pressure to use that minimizes cost (Ciaurri, 2011). They varied the configurations as well as utilized variations of the generalized pattern search and the Hookes-Jeeves Direct Search to search their gradients and find the optima. This work resulted in finding a feasible and optimal configuration scheme, expected profits, an increase in oil production, a decrease in water consumption, and thus showed how DFO computational techniques can be applied to improve industries.

Engineering

Another real-world application of DFO is for the minimization of the number of seismic dampers to use to reduce the damage that tall buildings cause to each other during an earthquake in dense urban environments. Such events can put thousands of lives in danger and caused billions of dollars in damage in 2023 (USGS, 2023). Shock absorbing dampers, originally developed by NASA for the Apollo programs, are used to in building construction to join adjacent buildings together which reduces the chance that buildings collide while increasing the structural stability overall (NASA, 2015). The upfront cost of seismic dampers is extremely high, so it is desirable to minimize the number of dampers that are required to put the building’s risk of damage in an earthquake within acceptable limits. Thus, DFO, and specifically Model-Based DFO, is the optimal choice for solving this kind of problem since the objective function is a “numerical integration” generated through an earthquake simulator that results in the optimizer not having access to the objective function gradients (Audet, 2017). Other optimization applications in this field, such as in minimizing peak floor accelerations in multi-story buildings when subjected to earthquakes, may also benefit from DFO as can resolve the issues of noisy or discontinuous objective functions that pop up in these applications (Ortega, 24).

Medical

Using Model-Based DFO consistently beats other methods in its efficiency of earthquake retrofitting optimization like Genetic Algorithms and Nelder-Mead since, in this application, the objective function appears to be differentiable which makes it an ideal use case (Audet, 2017). One application that highly relies on DFO is the medical experimentation field. In the medical experimentation field DFO is often needed due to the complexity, noisy, non-differentiable functions or lack of ability to acquire data to obtain functions. An example of this is in cancer treatment where chemotherapy regimens involve 20+ independent variables with vast amounts of interdependent biological responses. Many biological responses are non-linear. Collection of testing combinations of these chemotherapy, dosage amounts, and interval timing between doses are not feasible; therefore there is not an ability to create a response function in order to use gradient optimization. Nelder and Mead (1964) and Box (1964) methods are example DFO algorithms that have been used in this chemotherapy optimization problem. These are examples of Direct Search Methods (DSM) that help narrow the field of combinations of variables. A case study of this can be found in Berenbaum MC. “Direct search methods in the optimisation of cancer chemotherapy regimens (1990).” Nealder-Mead is a common optimizer option in common tools such as Excel, Python (SciPy) and MATLAB.

Conclusion

Thanks to its robustness, Derivative-Free Optimization (DFO) has emerged as a useful method of solving complex optimization problems where traditional methods that require derivatives to be available are not practical. This method of optimization is limited by the high computation cost, sensitivity to noise that leads to imperfect results, and the lack of gradient information that leads to slower convergence. However, advancements in computational power and algorithmic design are helping to mitigate these challenges, making DFO methods more efficient and accessible. There are numerous applications of DFO including in the oil, architecture, and medical industries where solving optimization problems has implications on global and local economies, the environment, and people’s health.

These examples demonstrate the usefulness that computational optimization has on humanity and its importance in our continuingly complex modern world. As the world continues to grow, environments continue to change, and better data becomes available, the methods of DFO will continue to grow with the world while helping humanity solve many of its most important challenges.