Понятие о численных методах оптимизации

Начальные сведения о численных методах оптимизации

Иногда удается, опираясь на условия оптимальности или на геометрическую интерпретацию, получить решение задачи оптимизации

f(x) ® min, x Î X, (2.1)

в явном виде, но в большинстве случаев задачу (2.1) приходится решать численно, с применением ЭВМ. Так, например, для решения задачи минимизации на Rⁿ дифференцируемой функции f можно воспользоваться каким-либо численным методом решения системы уравнений f'(x) = 0. Однако, как правило, наиболее эффек­тивными оказываются методы, разработанные специально для реше­ния задачи оптимизации, так как они позволяют полнее учесть ее специфику.

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

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

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

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

Алгоритмы, использующие лишь информацию о значениях мини­мизируемой функции, называются алгоритмами нулевого порядка; алгоритмы, использующие также информацию о значениях первых производных, – алгоритмами первого порядка; алгоритмы, использую­щие, кроме того, информацию о вторых производных, – алгоритмами второго порядка.

В курсе рассматриваются алгоритмы только нулевого, первого и второго порядка.

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

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

Однако для решения большинства задач точки вычисления выби­раются поочередно, т. е. точка xⁱ⁺¹ выбирается, когда уже выбраны точки предыдущих вычислений х¹, ..., хⁱ и в каждой из них произведены предусмотренные алгоритмом вычисления, результаты кото­рых будем обозначать соответственно через у¹, ..., уⁱ. Такие алго­ритмы называются последовательными. Таким образом, последова­тельный алгоритм определяется точкой х¹ Î Х и набором отображе­ний вида

.

При этом

. (2.2)

В дальнейшем для записи методов минимизации мы будем поль­зоваться соотношением вида

x^k+1 = x^k + a_kh^k, a_k Î R, k = 0, 1, 2, … (2.3)

При этом конкретный алгоритм определяется заданием точки х⁰,правилами выбора векторов h^k и чисел a_k на основе полученной в результате вычислений информации, а также условием остановки. Таким образом, величины a_k, h^k в формуле (2.3) точно так же, как xⁱ⁺¹ в формуле (2.2), определяются теми или иными видами функ­циональной зависимости от точек и результатов всех ранее прове­денных вычислений, причем на практике обычно используются наи­более простые виды зависимости. Правила выбора a_k, h^k могут предусматривать и дополнительные вычисления, т.е. вычисления некоторых характеристик решаемой задачи в точках, отличных от x⁰, х¹, ..., х^k. Именно поэтому в формулах (2.2) и (2.3) употреблены различные индексы.

Вектор h^k определяет направление (k+1)-го шага метода мини­мизации, а коэффициент a_k – длину этого шага. При этом следует иметь в виду, что при

|| h^k || ¹ 1 длина отрезка, соединяющего точки х^k, x^k+1, конечно, не равна |a_k |. Обычно название метода минимизации определяется способом выбора h^k, а его различные варианты связы­ваются с разными способами выбора a_k. Наряду с термином шаг метода мы будем пользоваться также термином итерация метода.

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