ORIGINAL BOOK: M. M. Hammad, M. M. Yahia, Mathematics for Machine Learning and Data Science: Optimization with Mathematica Applications, arXiv:2302.05964. https://doi.org/10.48550/arXiv.2302.05964
RESEARCHGATE
RESEARCHGATE
Book Abstract: The field of optimization has gotten a lot of interest in recent years owing to significant advances in computer technology. Numerous issues in machine learning, economics, finance, geophysics, molecular modeling, computational systems biology, operations research, and all areas of engineering are now being resolved owing to the rapid growth of optimization methods and algorithms. This monograph presents the main theorems in linear algebra, convex sets, convex functions, single variable optimization, multivariable optimization, and their corresponding algorithms. We also briefly touch upon the constrained nonlinear optimization. We have found the Wolfram language to be ideal for specifying algorithms in human readable form. To minimize nonlinear objective functions, we have created 27 Mathematica functions that follow the principles of 18 algorithms. The code examples were carefully designed to demonstrate the purpose of given algorithm. The code for each algorithm will run as is with no code from prior algorithms or third parties required beyond the installation of Mathematica.
ContentsPreface iAbstract iiCHAPTER 1 MATHEMATICA NOTEBOOKS 1.1 Mathematica Notebooks, Palettes, Packages, and Help 1.2 Basic Concepts 1.3 Elementary Functions 1.4 Variables and Functions 1.5 Lists 1.6 2D and 3D Graphing 1.7 Manipulate 1.8 Control Structure 1.9 Modules, Blocks, and Local Variables 1.10 Requesting Input and Choice Dialog CHAPTER 2 MATRIX NOTATIONS, DECOMPOSITION, AND CALCULUS 2.1 Vectors and Matrices with Dirac Notations 2.2 Vectors and Matrices with Index Notations 2.3 Matrix Decomposition 2.4 Basics of Matrix Calculus 2.5 Numerical Differentiation and Finite Difference Methods 2.6 Mathematica Built-in Functions CHAPTER 3 LINEAR ALGEBRA – THE INCREDIBLE BEAUTY OF MATH3.1 Vector Spaces 3.2 Inner Product 3.3 Subspace 3.4 Linear Operator, Linear Transformation, and Matrix Representation 3.5 Eigenvalues, Eigenvectors and Eigenspaces 3.6 The Four Fundamental Subspaces of a Matrix 3.7 Symmetric Matrices and Orthogonal Diagonalization 3.8 Singular Values and Singular Vectors in the Singular Value Decomposition (SVD) 3.9 Quadratic Form and Definite Matrix in R^n 3.10 Mathematica Built-in Functions CHAPTER 4 CONVEX STES AND CONVEX FUNCTIONS 4.1 p-norm in finite dimensions 4.2 Hyperplanes, Hyperspheres and Hyperellipsoid 4.2.1 Lines, Planes, Hyperplanes, and Half-Spaces in R^n 4.2.2 Circle, Spheres, Hyperspheres, and Balls in R^n 4.2.3 Ellipse, Ellipsoid, and Hyper-Ellipsoid in R^n 4.3 Convex sets 4.4 Convex Hull 4.5 Convex Cone 4.6 Convex Functions 4.7 General Case (Multi-Variable Function) and Sub-gradient of Convex Functions 4.8 Mathematica Built-in Functions CHAPTER 5 SINGLE-VARIABLE OPTIMIZATION WITHOUT CONSTRAINTS 5.1 Single-variable Functions 5.2 Optimization Problem and Algorithms 5.3 Bracketing Methods 5.3.1 Exhaustive Search Method 5.3.2 Bounding Phase Method 5.4 Region-Elimination Methods 5.4.1 Interval Halving Method 5.4.2 Fibonacci Search Method 5.4.3 Golden Section Search Method 5.5 Successive Quadratic Estimation Method (Powell Method) 5.6 Gradient-based Methods 5.6.1 Newton-Raphson Method 5.6.2 Bisection Method (Bolzano search) 5.6.3 Secant Method 5.7 Cubic Search Method 5.8 Mathematica Built-in Functions CHAPTER 6 MULTIVARIABLE UNCONSTRAINED OPTIMIZATION 6.1 Level Curves and Local Linearization of the Two-Variable Functions 6.2 The Directional Derivative of Two-Variable Function 6.3 The Gradient and Tangent Planes of Functions of Two- and Three-Variables 6.4 Optimality Criteria (General Case n-Variables) 6.5 Mathematica Built-in Functions CHAPTER 7 MULTI-VARIABLE DIRECT-SEARCH ALGORITHMS 7.1 Introduction 7.2 Artificial Landscapes 7.3 Unidirectional Search 7.4 Direct Search Methods 7.4.1 Box Evolutionary Method 7.4.2 Simplex Search Method (Nelder–Mead Simplex Method) 7.4.3 Hooke-Jeeves Pattern Search Method 7.4.4 Powell Conjugate Direction Method 7.4.5 Cyclic Coordinate Search CHAPTER 8 MULTI-VARIABLE GRADIENT- and HESSIAN-BASED ALGORITHMS 8.1 First-Order Approximations Methods (Gradient-Based Methods)8.1.1. Cauchy Method (Steepest Descent Method) 8.1.2. Steepest Descent Without Line Search (Formula 1) 8.1.3. Steepest Descent Without Line Search (Formula 2) 8.1.4. Steepest Descent Without Line Search (Formula 3: Barzilai–Borwein Two-Point Formulas) 8.1.5. Momentum 8.1.6. Nesterov Momentum 8.2 Second-order Approximations Methods (Hessian-Based Methods) 8.2.1. Newton Method 8.2.2. Marquardt Method and Modification of the Hessian 8.2.3. Gauss-Newton Method CHAPTER 9 MULTI-VARIABLE CONJUGATE-DIRECTION AND QUASI-NEWTON ALGORITHMS 9.1 Conjugate Direction Method 9.2 Conjugate Gradient Method 9.2.1. Convergence Analysis of Conjugate Gradient method 9.3 Method of Conjugate for General Functions 9.3.1. The Hestenes-Stiefel Formula 9.3.2. The Polak-Ribiere Formula 9.3.3. The Fletcher-Reeves Formula 9.4 The Basic Quasi-Newton Approach 9.4.1. Approximating the Inverse Hessian (Computation of S_k) 9.4.2. Convergence Analysis of quasi-Newton algorithms for quadratic problem 9.5 The Rank One Correction Formula 9.5.1. Convergence Analysis of Rank One Correction Formula 9.6 The Rank Two Correction Formula 9.6.1. The DFP Method 9.6.2. The BFGS Method 9.7 Other Families of Quasi-Newton Algorithms 9.7.1. The Huang Family 9.7.2. Hoshino Method 9.7.3. The Broyden Family CHAPTER 10 MULTI-VARIABLE CONSTRAINED OPTIMIZATION 10.1 Constrained Optimization Problems 10.2 Direct Substitution Method 10.3 Lagrange Multipliers Illustration 10.3.1. Optimizing a Function of Three Variables Subject to One Constraint 10.3.2. Optimizing a Function Subject to Two Constraints 10.4 Non-Degenerate Constraint Qualification 10.5 Tangent and Normal Spaces 10.6 First-Order Necessary Conditions 10.7 Second-Order Necessary and Sufficient Conditions 10.8 Active and Inactive Inequality Constraints 10.9 The Transformation to Equality Constraints 10.10 Karush-Kuhn-Tucker Condition 10.11 Second-Order Conditions 10.12 Mathematica Built-in Functions
CHAPTER 7: MULTI-VARIABLE DIRECT-SEARCH ALGORITHMS
Introduction
Introduction
In optimization, where the goal is to find the best solution to a given problem, direct-search methods stand as essential tools. Unlike methods that require derivative information, direct-search techniques navigate the solution space through exploration and evaluation of potential solutions. This chapter delves into five distinctive direct-search methods, each offering a unique approach to solving optimization problems. These methods include the Box Evolutionary Method, the Simplex Search Method, the Hooke-Jeeves Pattern Search Method, the Powell Conjugate Direction Method, and the Cyclic Coordinate Search.
Each of these methods has its strengths and weaknesses and may perform differently depending on the specific problem at hand. The choice of method depends on the problem’s characteristics, such as the number of variables, presence of constraints, smoothness of the objective function, and other factors.
Each of these methods has its strengths and weaknesses and may perform differently depending on the specific problem at hand. The choice of method depends on the problem’s characteristics, such as the number of variables, presence of constraints, smoothness of the objective function, and other factors.
Artificial Landscapes
Artificial Landscapes
The test functions, known as artificial landscapes, are useful for evaluating characteristics of optimization algorithms, such as convergence rate, precision, robustness, and general performance.
Contour plots of some test functions:
Sphere function
Sphere function
Rosenbrock function
Rosenbrock function
Beale function
Beale function
Booth function
Booth function
Matyas function
Matyas function
Himmelblau’ s function
Himmelblau’ s function
Three - hump camel function
Three - hump camel function
Styblinski–Tang function
Styblinski–Tang function
Unidirectional Search
Unidirectional Search
One of the very basic search techniques for multi-variable optimization is a unidirectional search method. The idea of this method is to convert the multi-variable function to a single variable and then investigate the optimum. Many multi-variable optimization techniques use successive unidirectional search techniques to find the minimum point along a particular search direction. Since unidirectional searches will be mentioned in the different algorithms, we illustrate here how a unidirectional search can be performed on a multi-variable function. (for more mathematical details, see page 247)
Definition of the unidirectionalsearch function
This function start by bracketing the minimum (using Bounding Phase Method) then isolating the minimum (using Golden Section Search Method)
Direct Search Methods
Direct Search Methods
In this section, we present a few minimization algorithms that use function values only. Direct methods are also called zero-order, black box, pattern search, or derivative-free methods. We assume here that f(x) is continuous, and ∇f(x) may or may not exist but certainly is not available. Also, we assume that f(x) has a single minimum in the domain of interest.
In a single-variable function optimization, there are only two search directions in a point that can be modified—either in the positive x-direction or the negative x-direction. The extent of increment or decrement in each direction depends on the current point and the objective function. In multi-variable optimization, each variable can be modified either in the positive or in the negative direction, thereby totaling 2^N different ways, where N is the number of variables. Typically, the domain of the performance index (variables) will be subdivided into a grid of points, and then various strategies for shrinking the area in which the solution lay will be applied. Often this led to nearly exhaustive enumeration and hence proved unsatisfactory for all problems. The more useful idea was to pick a base point and, rather than attempting to cover the entire range of the variables, evaluate the performance index in some pattern about the base point.
In a single-variable function optimization, there are only two search directions in a point that can be modified—either in the positive x-direction or the negative x-direction. The extent of increment or decrement in each direction depends on the current point and the objective function. In multi-variable optimization, each variable can be modified either in the positive or in the negative direction, thereby totaling 2^N different ways, where N is the number of variables. Typically, the domain of the performance index (variables) will be subdivided into a grid of points, and then various strategies for shrinking the area in which the solution lay will be applied. Often this led to nearly exhaustive enumeration and hence proved unsatisfactory for all problems. The more useful idea was to pick a base point and, rather than attempting to cover the entire range of the variables, evaluate the performance index in some pattern about the base point.
Box Evolutionary Method
Box Evolutionary Method
The basic idea of this method is to construct a N-dimensional hypercube (called a factorial design pattern) where the center point is the current point. The Box algorithm requires (2^N+1) points, of which 2^N are corner points of an N-dimensional hypercube centered on the other point. For all 2^N+1 points, function values are obtained and compared. Then, the best point is identified. In the next iteration, another hypercube is formed around this best point. If at any iteration, an improved point is not found, the size of the hypercube is reduced. This process continues until the hypercube becomes very small. (for more mathematical details, see page 276)
Notations:
x0 :Intial vector
deltai :Size reduction parameter delta
epsilon :Small number to check the accuracy of the box method
f [x,y] :Objective function
xbar[k] :Final design solution of iteration k
f[xbar[k]] :Final objective function value of iteration k
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={5,5}
deltai={1,1}
epsilon=0.1
f[{x,y}]=x^2+y^2
domainx={-6,6}
domainy={-6,6}
Notations:
x0 :Intial vector
deltai :Size reduction parameter delta
epsilon :Small number to check the accuracy of the box method
f [x,y] :Objective function
xbar[k] :Final design solution of iteration k
f[xbar[k]] :Final objective function value of iteration k
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={5,5}
deltai={1,1}
epsilon=0.1
f[{x,y}]=x^2+y^2
domainx={-6,6}
domainy={-6,6}
Taking Initial Inputs from User
Taking the Function from User
Starting the algorithm
Final Result
Results of Each Iteration
Data visualization
Domain of Varibles
3 D + Contour Plot
Contour Plot with Step Iterations
Data Manipulation
Mathematica built in function
Simplex (Nelder and Mead ) Search Method
Simplex (Nelder and Mead ) Search Method
In the box search method, the number of evaluations, even for problems of modest dimension, rapidly becomes overwhelming. Hence, more efficient methods must be investigated if we are to use these direct-search methods on problems of reasonable size. In the simplex search method, the number of points in the initial simplex is much less compared to that in Box evolutionary optimization method. This reduces the number of function evaluations required in each iteration. With N variables, only (N+1) points are used in the initial simplex.
In N dimensions, a regular simplex is a polyhedron composed of N+1 equidistant points, which form its vertices. For example, an equilateral triangle is a simplex in two dimensions; a tetrahedron is a simplex in three dimensions. The main property of a simplex employed by their algorithm is that a new simplex can be generated on any face of the old one by projecting any chosen vertex a suitable distance through the centroid of the remaining vertices of the old simplex. The new simplex is then formed by replacing the old vertex with the newly generated projected point. In this way, each new simplex is generated with a single evaluation of the objective.
Hence, the method begins by setting up a regular simplex in the space of the independent variables and evaluating the function at each vertex. At each iteration, the worst point in the simplex is found first. Then, a new simplex is formed from the old simplex by some fixed rules that steer the search away from the worst point in the simplex. The extent of steering depends on the relative function values of the simplex. (for more mathematical details, see page 281)
In N dimensions, a regular simplex is a polyhedron composed of N+1 equidistant points, which form its vertices. For example, an equilateral triangle is a simplex in two dimensions; a tetrahedron is a simplex in three dimensions. The main property of a simplex employed by their algorithm is that a new simplex can be generated on any face of the old one by projecting any chosen vertex a suitable distance through the centroid of the remaining vertices of the old simplex. The new simplex is then formed by replacing the old vertex with the newly generated projected point. In this way, each new simplex is generated with a single evaluation of the objective.
Hence, the method begins by setting up a regular simplex in the space of the independent variables and evaluating the function at each vertex. At each iteration, the worst point in the simplex is found first. Then, a new simplex is formed from the old simplex by some fixed rules that steer the search away from the worst point in the simplex. The extent of steering depends on the relative function values of the simplex. (for more mathematical details, see page 281)
Notations:
x0 :Intial vector
delta :Size reduction parameter delta
epsilon :Small number to check the accuracy of the simplex (Nelder and Mead ) search method
f [x,y] :Objective function
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={4,3}
epsilon=0.1
f[{x,y}]=(x^2+y-11)^2+(x+y^2-7)^2
domainx={-5,5}
domainy={-5,5}
x0 :Intial vector
delta :Size reduction parameter delta
epsilon :Small number to check the accuracy of the simplex (Nelder and Mead ) search method
f [x,y] :Objective function
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={4,3}
epsilon=0.1
f[{x,y}]=(x^2+y-11)^2+(x+y^2-7)^2
domainx={-5,5}
domainy={-5,5}
Taking Initial Inputs from User
Taking the Function from User
Starting the Algorithm
Final Result
Results of Each Iteration
Data Visualization
Domain of Varibles
3D + Contour Plot
Contour Plot with Step Iterations
Data Manipulation
Mathematica built in function
Hooke-Jeeves Pattern Search Method
Hooke-Jeeves Pattern Search Method
Notations:
x0 :Intial vector
deltai :Size reduction parameter delta
epsilon :Small number to check the accuracy of the Hooke-Jeeves Pattern Search Method
f [x,y] :Objective function
α :The factor α of pattern move: (α=2)
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={5,5}
deltai={1,1}
epsilon=0.01
α=2
f[{x,y}]=(x+2y-7)^2+(2x+y-5)^2
domainx={-6,6}
domainy={-6,6}
x0 :Intial vector
deltai :Size reduction parameter delta
epsilon :Small number to check the accuracy of the Hooke-Jeeves Pattern Search Method
f [x,y] :Objective function
α :The factor α of pattern move: (α=2)
lii :The last iteration index
result[k] :The results of iteration k
Example for Input:
x0={5,5}
deltai={1,1}
epsilon=0.01
α=2
f[{x,y}]=(x+2y-7)^2+(2x+y-5)^2
domainx={-6,6}
domainy={-6,6}
Taking Initial Inputs from User
Taking the Function from User
Definition of Exploratory Search Function
Starting the Main Algorithm
Final Result
Results of Each Iteration
Data Visualization
Domain of Varibles
3D+ Contour Plot
Contour Plot with Step Iterations
Data Manipulation
Mathematica built in function
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Mathematics for Machine Learning and Data Science: Optimization with Mathematica Applications
by Mohamed Hammad and Mohamed Yahia
Wolfram Community, STAFF PICKS, August 25, 2023
https://community.wolfram.com/groups/-/m/t/2998780
by Mohamed Hammad and Mohamed Yahia
Wolfram Community, STAFF PICKS, August 25, 2023
https://community.wolfram.com/groups/-/m/t/2998780