Оптимизация — это задача поиска наилучшего решения в заданном множестве допустимых вариантов. Она является центральной во многих областях науки, техники и экономики. В различных приложениях, начиная от проектирования самолетов и заканчивая оптимизацией алгоритмов машинного обучения, требуется найти оптимальные значения параметров, чтобы минимизировать затраты, максимизировать эффективность или улучшить производительность [1–4].
Существуют аналитические методы оптимизации, которые позволяют получить точное решение при определенных условиях. Однако в большинстве практических задач приходится сталкиваться со сложными функциями, которые не поддаются аналитическому решению. В таких случаях на помощь приходят численные методы оптимизации, которые позволяют найти приближенное, но приемлемое решение.
В данной статье рассмотрим три наиболее широко используемых метода оптимизации: метод сопряженных градиентов, метод Ньютона и ДФП-метод и пошаговый алгоритм реализации для каждого из данных методов. В первую очередь эти методы различаются своей эффективностью, сходимостью. В статье представлен каждый из них, а также реализация в САПР MATLAB.
Для того чтобы сравнить 3 предложенных метода между собой, рассмотрим одинаковую задачу для каждого из методов: найти минимум функции
из исходной точки x0 [1;1] с заданной точностью E = 10–5. График функции, вместе с ее точкой минимума, приведен на рис. 1.
Метод сопряженных градиентов — метод нахождения локального экстремума функции на основе информации о ее значениях и ее градиенте. В случае квадратичной функции в Rn минимум находится не более чем за n шагов [5].
Алгоритм действий для метода сопряженных градиентов будет выглядеть следующим образом:
1) находим антиградиент w с исходной функции (w = –[df (x)/dx1; df (x)/dx2]). Также для первого шага направление спуска p = w (далее переопределим значение);
2) решая задачу одномерной минимизации функции fi (kappa) = f (Xk-1 + kappak*pk) по каждой из координат с помощью метода золотого сечения*, определяем шаг спуска kappa (=xmin);