Описание

Этот репозиторий содержит реализации различных методов оптимизации, включая градиентный спуск, метод золотого сечения, метод Свена и метод ДСК-Пауэлла. Эти алгоритмы позволяют находить минимум функций, используя разные подходы.

Установка

1. Клонируйте репозиторий:

git clone https://github.com/eclipse7723/optimization_methods.git

2. Перейдите в директорию проекта:

cd optimization_methods

3. Установите необходимые зависимости:

pip install -r requirements.txt

Методы оптимизации

1. Метод градиентного спуска (Gradient Descent)

Градиентный спуск — это итеративный метод оптимизации, использующий градиент функции для нахождения её минимума.

• GradientDescent: основной класс для инициализации различных методов градиентного спуска.
  • OptimalGradientDescent: метод оптимального градиентного спуска.
  • ConstGradientDescent: метод постоянного градиентного спуска.
  • BoothGradientDescent: модификация оптимального градиентного спуска с параметром delta.
  • HeavyBallGradientDescent: модификация оптимального градиентного спуска с эффектом "тяжелого шара".
  • LyusternikGradientDescent: модификация, использующая параметр beta для изменения шага.

Параметры

• fn: целевая функция, которую вы хотите минимизировать.
• start_point: начальная точка в виде np.ndarray.
• step: начальный шаг для метода (если не указать, будет выбран оптимальный).

Дополнительные параметры:

• grad: функция градиента (по-умолчанию рассчитывается численно).
• modification: строка, определяющая модификацию градиентного спуска. Возможные значения:
  • booth: модификация Бута.
  • heavy_ball: модификация тяжелого шара.
  • lyusternik: модификация Люстерника.
  • по-умолчанию модификация не используется
• one_dim_method: строка, определяющая одномерный метод для нахождения шага. Возможные значения:
  • golden_section: метод золотого сечения. (по-умолчанию)
  • dsk_powell: метод ДСК-Пауэлла.
• sven_step: значение, определяющее шаг для алгоритма Свена, если не был указан начальный шаг step.
• criteria: 0 для проверки по норме вектора и значения функции, 1 для проверки по норме градиента.
  • 0: ||x_(k+1) - x_k|| / ||x_k|| < criteria_eps AND |f(x_(k+1) - f(x_k)| < criteria_eps
  • 1: ||∇f(x)|| < criteria_eps
• criteria_eps: точность, с которой необходимо остановиться (по умолчанию 10**-3).

Пример использования

Импортируем необходимый код:

from optimization_methods.methods.GradientDescent import GradientDescent
from optimization_methods.utils.utils import gradient
import numpy as np

def fn(x1, x2):
    return (10 * (x1 - x2) ** 2 + (x1 - 1) ** 2) ** 4

start_point = np.array([-1.2, 0.0])
searched_point = np.array([1.0, 1.0])
grad = lambda point: gradient(fn, point, 10 ** -8)

Все примеры будут на основе функции fn, в точке start_point и искомая точка searched_point:

1. Оптимальный спуск

optimizer = GradientDescent(fn, start_point, grad=grad).start()
print(f"result is {optimizer.x}")

2. Постоянный спуск

Тут необходимо просто указать начальный шаг step:

optimizer = GradientDescent(fn, start_point, step=0.1, grad=grad).start()
print(f"result is {optimizer.x}")

3. Использование модификаций

Вы можете использовать различные модификации, указав параметр modification. Например:

• Booth: для использования модификации Booth используйте modification='booth'.
• Heavy Ball: для эффекта тяжелого шара используйте modification='heavy_ball'.
• Lyusternik: для применения метода Люстерника используйте modification='lyusternik'.

2. Метод "Золотое сечение" (Golden Section)

Метод "Золотое сечение" — это одномерный метод оптимизации, который позволяет находить минимум функции на заданном интервале. Ниже приведены инструкции по его использованию и пример.

Параметры

• fn: целевая функция, которую вы хотите минимизировать (должна принимать одно число в качестве аргумента).
• a: левая граница интервала поиска.
• b: правая граница интервала поиска.
• eps: точность, с которой нужно остановиться (по умолчанию 0.001).

Пример использования

Чтобы использовать метод "Золотое сечение", вам нужно создать экземпляр класса GoldenSection, передав ему целевую функцию fn и границы интервала a, b, а также уточнить eps при необходимости.

from optimization_methods.methods.GoldenSection import GoldenSection

def fn(x):  # Определяем целевую функцию
    return (x - 2) ** 2  # Минимум в точке x = 2

# Задаем границы интервала
a = 0  # Левая граница
b = 4  # Правая граница

# Инициализация метода
golden_section = GoldenSection(fn=fn, a=a, b=b, eps=0.001)

# Получение результата
minimum = golden_section.x
minimum_value = fn(minimum)

print(f"Minimum found at: x = {minimum:.6f}, f(x) = {minimum_value:.6f}")

3. Метод "ДСК-Пауэлл" (двухстепенной метод поиска)

Метод "ДСК-Пауэлл" (двухстепенной метод поиска) — это одномерный метод оптимизации, который позволяет находить минимум функции на заданном интервале. Ниже приведены инструкции по его использованию и пример.

Параметры

• fn: целевая функция, которую вы хотите минимизировать (должна принимать одно число в качестве аргумента).
• a: левая граница интервала поиска.
• b: правая граница интервала поиска.
• eps: точность, с которой нужно остановиться (по умолчанию 0.001).

Пример использования

Чтобы использовать метод "ДСК-Пауэлл", вам нужно создать экземпляр класса DSKPowell, передав ему целевую функцию fn и границы интервала a, b, а также уточнить eps при необходимости.

from optimization_methods.methods.DSKPowell import DSKPowell

def fn(x):  # Определяем целевую функцию
    return (x - 3) ** 2  # Минимум в точке x = 3

# Задаем границы интервала
a = 0  # Левая граница
b = 6  # Правая граница

# Инициализация метода
dsk_powell = DSKPowell(fn=objective_function, a=a, b=b, eps=0.001)

# Получение результата
minimum = dsk_powell.x
minimum_value = fn(minimum)

print(f"Minimum found at: x = {minimum:.6f}, f(x) = {minimum_value:.6f}")

4. Алгоритм Свена

Алгоритм Свена предназначен для нахождения интервала неопределенности функции, что является важным этапом в оптимизации. Этот метод помогает определить границы, в которых можно искать минимум функции. Ниже приведены инструкции по его использованию и пример.

Параметры

• fn: целевая функция, которую вы хотите минимизировать.
• start_point: начальная точка в виде np.ndarray.
• step: начальный шаг для метода.

Пример использования

from optimization_methods.methods.Sven import Sven

def fn(x):  # Определяем целевую функцию
    return (x - 4) ** 2  # Минимум в точке x = 4

# Задаем начальную точку и шаг
start_point = 2.0  # Начальная точка
step = 1.0         # Шаг

# Инициализация метода
sven = Sven(fn=fn, start_point=start_point, step=step)

# Получение результата
interval = sven.interval
minimum = sven.x

print(f"Interval found: ({interval[0]:.6f}, {interval[1]:.6f})")
print(f"Best point in the interval: x = {minimum:.6f}")