Основы теории оптимизации (стр. 14 )

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

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

3.1. Общая характеристика методов нулевого порядка

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

3.2. Нелокальная линейная аппроксимация.

а) Метод конечных разностей. Этот метод состоит в замене производных соответствующим образом выбранными разностями.

Одномерная задача. Рассмотрим задачу:

(1)

где

Разложим и(х + h) в ряд по степеням h:

Oтсюда следует

при

Обозначим Тогда

(2)

Уравнения (2) образуют систему линейных уравнений относительно неизвестных и1, и2, ... , ип, при этом и0 = α и un+1 = β. Эта система имеет ленточную симметричную трехдиагональную матрицу, что позволяет про­водить вычисления быстро и точно.

В нашем примере легко показать сходимость приближенного решения к истинному при п→∞, т. е. h→0. Действительно, вычитая выражение (1) из (2), получим

где

Отсюда следует

Пустьтогда

что и доказывает сходимость.

Чтобы повысить порядок погрешности метода, разложим

в ряд Тейлора в окрестности х:

Если учесть, что

и подставить и(4)k в предыдущую формулу, получим систему линейных урав­нений Аи = b, где

В этом случае погрешность метода составляет

б) Симплексный метод. В конечно-раз­ностном градиентном методе пробные и рабочие шаги разделяют — точки xk + αіеі служат только для оценки гра­диента в xk, в xk+1 вся работа проводится заново. Можно посту­пить и иначе, и строить линейную аппроксимацию по набору то­чек, расположенных достаточно далеко.

Типичным примером служит так называемый симплексный метод (не путать с симплекс-методом в линейном программиро­вании!). Пусть выбраны п+1 точек х0, х1, ..., хп, образующие вершины правильного симплекса. Вычислим значения f(х) в вершинах и найдем ту, для которой f(x) максимальна:

.

Построим новый симплекс, отличающийся от старого лишь одной вершиной; хj заменяется на хп+1:

(3)

(т. е. xn+1 симметрично с хj относительно грани, противолежа­щей хj). Если окажется, что в новом симплексе максимум дости­гается в xn+1, то возвращаемся к исходному симплексу, заменив хj на вершину, в которой значение f(x) максимально среди оставшихся вершин и т. д. Если какая-либо точка сохраняется в п+1 последовательном симплексе, то последний симплекс сокращается вдвое подобным преобразованием с центром в этой вершине (рис. 1).

Рис. 1. Cимплексный метод

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

3.3. Квадратичная аппроксимация.

Вычислив значения f(x) в достаточном числе точек, можно построить квадратичную ап­проксимацию f(x). Удобно это сделать, например, следующим образом (метод барицентрических координат). Выбирается (как и в симплексном методе) п+1 базисных точек х0,...,хп. Вы­числяются значения функции во всех этих точках и серединах соединяющих их отрезков (обозначим

После этого решается система линейных (относительно λ1, λ2, ..., λп) уравнений

(4)

и строится точка

(5)

Нетрудно проверить, что если f квадратична, то хп+1 = х* =А-1b при любых х0, ..., хп таких, что хп = х0,...,х1— x0 линейно независимы.

Далее (для неквадратичной f(x)) точка xn+1 включается в число базисных, а одна из прежних базисных точек (точка х0 или та, в которой f(x) максимальна) удаляется. На следующей итерации достаточно вычислить f(x) в п+1 точках (в хп+1 и серединах отрезков, соединяющих xn+1 с остальными базисными точками). Новая система уравнений для λi будет отличаться от (4) лишь одной строкой, так что можно использовать резуль­тат известной леммы для построения решения. Аналогичным образом процесс продолжается дальше.

Удобство метода в том, чго сама квадратичная аппроксима­ция функции не выписывается явно, строится лишь точка мини­мума этой аппроксимации. По сравнению с конечно-разностным аналогом метода Ньютона здесь существенно меньше вычисле­ний f(x) на каждом шаге (п+1 вместо п(п+1)/2). Для при­дания устойчивости процессу в нем нужно ввести регулировку длины шага, принять меры для предотвращения вырождения системы базисных точек, проверять условие выпуклости fij ≤(fii + fjj)/2 и т. п.

Другая группа методов прямого поиска использует идеи ме­тода сопряженных направлений и сводит исходную задачу к