shkalikovoleh/optalg

Reimplementation of optimization algorithms.

OptAlg

Set of optimization algorithms.

Usage

from optalg.<subpackage> import <algo-name>

def f(x):
  return <your-function value>(where argument x_i = x[i])

optimizer = <algo-name>(params...)
res = optimizer.optimize(f, [init_state]) #optimization result

For methods requiring gradient and hessian calculations, use autograd.numpy instead of numpy for define objective function. For example:

import numpy as np
from autograd.numpy import sin
from optalg.line_search import ArmijoBacktracking
from optalg.unconstrained.descent import GradientDescent
from optalg.stop_criteria import GradientNormCriterion


def f(x):
  return x[0]**2 + sin(x[1]**2)


gnCriterion = GradientNormCriterion(10**-3)
step_opt = ArmijoBacktracking(1, 0.5)
optimizer = GradientDescent(gnCriterion, step_opt)

res = optimizer.optimize(f, np.array([-3, 1]))
res.x #optimum

Unconstrained algorithms

Gradient free

Methods that does not require differentiability of the objective function. For direction calculation uses another search methods.

• Nelder-Mead - simplex reflection, contraction, expansion and shrink to the minimum of the objective function.
• Hooke-Jeeves - pattern search. Descent direction is the best combination of coordinates of the pertubation vector.

Gradient

Methods based on descent to minimum by gradient-like direction.

• Gradient descent - simple gradient descent

• Cojugate gradients descent - descent direction is the sum of gradient in current point and the weighted direction from the previous iteration. Avaliable variations:

  • Fletcher-Reeves
  • Polak-Ribiere
  • Hestenes-Stiefel
  • Dai-Yuan

Newton

Second-order descent algorithms

• Newton - descent direction is dot product of the hessian and gradient.

• Quasi Newton - inverse hessian replaces with an approximate value

  • BFGS - Broyden-Fletcher-Goldfarb-Shanno
  • DFP - Davidon-Fletcher-Powell
  • SR1 - Symmetric Rank 1 method
  • Broyden - Broyden's method

Evolutional

Methods based on natural evolution. On each iteration methods select "best" individual from population, reproduce new generation and replace previous individuals.

Immune

Artificial immune system

• ClonAlg - clonal selection algorithm

Constrained algorithms

Penalty

Set of method for constrained optimization that use penalty function for representing constraints

• Penalty - penalty function for external point
• Interior - barrier function for interior point
• Augmented Lagragian - modified Lagrangian + inequality constraints

Line search

On each step descent direction multiplies by step size. Avaliable descent's step size calculation methods:

• FixedStep - constant step size
• ArmijoBacktracking - step dividing if the function value at the new point does not satisfy armijo condition.
• BisectionWolfe - bisection method that either computes a step size satisfying the weak Wolfe conditions or sends the function values to -inf.

optalg's Issues

Fibonacci algorithm is broken

Add Pattern search method (Hooke-Jeeves)

Add ability to change the starting position

Add ability for gradient methods to change the x0 value(starting position) for gradient descent from the other point with same another parameters.

Add Golden ratio iterative algo

Can not get empty history

If we call get_last_history() for gradient descent methods, that have empty history, we catch an error.

Add ClonAlg

Add immune ClonAlg optimization method.

1. Create immune subpackage(folder and init)
2. Add base immune class(if you can select general parameters). This class must inherit OptimizerWithHistory.
3. Add CloneAlg implementation
4. Check history correctness
5. Add unittests(in tests/immune).

For run test use
python3 -m unittest discover from main directory.

Add different step selection for conjugate gradients

Add step formula named after their developers:

1. Fletcher–Reeves(now implemented)
2. Polak–Ribière
3. Hestenes-Stiefel
4. Dai–Yuan

Add penalty method

Add constrained optimization method that on each iteration minimize with unconstrained optimization objective function plus some penalty which represent constarints.
Variations:

• Internal point
• External point

Add Fibonacci/Modified Fibonacci iterative algo

Add Lagrange method

Add modified Lagrange method that can optimize function with equality and inequality constraints.
Literature:

• Пантелеев Методы оптимизации стр. 275

Add quasi newton optimization methods

Add method that use inverse hessian approximation.

1. Broyden
2. DFP
3. SR1
4. BFGS

Add simple minimum search

Add search argmin from n values in selected bounds for one-argument function.

Add Newton optimization method

Add newton optimization method, that use inverse hessian matrix for descent direction calculation.

Add Nelder-Mead method

Add Nelder-Mead optimization method.
Please place your implementation in a optalg.simplex subpackage.

Add Gradient Descent Fastest

Add gradient descent with step determine by other optimizer

Fix stop criteria argument

In GD with step decrease and fastest stop criteria previous point argument is incorrect because last element in history is current point. We must use -2 index for select previous point for correct stop criteria work.

Add conjugate directions descent

Add decent by conjugate directions(sum of gradient in the current point and weighed gradient in the previous point)

Add gradient descent with step decrease

Add gradient descent algorithm with step decrease via divide learning rate into fixed value if function value in new point greater than in previous point.

Add Genetic algorithm

• Add classic genetic algorithm.
• Move immune package in genetic and create base classes.

Add PSO

Add particle swarm optimization algorithm(with abstractions).
Wiki