ОПТИМИЗАЦИИ МЕТОДЫ численные

— методы построения алгоритмов, позволяющих отыскивать минимальное (максимальное) значение функции элемент некоторого пространства Е) и точку в которой это значение реализуется. Область определения ф-ции может либо совпадать со всем пространством Е, либо же ограничиваться определен, условиями , где Q — некоторое мн-во из Е. В соответствии с этим рассматриваются либо задачи оптимизации без ограничений (отыскание безусловного экстремума), либо задачи с ограничениями (задачи на условный экстремум). Если в допустимой области Q изменения аргумента х имеется несколько точек, реализующих локальные минимумы ф-ции , то можно рассматривать две задачи оптимизации: отыскание локального (относительного) минимума и отыскание глобального (абсолютного) минимума. О. используемые для решения различных оптимизационных задач, во многом зависят от свойств минимизируемой ф-ции — непрерывности, выпуклости и т. д.

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

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

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

Градиентный метод — исторически первый О. м. Впервые был использован в работах франц. математика Коши (1789--1857). В этом методе в формуле (1) вектор величина параметра в различных вариантах метода выбирается различными способами: а) на всех итерациях полагается — некоторая константа, зависящая от свойств ф-ции выбирается из условия

в) начиная с некоторого значения параметра, проверяется выполнение неравенства

где если при выбранном значении а это неравенство не удовлетворяется, производится дробление параметра до тех пор, пока неравенство выполнится, и полученное значение принимается за искомое. Если ф-ция дважды дифференцируема и выполняются условия

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

В обобщенном методе Ньютона выбирается, как и в пунктах б) и в) градиентного метода, причем в последнем случае в качестве начального значения а, начиная с которого проверяется неравенство, берется 1. При выполнении условия (2) метод Ньютона сходится к решению с любого начального приближения со сверхлинейной скоростью

при всех при к . Если существуют ограниченные третьи производные ф-ции если вторые производные удовлетворяют условию Липшица), метод Ньютона сходится к решению с квадратичной скоростью:

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

когда минимизируется квадратичная ф-ция векторы оказываются сопряженными: Приведем некоторые ф-лы для построения

Здесь в качестве берется произвольная положительно определенная матрица. Методы сопряженных направлений позволяют отыскивать минимум квадратичной ф-ции не более чем за шагов. При минимизации неквадратичных ф-ций эти методы сопряженных направлений обычно реализуются с восстановлением матрицы через конечное число шагов , т. е. полагается Такие варианты методов сопряженных направлений при выполнении условия (2) сходятся к решению со сверхлинейной скоростью. Можно использовать методы сопряженных направлений и для решения задач в гильбертовом пространстве; при этом, если выполняется условие (2), скорость сходимости методов линейная. Если то для отыскания безусловного экстремума можно пользоваться методами двойственных направлений, в которых при условии при условии выбирается так, как и в методе . Матрица где произвольная система линейно независимых векторов, таких, что при базис, двойственный (биортогональный) к базису Начальные итерации процесса можно осуществлять, как и в градиентном методе. Построение базиса двойственного к базису ществляется по ф-лам

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

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

во втором — точка является точкой минимума квадратичной ф-ции 1

на мн-ве Q. Выбор в обоих методах производится, как в пунктах б) или в) градиентного метода с учетом ограничений При определенных условиях метод условного градиента сходится с линейной скоростью; метод Ньютона при выполнении условия (2) на мн-ве Q сходится со сверхлинейной скоростью. Если требуется найти минимум ф-ции при ограничениях где х и у — элементы различных гильбертовых пространств частности, может быть нелинейный оператор, такой, что ур-ние Р определяет дифференцируемую ф-цию то можно строить последовательные приближения к решению по ф-лам

где точка минимума ф-ции при условиях Здесь частные производные вычисляются в точке выбирают как и в пунктах б) и в) градиентного метода, используя ф-цию Аналогичным образом можно строить алгоритм, использующий для определения точки квадратичную аппроксимацию функций

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

к решению последовательности задач на безусловный экстремум — минимизации ф-ций

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

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

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

где — неизвестные множители. Простейший метод отыскания точки градиентный: последовательные приближения строятся по ф-лам

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

Лит.: Левитин Е. С., Поляк Б. Т. Методы минимизации при наличии ограничений. «Журнал вычислительной математики и математической физики», 1966, т. 6, № 5; Данилин Ю. М. Методы минимизации, основанные на аппроксимации исходного функционала выпуклым. «Журнал вычислительной математики и математической физики», 1970, т. 10, М S; Данилин Ю. М., Пшеничный Б. Н. О методах минимизации с ускоренной сходимостью. «Журнал вычислительной математики и математической физики», 1970, т. 10, JSIS 6; Huang Н. У. Unified approach to quadratically convergent algorithms for function minimization. «Journal of optimization theory and applications», 1970, v. 5, JSs 6.

Ю. М. Данилин.