{ "cells": [ { "cell_type": "markdown", "id": "bed6b269-bb6c-451b-b2c9-ac6fd9afd33d", "metadata": {}, "source": [ "# Project on Minimizing Functions (template)\n", "\n", "**Brenton LeMesurier**, lemesurierb@charleston.edu\n", "\n", "**Version of November 20, 2025**" ] }, { "cell_type": "markdown", "id": "553ad156-65d9-4f47-8d8d-95462e966cd6", "metadata": {}, "source": [ "## Introduction\n", "\n", "The background to this project is seen in Chapter {ref}`chapter-optimization`,\n", "and will start with the one dimensional case of minimizing a continuous function $f:[a, b] \\to \\mathbb{R}$,\n", "\n", "comparing two derivative-free methods:\n", "the {ref}`Golden Section Search `\n", "and\n", "{ref}`Successive Parabolic Interpolation `.\n", "\n", "A subsequent goal will be to consider functions of more dimensions — for this project, two is enough: $f:\\mathbb{R}^2 \\to \\mathbb{R}$." ] }, { "cell_type": "markdown", "id": "4550bfdc-d181-41cd-a87c-dadaf93f95b0", "metadata": {}, "source": [ "**References:**\n", "\n", "- {cite}`Sullivan` Section 3.4, [*Optimization*](https://numericalmethodssullivan.github.io/ch-calculus.html#optimization).\n", "\n", "- {cite}`Sauer` Chapter 13, *Optimization*.\n", "\n", "- {cite}`Chenney-Kincaid` Chapter 13, *Minimization of Functions*.\n", "\n", "- {cite}`Kincaid-Chenney` Chapter 11, *Optimization*." ] }, { "cell_type": "markdown", "id": "a2986cfe-8520-4453-b425-0ace601fafc5", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-1\n", "Describe the golden section search method precisely in pseudocode.\n", "```" ] }, { "cell_type": "markdown", "id": "e5d7c684-f1ea-4f5a-b1b5-4affb23d70f3", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-2\n", "\n", "Implement the Golden Section Search and test it on a few examples, such as\n", "\n", "1. $f(x) = -x e^{-x}$ (whose minimum can be shown to occur at $x=1$)\n", "\n", "2. The [Leonard-Jones potential](https://en.wikipedia.org/wiki/Lennard-Jones_potential) $\\displaystyle f(x) = \\frac{1}{x^{12}} - \\frac{1}{x^6}$.\n", "\n", "The second in particular requires preparatory work finding a suitable initial triplet.\n", "\n", "Note that with a nice smooth \"target function\" $f$ as here, one can get numerical confirmation of the result by checking that $f'(x) \\approx 0$.\n", "\n", "To be careful, that only checks that it is a critical point; the second derivative test can confirm that it is a local minimum.\n", "```" ] }, { "cell_type": "markdown", "id": "82462943-c650-47de-b0ca-1903bd504f2e", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-3\n", "Describe the method of Successive Parabolic Interpolation precisely in pseudocode.\n", "```" ] }, { "cell_type": "markdown", "id": "4bfd5c27-a3d3-41cb-a191-3c8a65876d1a", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-4\n", "Implement the method of Successive Parabolic Interpolation and test it on a few examples, such as those in {ref}`project-optimzation-exercise-2`.\n", "```" ] }, { "cell_type": "markdown", "id": "ae9be30d-2c26-4343-abaa-8258a84ebb66", "metadata": {}, "source": [ "## Minimizing Functions of Several Variables: Steepest Descent (a.k.a. Gradient Search)\n", "\n", "Reference: {ref}`section-multidimensional-optimization`\n", "\n", "The two key ideas here are that:\n", "\n", "- A function $f:\\mathbb{R}^n \\to \\mathbb{R}$ decreases most rapidy from a point $\\mathbf{x_0}$ in the direction opposite its gradient: $-\\nabla f(\\mathbf{x_0})$.\n", "\n", "- We can search for the lowest value in that \"downhill direction\" by using a method for minimzing a function of one variable." ] }, { "cell_type": "markdown", "id": "b38861a2-1d9a-4734-b219-3eb7542ecad5", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "The basic strategy is that, starting at an approximation $\\mathbf{x}^{(k)}$, one looks along the \"downhill ray\" $g_k(t) = \\mathbf{x}^{(k)} - t \\nabla f(\\mathbf{x}^{(k)} )$, $t \\geq 0$,\n", "to find the value $t_k$ of $t$ which minimizes this auxilliary function, giving the improved aproximation\n", "\n", "$$\\mathbf{x}^{(k+1)} = \\mathbf{x}^{(k)} - t_k \\nabla f(\\mathbf{x}^{(k)}).$$\n", "\n", "This minimization can be done by one of the methods in {ref}`section-optimization-1D` such as the {ref}`Golden Section Search `." ] }, { "cell_type": "markdown", "id": "2e32f43a-b4e9-4c54-b7ad-1c1987d5debb", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "Some details need to be addressed, like the fact that in principle one has to search the infinite domain $t \\in [0, \\infty)$ rather than a closed interval like $t \\in [0,T]$.\n", "\n", "Thus some experimentation is needed." ] }, { "cell_type": "markdown", "id": "6249c33a-0c0a-42ab-b404-e9eaf886c72a", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-5\n", "Implement the method of Steepest Descent,\n", "and test it initially on an example like\n", "\n", "$$f_1(x, y) = 2(x-1)^2 + 3(y-2)^2$$\n", "\n", "with an obvious, unique minimum.\n", "```" ] }, { "cell_type": "markdown", "id": "e77934ff-398f-4ebb-b3da-1d15ee8b525c", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-6\n", "\n", "Test the above on some more challenging examples like\n", "\n", "$$ f_2(x, y) = K(y-x^2)^2 + (x-1)^2) $$\n", "\n", "with minimum at $x=y=1$.\n", "\n", "Start with $K = 1$; the try with a larger value like $K = 100$, which makes it harder — a graph might reveal why.\n", "```" ] }, { "cell_type": "markdown", "id": "8014f852-2302-4e2e-9850-d6a9f65c4f5f", "metadata": {}, "source": [ "```{exercise}\n", ":label: project-optimzation-exercise-7\n", "\n", "It can also be interesting to explore a function that has multiple local minima, like\n", "\n", "$$ f_3(x, y) = (1 - \\cos(x-1)) (1 - \\cos(y-1)) $$\n", "```" ] }, { "cell_type": "markdown", "id": "29c17bb6-5d18-47ca-9976-b5f6cd1b1b1e", "metadata": {}, "source": [ "## Observations and Conclusions" ] } ], "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.12.2" } }, "nbformat": 4, "nbformat_minor": 5 }