XVII Международная студенческая научная конференция Студенческий научный форум - 2025

Введение

Методы одномерной оптимизации представляют собой важный класс численных методов, предназначенных для нахождения экстремумов функций одной переменной. Эти методы находят широкое применение в различных областях науки и техники, где необходимо минимизировать или максимизировать функции, связанные с реальными задачами. Одномерная оптимизация, в отличие от многомерной, сосредоточена на поиске оптимальных значений в одномерном пространстве, что значительно упрощает процесс поиска экстремумов и делает его более эффективным с вычислительной точки зрения.

1. Идеи методов

Основная идея методов одномерной оптимизации заключается в том, чтобы исследовать поведение функции в окрестности предполагаемого экстремума, используя различные подходы для нахождения точек, в которых функция достигает своего минимума или максимума. Для этого необходимо определить, каким образом мы будем исследовать функцию, и какие критерии будем использовать для оценки её поведения. К числу таких критериев относятся производные функции, которые позволяют установить, где функция возрастает или убывает, а также различные численные методы, которые помогают находить корни уравнений и экстремумы [8].

Одним из наиболее простых и интуитивно понятных методов одномерной оптимизации является метод перебора. Этот метод заключается в том, что мы последовательно исследуем значения функции на заданном интервале, выбирая точки, в которых функция принимает минимальные или максимальные значения. Хотя метод перебора является наглядным, его эффективность оставляет желать лучшего, особенно если необходимо исследовать функцию на большом интервале или с высокой точностью. В таких случаях более предпочтительными становятся методы, основанные на анализе производных функции [1].

Следующий метод. Метод градиентного спуска является одним из наиболее популярных методов, основанных на производных. Он заключается в том, что мы начинаем с некоторой начальной точки и на каждом шаге перемещаемся в направлении, противоположном градиенту функции. Это позволяет нам постепенно приближаться к точке минимума. Однако метод градиентного спуска имеет свои недостатки, такие как возможность застревания в локальных минимумах и необходимость выбора подходящего шага, что может существенно повлиять на скорость сходимости метода [5].

Третий метод. Метод золотого сечения. Этот метод основан на делении интервала поиска на две части с использованием специального соотношения, называемого золотым сечением. Суть этого метода заключается в том, что мы последовательно сокращаем интервал, в котором ищем минимум, основываясь на значениях функции в определённых точках. Метод золотого сечения является эффективным, так как он позволяет значительно сократить количество необходимых вычислений, особенно при работе с непрерывными функциями.

Метод Фибоначчи также является одним из методов одномерной оптимизации, который использует последовательность Фибоначчи для определения точек, в которых будет производиться оценка функции. Этот метод позволяет эффективно находить экстремумы функции, особенно когда требуется высокая точность.

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

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

В заключение, методы одномерной оптимизации представляют собой мощный инструмент для решения задач, связанных с нахождением экстремумов функций. Разнообразие доступных методов позволяет выбрать наиболее подходящий подход в зависимости от конкретной задачи и свойств исследуемой функции. Важно помнить, что каждый метод имеет свои преимущества и недостатки, и выбор оптимальной стратегии поиска может существенно повлиять на эффективность решения задачи.

Градиентный метод

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

Основные принципы градиентных методов:

Направление антиградиента: градиент функции указывает направление наибольшего роста функции, а его антипод (антиградиент) указывает направление наибольшего убывания. В градиентных методах движение к минимуму происходит именно в направлении антиградиента.

Рис.1. Градиентный метод

Итерационный процесс: на каждой итерации метод вычисляет градиент в текущей точке и делает шаг в направлении антиградиента, перемещаясь к точке с меньшим значением функции.

Шаг: длина шага в направлении антиградиента определяется параметром, называемым шагом или скоростью обучения. Правильный выбор шага критически важен для сходимости метода.

Основные виды градиентных методов:

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

   • Алгоритм:

Инициализация начальной точки x₀.

Повторять до сходимости:

Вычислить градиент ∇f(xₖ) в текущей точке xₖ.

Обновить текущую точку: xₖ₊₁ = xₖ - α * ∇f(xₖ), где α — шаг (скорость обучения).

• Особенности:

Самый простой и базовый градиентный метод.

Требует настройки параметра шага (α).

Сходимость может быть медленной, особенно вблизи минимума или при наличии «плоских участков» на функции.

Чувствителен к выбору начальной точки.

Может застревать в локальных минимумах.

Подходит для задач с большим количеством переменных, где вычисление вторых производных может быть затруднительным.

1. Метод наискорейшего спуска (Steepest Descent):

   1. Алгоритм:

Инициализация начальной точки x₀.

Повторять до сходимости:

Вычислить градиент ∇f(xₖ) в текущей точке xₖ.

Определить оптимальную величину шага αₖ вдоль направления антиградиента (обычно с помощью линейного поиска).

Обновить текущую точку: xₖ₊₁ = xₖ - αₖ * ∇f(xₖ).

