Skip to content

Latest commit

 

History

History
217 lines (151 loc) · 10.7 KB

README.md

File metadata and controls

217 lines (151 loc) · 10.7 KB
Raw

Описание

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

Установка

  1. Клонируйте репозиторий:
git clone https://github.com/eclipse7723/optimization_methods.git
  1. Перейдите в директорию проекта:
cd optimization_methods
  1. Установите необходимые зависимости:
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: строка, определяющая одномерный метод для нахождения шага. Возможные значения:
  • 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:

math function

  1. Оптимальный спуск
optimizer = GradientDescent(fn, start_point, grad=grad).start()
print(f"result is {optimizer.x}")
  1. Постоянный спуск

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

optimizer = GradientDescent(fn, start_point, step=0.1, grad=grad).start()
print(f"result is {optimizer.x}")
  1. Использование модификаций

Вы можете использовать различные модификации, указав параметр 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}")