Optimization-Algorithms

A repository of optimization algorithms implemented in Python & MATLAB for mathematical optimization problems.

Global search algorithms:

Global search algorithms are a type of optimization algorithm used to find the global optimum of a problem. One example of such an algorithm is Particle Swarm Optimization (PSO).

• PSO is a population-based optimization algorithm inspired by the social behavior of birds flocking or fish schooling. In PSO, a group of particles, each representing a candidate solution, move through a multidimensional search space in search of the global optimum. Each particle's movement is influenced by its own position and velocity, as well as the best position and velocity of the particles in the swarm. PSO can be used for both continuous and discrete optimization problems, and is relatively simple to implement and efficient.

• Genetic Algorithm (GA) is a population-based optimization algorithm inspired by the process of natural selection and evolution. In GA, a population of candidate solutions, represented as chromosomes, is iteratively evolved through a process of selection, crossover, and mutation to find the global optimum. Each chromosome represents a potential solution to the problem, and its fitness is evaluated based on a fitness function. GA can handle both continuous and discrete optimization problems, and is particularly useful when the search space is large and complex.

PSO and GA are both powerful global search algorithms that can be used for a variety of optimization problems. PSO is typically faster than GA and has fewer parameters to tune, making it a good choice for problems with smooth and continuous search spaces. GA, on the other hand, is more robust and can handle a wider range of problem types, including those with discrete and nonlinear search spaces. Ultimately, the choice between PSO and GA depends on the nature of the problem and the performance criteria.

Linear Programming:

Linear programming is a mathematical optimization technique used to find the optimal solution to a linear objective function subject to linear constraints. It is used in various real-world applications like supply chain management, financial planning, transportation planning, and resource allocation. The objective function and constraints are represented as linear equations or inequalities, and solving a linear programming problem requires standardizing the objective function and constraints. The simplex method and interior-point methods are popular ways to solve linear programming problems. However, linear programming has limitations, including the requirement for linear objective functions and constraints. Nonlinear programming techniques, such as nonlinear programming and integer programming, are used for problems with nonlinear constraints or nonlinear objective functions.

Unconstrained Optimization:

• Conjugate direction methods are optimization algorithms used to solve unconstrained optimization problems. These methods choose a search direction that is conjugate to the previous direction. The conjugate gradient method and the Fletcher-Reeves method are popular conjugate direction methods. These methods are particularly useful for optimizing quadratic functions but may not be well-suited for nonlinear optimization problems.

• Newton's Method is an iterative algorithm that uses the second derivative of a function to update the current estimate of the minimum or maximum. Specifically, at each iteration, Newton's Method updates the estimate by taking a step in the direction of the minimum or maximum of the quadratic approximation of the function at the current estimate. This approach allows for rapid convergence, but it can be sensitive to the initial guess and may not work well for functions with multiple local minima or maxima.

• Steepest Descent Method is another iterative algorithm used to find the minimum or maximum of a function. Unlike Newton's Method, Steepest Descent Method does not require knowledge of the second derivative of the function. Instead, it takes steps in the direction of the steepest descent or ascent of the function at the current estimate. This approach may take longer to converge than Newton's Method, but it can handle functions with multiple local minima or maxima and is less sensitive to the initial guess.

• Golden section search is an algorithm for one-dimensional optimization, used for identifying the minimum or maximum of a function. It involves dividing an interval into two sub-intervals, using the golden ratio to choose the splitting point, and selecting the sub-interval containing the extremum. While the algorithm has some benefits over other one-dimensional optimization algorithms, it may be slow to converge under certain conditions.

• Quasi-Newton methods are a class of optimization algorithms that approximate the inverse Hessian matrix of the objective function to find the minimum or maximum of a function. The Hessian matrix represents the second-order partial derivatives of the function and provides information about the curvature of the function. Quasi-Newton methods use an approximation of the Hessian matrix, which is updated at each iteration of the algorithm, to improve the search direction towards the optimal solution. The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and the Davidon-Fletcher-Powell (DFP) method are two well-known quasi-Newton methods.

  • The BFGS method is more commonly used than the DFP method because it is more robust and easier to implement. The BFGS method updates the approximation of the inverse Hessian matrix using a formula that takes into account the change in the gradient of the objective function between iterations. The algorithm converges quickly to the optimal solution and is effective for both convex and non-convex optimization problems.

  • Quasi-Newton methods are preferred over Newton's method because they do not require the computation of the exact Hessian matrix, which can be expensive and difficult to compute for high-dimensional problems. Quasi-Newton methods are also preferred over gradient descent methods because they are more effective at finding the optimal solution and can converge faster.