lectures/derivativeFreeOptimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "41df9272",
   "metadata": {},
   "source": [
    "# Derivative-free optimization\n",
    "### Carl Fredrik Berg, NTNU, 2023\n",
    "\n",
    "In the following notes we will discuss optimization of a function when its derivative is either unavailable, hard to obtain or unreliable. This is common in geoscience, as the models are can be too complicated to find the derivative. Further, as function evaluations can be computationally heavy, it is hard to calculate numerical approximations for the derivative. Lastly, the response surface of the models can be erratic, thus making the derivative unreliable for optimization purposes. Derivative-free methods might also be better to avoid being trapped in a local extrema for multi-modal functions.\n",
    "\n",
    "Again, let $F \\colon \\mathbb{R}^n \\to \\mathbb{R}$ be a multi-variable real-valued function. We want to find a point $x_o \\in \\mathbb{R}^n$ such that $F(x_o) \\leq F(x)$ for all $x \\in \\mathbb{R}^n$ (or, inversely, finding the maxima by finding a $x_o \\in \\mathbb{R}^n$ such that $F(x_o) \\geq F(x)$ for all $x \\in \\mathbb{R}^n$). The derivative based methods use the local derivative to find the steepest decent (ascent), and then move in the steepest decent direction. \n",
    "\n",
    "As the name indicates, derivative-free methods do not use the derivative in the optimization, they only use function evaluations. They might still use methods that resemble numerical derivative (see the pattern search algorithm below). Instead of using the derivatives, they use some sort of metaheuristic methods: A <i>heuristic</i> is a procedure for solving a problem, either more quickly when the classical methods are too slow, or approximately when classical methods fail to find exact solutions. \n",
    "\n",
    "We might divide the metaheuristic algorithms into two classes, based on the number of candidate solutions used in each iteration. Single-solution based metaheuristic algorithms include the simulated annealing, as we will explore in an upcoming note. Population based metaheuristic algorithms have a population of test candidates that interact at each iteration. These population based algorithms include evolutionary algorithms such as the genetic algorithm (GA), and swarm-intelligence algorithms such as the particle swarm optimization (PSO). Both will be consider in the upcoming notes.\n",
    "\n",
    "Derivative-free optimization methods often have input parameters, which might require tuning to obtain good converge of the methods. In general, one might need to use different methods for different problems, so derivative-free optimization is a bit of an art, unfortunately.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef3fbda5",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}