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

В большинстве случаев экстремальную задачу , φ_i(x) ≤ 0, i = 1, …,m приходится решать численно на компьютере. При этом можно с помощью необходимых условий оптимальности свести задачу оптимизации к некоторой другой задаче, а затем попытаться использовать разработанные для ее решения численные методы. Так, например, для решения задачи минимизации на Rⁿ дифференцируемой функции f можно воспользоваться каким-либо численным методом решения системы уравнений f '(x) = 0. Однако, наиболее эффективными оказываются методы, разработанные специально для решения задачи оптимизации, так как они позволяют полнее учесть ее специфику.

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

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

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

Для большинства задач точки вычисления выбираются последовательно, то есть точка x^{k +1}, k = 0,1,…, выбирается, когда уже выбраны точки предыдущих вычислений x⁰,…, x^k и в каждой из них произведены предусмотренные алгоритмом вычисления. Для записи методов минимизации будем пользоваться соотношением вида x^k+1 = x^k a _kh_k, a _k ϵ R, k = 0,1,2,…. (1)

При этом конкретный алгоритм определяется заданием точки x⁰, правилами выбора векторов h_k и чисел a _k на основе полученной в результате вычислений информации, а также условиями остановки. Таким образом, величины a _k, h_k в (1) определяются теми или иными видами функциональной зависимости от точек и результатов всех ранее проведенных вычислений, причем на практике обычно используются наиболее простые виды зависимости. Правила выбора a _k, h_k могут предусматривать и дополнительные вычисления, то есть вычисления некоторых характеристик решаемой задачи в точках, отличных от x⁰, x¹,…, x^k.

Вектор h_k определяет направление (k +1) -го шага метода минимизации, а коэффициент a _k – длину этого шага. Следует иметь в виду, что при || h_k || ≠ 1 длина отрезка, соединяющего точки x^k, x^{k +1}, не равна | a _k|. Обычно название метода минимизации определяется способом выбора h_k, а его различные варианты связываются с разными способами выбора a _k. Наряду с термином шаг метода будет использоваться также термин итерация метода.

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

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

Не нашли, что искали? Воспользуйтесь поиском: