1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 3
Текст из файла (страница 3)
На первом этапе вычисляютсяпредусмотренные алгоритмом характеристики задачи. На втором этапе пополученной информации строится приближение к решению. Для задач оптимизации выбор на втором этапе способа построения приближения, как правило, не вызывает затруднений. Например, для методов спуска, в которых накаждом шаге происходит переход в точку с меньшим, чем предыдущее, значением функции, за приближение к точке минимума обычно выбирается точка последнего вычисления.
Поэтому в алгоритме достаточно указать способвыбора точек вычисления, при условии, что уже решен вопрос о том, какиеименно характеристики решаемой задачи следует вычислять.Для большинства задач точки вычисления выбираются последовательно,то есть точка x k +1 , k = 0,1,K, выбирается, когда уже выбраны точки предыдущих вычислений x 0 ,K, x k и в каждой из них произведены предусмотренные алгоритмом вычисления. Для записи методов минимизации будем пользоваться соотношением видаx k +1 = x k + a k hk , a k Î R, k = 0,1, 2,K .(8)При этом конкретный алгоритм определяется заданием точки x 0 , правиламивыбора векторов hk и чисел a k на основе полученной в результате вычислений информации, а также условиями остановки. Таким образом, величиныa k , hk в (8) определяются теми или иными видами функциональной зависимости от точек и результатов всех ранее проведенных вычислений, причем напрактике обычно используются наиболее простые виды зависимости.
Правила выбора a k , hk могут предусматривать и дополнительные вычисления, тоесть вычисления некоторых характеристик решаемой задачи в точках, отлич-ных от x 0 , x1 ,K, x k .Вектор hk определяет направление ( k + 1) -го шага метода минимизации, акоэффициент a k – длину этого шага. Следует иметь в виду, что при || hk ||¹ 113длина отрезка, соединяющего точки x k , x k +1 , не равна | a k | . Обычно название метода минимизации определяется способом выбора hk , а его различныеварианты связываются с разными способами выбора a k .
Наряду с терминомшаг метода будет использоваться также термин итерация метода.Трудоемкость решения задачи оптимизации зависит от числа ее переменных, вида целевой функции, а также вида и числа ограничений. Часто методы, разработанные для решения того или иного типа задач, оказываются полезными для решения более сложных задач. Так, например, алгоритмы одномерной оптимизации широко применяются при решении многомерных задач;многие алгоритмы условной оптимизации используют методы безусловнойоптимизации или являются их модификацией; методы решения задачи линейного программирования используются при решении задач нелинейногопрограммирования и т.
д.Среди методов минимизации можно условно выделить конечношаговые ибесконечношаговые методы. Конечношаговыми, или конечными, называютсяметоды, гарантирующие отыскание решения задачи за конечное число шагов.Конечношаговые методы удается построить лишь для некоторых специальных типов задач оптимизации, например, задач линейного и квадратичногопрограммирования. Для бесконечношаговых методов достижение решениягарантируется лишь в пределе.§ 4.
Сходимость методов оптимизацииВажной характеристикой бесконечношаговых методов является сходимость. Будем говорить, что метод, задаваемый соотношением (8), сходится,если x k ® x * при k ® ¥ , где x * – решение задачи (1)-(2). Еслиf ( x k ) ® f ( x * ) при k ® ¥ , то иногда также говорят о сходимости по функции, при этом последовательность {x k }k ÎN называют минимизирующей. Минимизирующая последовательность может и не сходиться к точке минимума.В случае, когда точка минимума x * не единственна, под сходимостью методапонимается сходимость последовательности {x k }k ÎN к множеству Q * точекминимума функции f .Эффективность сходящегося метода можно охарактеризовать с помощьюпонятия скорости сходимости.
Пусть x k ® x * при k ® ¥ . Говорят, что последовательность {x k }k ÎN сходится к x * линейно (с линейной скоростью, соскоростью геометрической прогрессии), если существуют такие константыq Î ( 0,1) и k 0 , чтоx k +1 - x * £ q x k - x * при k ³ k 0 .(9)Говорят, что {x k }k ÎN сходится к x * сверхлинейно (со сверхлинейной ско14ростью), еслиx k +1 - x * £ qk +1 x k - x * , qk ® 0 при k ® ¥ .(10)Говорят о квадратичной сходимости, если существуют такие константыC ³ 0 и k 0 , что2x k +1 - x * £ C x k - x * при k ³ k 0 .(11)Иногда, сохраняя ту же терминологию, неравенства (9)-(11) заменяют соответственно на неравенстваx k +1 - x * £ C1q k +1 при k ³ k 0 ,(12)x k +1 - x * £ C2 qk +1qk K q1 ,(13)x k +1 - x * £ C3q 2k +1 при k ³ k 0 , 0 < q < 1.(14)Ясно, что из (9) следует (12), а из (10) следует (13).
Если предположить,1что справедливо (11) и при некотором q Î ( 0,1) x k0 - x * £ q 2 k0 , тоC1 2 k 0 +11q, x k0 + 2 - x * £ q 2k 0 + 2 ,…,CCтогда из (11) следует (14) при C3 = 1 / C .x k0 +1 - x * £Для характеристики сходимости последовательности { f ( x k )}k ÎNf ( x* )кв ситуациях, аналогичных (6) или (9), (7) или (10), (8) или (11), используются аналогичные термины: линейная, сверхлинейная и квадратичнаяскорость сходимости.Для невыпуклых задач численные методы оптимизации обычно позволяютотыскивать лишь локальные решения, а, точнее говоря, стационарные точки.Задача отыскания глобального решения в общем случае чрезвычайно сложна.Алгоритмы глобальной оптимизации требуют больших затрат вычислительных ресурсов даже для функций одной переменной. Получение же достаточно точного решения многомерных задач глобальной оптимизации с помощьюсуществующих в настоящее время численных методов оказывается вообщеневозможным.
Установление факта сходимости и оценка скорости сходимости дают существенную информацию о выбранном методе минимизации.Прежде всего, требования, которые приходится накладывать в теореме о сходимости на минимизируемую функцию, показывают область применимостиметода. Часто в теоремах о сходимости в явном виде формулируются требования к начальному приближению. Наконец, анализ скорости сходимостидает полезную количественную и качественную характеристику изучаемогометода оптимизации.В то же время реальный процесс оптимизации не может быть бесконечношаговым, что существенно ограничивает применимость теорем о сходимости на практике. Кроме того, в ряде случаев предположения этих теорем15труднопроверяемы.
Поэтому при выборе подходящего метода решения реальных задач приходится во многом руководствоваться здравым смыслом,опытом, интуицией, а также результатами численных экспериментов. Длязадания конкретного вычислительного алгоритма бесконечношаговый методнеобходимо дополнить условием остановки.
Условие остановки может определяться имеющимися в наличии вычислительными ресурсами. Например,может быть задано число вычислений предусмотренных алгоритмом характеристик минимизируемой функции f . Остановка может производиться и подостижении заданной точности решения задачи, например, на основе оценок(12)-(14). Однако при решении реальной задачи трудно оценить истиннуюточность. Так, константы, фигурирующие в оценках (12)-(14), обычно неизвестны. Поэтому о достижении заданной точности приходится судить по косвенным признакам.На практике часто используются следующие условия остановки:x k +1 - x k £e 1 ,(15)f ( x k +1 ) - f ( x k ) £e 2 ,(16)f ' ( x k +1 ) £e 3 .(17)До начала вычислений выбирается одно из условий (15)-(17) и соответствующее ему малое e i > 0 , i = 1,2,3 .
Вычисления прекращаются после ( k + 1) го шага, если впервые оказывается выполненным выбранное условие остановки. На практике также используются критерии, состоящие в одновременном выполнении двух из условий (15)-(17) или всех трех условий.
Ясно, чтокритерий (17) относится лишь к задачам безусловной оптимизации. Его выполнение означает, что в точке x k +1 с точностью e 3 выполнено условие стационарности. В задаче условной оптимизации критерий (17) следует заменить на критерий « e -стационарности», соответствующий данной задаче.Вместо условий (15)-(17), основанных на понятии абсолютной погрешности, можно использовать аналогичные критерии, основанные на понятии относительной погрешности:x k +1 - x k £d 1(1 + x k +1 ) ,f ( x k +1 ) - f ( x k ) £d 2(1 + f ( x k +1 ) ) ,f ' ( x k +1 ) £d 3(1 + f ( x k +1 ) ) .Отметим, что выполнение указанных критериев и других подобных им эвристических условий остановки не гарантирует достижения необходимойточности решения задачи.В методах спуска направление движения к минимуму на каждом шаге выбирается из числа направлений убывания минимизируемой функции.16Говорят, что вектор h задает направление убывания функции f в точкеx , если f ( x + ah) < f ( x ) при всех достаточно малых a > 0 .
Сам вектор hтакже называют иногда направлением убывания. Множество всех направлений убывания функции f в точке x будем обозначать через U ( x , f ) . Такимобразом, если любой достаточно малый сдвиг из x в направлении вектора hприводит к уменьшению значения функции f , то h ÎU ( x , f ) . Заменив неравенство, фигурирующее в определении направления убывания, на противоположное, получим определение направления возрастания.В дальнейшем нам понадобятся следующие достаточный и необходимыйпризнаки направления убывания функции.Лемма 4. Пусть функция f дифференцируема в точке x Î R n . Если вектор h удовлетворяет условиюf ' ( x ), h < 0 ,(18)то h ÎU ( x , f ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