1. 1. Особенности:

На каждой итерации выбирается оптимальный шаг в направлении антиградиента.

Сходится быстрее, чем обычный градиентный спуск, особенно при правильном выборе метода линейного поиска.

Более затратен с точки зрения вычислений на итерацию из-за необходимости линейного поиска.

Может «зигзагообразно» двигаться к минимуму при плохой обусловленности задачи.

1. Метод сопряженных градиентов (Conjugate Gradient, CG):

   1. Алгоритм:

Инициализация начальной точки x₀ и начального направления d₀ = -∇f(x₀).

Повторять до сходимости:

Вычислить градиент ∇f(xₖ) в текущей точке xₖ.

Определить оптимальную величину шага αₖ вдоль направления поиска dₖ.

Обновить текущую точку: xₖ₊₁ = xₖ + αₖ * dₖ.

Вычислить новое направление поиска: dₖ₊₁ = -∇f(xₖ₊₁) + βₖ * dₖ, где βₖ — коэффициент, обеспечивающий сопряженность нового направления с предыдущими.

1. 1. Особенности:

Использует сопряжённые (ортогональные) направления поиска, что повышает скорость сходимости.

Эффективен для решения задач с большим количеством переменных.

Требует меньшего количества итераций, чем градиентный спуск.

Подходит для выпуклых и близких к выпуклым задач.

Модифицированные методы градиентного спуска (адаптивные методы):

Эти методы автоматически настраивают шаг обучения (скорость обучения) для каждого параметра в зависимости от истории градиентов. Они более эффективны, чем классический градиентный спуск.

RMSprop (прогнозирование среднеквадратичного отклонения): адаптирует скорость обучения на основе скользящего среднего квадрата градиентов.

AdaGrad (адаптивный градиент): адаптирует скорость обучения на основе суммы квадратов градиентов.

Adam (адаптивная оценка моментов): объединяет идеи RMSprop и AdaGrad, используя скользящие средние как градиентов, так и их квадратов.

Преимущества градиентных методов:

• Простота реализации

• Не требуют вычисления вторых производных

• Эффективны для задач с большим количеством переменных

Недостатки градиентных методов:

• Могут сходиться медленно

• Чувствительны к выбору шага

• Могут застревать в локальных минимумах

Градиентные методы являются важным классом алгоритмов для решения задач безусловной оптимизации. Понимание принципов их работы и особенностей позволяет эффективно применять их на практике. Выбор конкретного градиентного метода зависит от характеристик задачи и требований к скорости и точности решения. Модифицированные градиентные методы (адаптивные) часто являются более предпочтительными из-за их более высокой эффективности и устойчивости.

Метод Ньютона (Newton’s Method)

Использует вторые производные (гессиан) для аппроксимации целевой функции квадратичной функцией в окрестности текущей точки и находит минимум этой аппроксимации. Направление поиска определяется обратным гессианом, умноженным на градиент.

Рис. 2. Метод Ньютона

• Преимущества:

Быстрая сходимость (квадратичная) в окрестности минимума. Не требует линейного поиска при хороших условиях.

• Недостатки:

Вычисление гессиана может быть дорогостоящим и сложным, особенно для многомерных задач. Обратный гессиан может быть плохо обусловлен или не существовать. Может сходиться к максимуму или седловой точке. Требует хорошей начальной точки.

Хорошо подходит для задач с небольшим количеством переменных и хорошо вычисляемым гессианом.

Квазиньютоновские методы (Quasi-Newton Methods):

Аппроксимируют гессиан или обратный гессиан на каждой итерации, используя только первые производные (градиенты).

• Преимущества:

Не требуют вычисления вторых производных, что делает их более экономичными, чем метод Ньютона. Сохраняют хорошую сходимость, приближающуюся к квадратичной в окрестности минимума. Более устойчивы, чем метод Ньютона.

• Недостатки:

Могут сходиться медленнее, чем метод Ньютона, в некоторых случаях. Широко используются в машинном обучении, оптимизации, обработке сигналов.

Краткое сравнение методов

Характеристика	Метод Ньютона	Квазиньютоновские методы
Производные	Первая и вторая	Только первая
Гессиан	Вычисляется явно	Аппроксимируется
Скорость сходимости	Быстрая (квадратичная)	Быстрая (сверхлинейная)
Вычислительные затраты	Высокие	Ниже, чем у метода Ньютона
Устойчивость	Может быть неустойчив	Более устойчивы
Память	Зависит от размерности	Могут использовать ограниченную память
Применение	Малое количество переменных	Широкое применение

Методы одномерной оптимизации являются основой для более сложных алгоритмов и представляют собой важный инструмент в арсенале численных методов. Они позволяют эффективно находить экстремумы функции, заданной на одномерном отрезке. В ходе работы были рассмотрены такие методы, как метод бисекции, метод золотого сечения и метод Фибоначчи. Каждый из этих подходов имеет свои достоинства и недостатки, которые зависят от свойств функции, которую необходимо оптимизировать. Например, метод бисекции прост в реализации и гарантирует сходимость, однако его скорость может быть низкой. Метод золотого сечения, в свою очередь, демонстрирует более высокую скорость сходимости, но требует больше вычислительных затрат. Метод Фибоначчи также эффективен, однако его применение ограничено определенными условиями.

Градиентные методы представляют собой более сложный класс алгоритмов, которые используют информацию о градиенте функции для нахождения ее экстремумов. Эти методы, такие как метод градиентного спуска, являются мощными инструментами для многомерной оптимизации. В ходе исследования было показано, что градиентные методы могут быть очень эффективными, особенно для гладких функций. Однако они также имеют свои ограничения, такие как зависимость от начальной точки и возможность застревания в локальных экстремумах. Кроме того, выбор шага в методе градиентного спуска может существенно повлиять на скорость сходимости. Важно отметить, что для повышения эффективности градиентных методов были разработаны различные модификации, такие как методы с адаптивным шагом и методы, использующие информацию о второй производной.

Методы Ньютона и квазиньютоновские методы представляют собой более сложные подходы, которые используют информацию о второй производной функции. Метод Ньютона, хотя и обладает высокой скоростью сходимости, требует вычисления гессиана, что может быть затруднительно для многомерных функций. Квазиньютоновские методы, такие как метод Бройдена-Флетчера-Гольдфарба-Шанно (BFGS), предлагают компромисс между сложностью и эффективностью. Они позволяют избежать явного вычисления гессиана, используя аппроксимации, что делает их более гибкими и удобными в применении. В рамках работы было продемонстрировано, что квазиньютоновские методы могут значительно улучшить скорость сходимости по сравнению с простыми градиентными методами, особенно в случаях, когда функция имеет сложную структуру.

Заключение

Методы оптимизации с ограничениями представляют собой отдельный класс алгоритмов, которые позволяют находить экстремумы функций при наличии ограничений на переменные. Эти методы, такие как метод Лагранжа и метод штрафов, являются важными инструментами в практических приложениях, где часто возникают ограничения на ресурсы или другие параметры. В ходе работы было показано, что методы оптимизации с ограничениями могут быть значительно более сложными в реализации, чем безусловные методы, однако они позволяют решать более широкий класс задач. Важно отметить, что выбор метода оптимизации с ограничениями должен основываться на конкретных условиях задачи, поскольку разные методы могут давать разные результаты в зависимости от структуры ограничений.

Сравнительный анализ численных методов оптимизации, проведенный в рамках работы, позволил выявить их сильные и слабые стороны. Например, методы одномерной оптимизации являются простыми и понятными, но ограничены в применении. Градиентные методы, хотя и более сложные, могут быть эффективными для гладких функций, но требуют тщательной настройки параметров. Методы Ньютона и квазиньютоновские методы предлагают высокую скорость сходимости, однако их применение может быть затруднено из-за необходимости вычисления производных. Методы оптимизации с ограничениями, в свою очередь, открывают новые возможности для решения задач, но могут быть более сложными в реализации.

Список литературы

1. Вадутов О. С. Синтез ПИД-регулятора в системах с запаздыванием методом условной оптимизации с ограничениями на размещение полюсов // Известия Томского политехнического университета. Инжиниринг георесурсов. – 2014. – Т. 325. – №. 5. – С. 16-22.

2. Войтишек А. В. Разработка и оптимизация рандомизированных функциональных численных методов решения практически значимых интегральных уравнений Фредгольма второго рода // Сибирский журнал индустриальной математики. – 2018. – Т. 21. – №. 2. – С. 32-45.

3. Гасников А. В., Двуреченский П. Е., Нестеров Ю. Е. Стохастические градиентные методы с неточным оракулом // Труды Московского физико-технического института. – 2016. – Т. 8. – №. 1 (29). – С. 41-91.

4. Гилл Ф., Мюррэй У., Лебедев В. Ю. Численные методы условной оптимизации. – 1977.

5. Гусев В. Б. Метод безусловной оптимизации для задачи с нестационарной целевой функцией, заданной на дискретной шкале времени // Проблемы управления. – 2021. – №. 1. – С. 36-42.

6. Рыжикова Е. Г. Разработка, обоснование и тестирование подхода к применению альфа-бета отсечения в численных методах оптимизации // ПерсПективы науки. – 2019. – С. 34.

7. Кольцов Ю. В., Бобошко Е. В. Сравнительный анализ методов оптимизации для решения задачи интервальной оценки потерь электроэнергии // Компьютерные исследования и моделирование. – 2013. – Т. 5. – №. 2. – С. 231-239.

8. Крутиков В. Н. и др. Численные методы безусловной оптимизации с итеративным обучением и их применение. – 2005.

Код для цитирования: Скопировать