Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 31
Текст из файла (страница 31)
32. Спуск по координатам странстве. На рис. 32 папе- сены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка ЛХ, (х„у,) описывает начальное приближение. Проводя спуск по координате х, попадем в точку М,(х„у,). Далее, двигаясь параллельно оси ординат, придем в точку М,(х„у!) и т. д. Гл.
6. метОды ОптимизАцпи Важным здесь является вопрос о сходимостп рассматриваемого процесса оптимизации. Другими словами, будет ли последовательность значений целевой функции ~(ЛХ,), /(Л1,), ... сходиться к наименьшему ее значению в данной области? Это зависит от вида самой функции н выоора начального приблиНачало жения.- .Для функции двух пере- менных очевидно, что метод Ввод и, (,х4Н) неприменим в случае наличия изломов в линиях уровня.
Это соответствует так на ~ ('4~, .~'2 ~ ° ° ~~п ) аываемому оврагу на поверх- ности. Здесь возможен слу(',=1 чай, когда спуск по одной координате приводит 'на «дно» евра га. Тогда любое 'А =В движение вдоль другой координаты ведет к возрастанию функции, соответствующему Ю=~ „Гх;) подьему на «берег» оврага. уточненне л;. 11оскольку поверхности типа «оврага» встречаются в инженерной практике, то при иск с и — » =~+1 пользовании метода покоор- дпнатного спуска следует убенег диться, что решаемая зада- ча не имеет етого недостатка.
(4-фсе Для гладких функций при удачно выбранном начальДа ном приближении (в некото- рой окрестности минимума) Вывод (л;~ процесс сходится к минимуму. К достоинствам метода Конец покоординатного спуска сле- дует также отнести возможРис. 33. Блок-схема метода по- ность использования простых координатного спуска алгоритмов одномерной опти- мизации. Блок-схема метода покоординатного спуска представлена на рпс. 33.
3. Метод градиентного спуска. В природе мы нередко наблюдаем явления, сходные с решением задачи на нахождение минимума. 11 ним относится, в частности, стеканпе воды с берега котлована на дно. Упростим ситуа- $3. ЫНОГОМЕРНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ цпю, считая, что берега котлована «упимодальны», т. е. опи гладкие и не содержат локальных углублений пли выступов. Тогда вода устрезштся вниз в направлении наибольшей крутизны берега в каждой точке. Переходя на математический язык, заключаем, что направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Из курса математпкп известно, что направление напоольшего возрастания функции двух переменных и=~(х, у) характеризуется ее градиентом да ди цгали = — е + — е дх 1 ду где е„е, — единичные векторы (орты) в направлении координатных осей.
Следовательно, направление, противоположное градиентному, укажет путь, ведущий вниз вдоль напоолее крутой линии. Методы, основанные на вы-- боре пути оптимизации с помощью градиента, называются градиентными. Идея метода градиентного спуска состоит в следующем. Выбираем некоторую начальную точку и вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному. В результате приходим в точку, значение функции в которой обычно меньше первоначального.
Если это условие не выполнено, т. е. значение функции не изменилось либо даже возросло, то нужно уменьшить шаг. В новой точке процедуру повторяем: вычисляем градиент и снова делаем шаг в обратном к нему направлении. Процесс продолжается до получения наименьшего значения целевой функции. Момент окончания поиска наступит тогда, когда движение из полученной точки с любым шагом приводит к возрастанию значения целевой функции. Строго говоря, если минимум' функции достигается внутри рассматриваемой области, то в этой. точке градиент равен нулю, что также может служить сигналом об окончании процесса оптимизации.
В описапном методе требуется вычислять на каждом шаге оптимизации градиент целевой функции ~(х;, х„ , х„): Г дт дт' д11 Формулы для частных производных можно получить в явном виде лишь в том случае, когда целевая функция гл. 6. метОды оптпмизАцпи задана аналитически. В противном случае эти производные вычисляются с иомощью численного дифференцирования: — — [/ (х„..., х, + Лх;,..., х„)— д1 т 1 — 1(х,,..., х;, ., х„)1, 1 = 1, 2, ..., н. Прп использовании градиентного спуска в задачах оптимизации основной оо ьем вычислений приходится ооычно на вычисление градиента целевой функции в ка;идой точке траектории спуска. Поэтому целесообразно уменьшить количество таких точек оез ущерба для само1о решения.
Это достигается в некоторых методах, являющихся модпфикациямп градиентного спуска. Одйпм пз них является л~етод наискорейшего сяуска. Согласно этому методу, после определения в начальной точке направленяя, противоположно~ о градиенту целевой функции, в этом направлении делают не один шаг, а двигаются до тех иор, пока целевая функция убывает, достигая таким образом минимума в некоторой то1ко. В этой точке снова определяют направление спуска (с помощью градиента) и ищут новую точку минимума целевой функции п т.
д. В этом методе спуск происходит гораздо более крупными шагами и градиент функции вычисляется в меньшем числе точек. Заметим, что метод наискорейшего спуска сводит тшогомерную задачу оптимизации к последовательности одномерных задач на каждом шаге оптимизации, как и в случае покоординатного спуска. Разница состоит в том, что здесь направление одномерной оптимизации определяется градиентом целевой функции, тогда как покоординатный спуск проводится па каждом шаге вдоль одного пз координатных направлений.
Советуем читателю для лучшего понимания метода наискорейшего спуска построить блок-схему, аналогичную представленной на рпс. 33 для метода покоординатного спуска. $ 4. Задачи с ограничениями 1. Метод штрафных функций. Решение задач математического программированйя значительно более трудоемко по сравнепзпо с задачамп оезусловиой оптимизации.
Ограничения типа равенств или неравенств трооуют их учета Р 4. злдлчп с ОГРлп11чГнпями на каждом шаге опгпмпзацпп. Одним пз направлений в методах решения задач математического программирования является сведенпе их к последовательности задач безусловной мпнимизацин. К этому направлению относится, в частности, метод гитрафных фуннг~ггй. Сущность метода состоит в следующем. Пусть ~(х„х„..., х„) — целевая функцня, для которой нужно найти мпнпмум пг в ограппченной ооласти Й (х„х,,, ... ..., х„ей). Данную задачу заменяем задачей о безусловной минимизации однопараметрпческого семейства функцпй Г(х, р) = ~(х) + — с~ (х), х=(х„х2,..., х„).
(6Л2) д;(х)=0, г=1, 2,..., 1; (6ЛЗ) Л,(х)) О, ~'= 1, 2, ..., У; х = (х„х... хА В этом случае в качестве вспомогательной целевой функ- Прп этом дополнптельную (штрафную) функцию ~ (х) выберем такпм образом, чтооы при ~-~ 0 решение вспомогательной задачи стремнлось к решению исходной плп, по крайней мере, чтобы их минимумы совпадалн: пи'пГ(х, р)- т прп 'р- О. Штрафная функция ~р(х) должна учитывать огранпченпя, которые задаются прп постановке задачи оптимизацпп; В частности, если имеются ограничения-неравенства аида д,(х„х...... х )~0 (г=1, 2, ..., У), то в качестве штрафной можно взять функцию, которая: 1) равна нулю во всех точках пространства проектирования, удовлетворяющих заданным ограничениям-неравенствам; 2) стремится к бескопсчпости в тех точках, в которых этп неравенства не выполняются, Таким образом, при вы— полнении ограничений-неравенств функцпп 1(х) н Г (х, р) имеют один и тот же минимум.
Если хотя бы одно неравенство не выполнится, товспомогательная целевая функцпя Г(х, р) получает бесконечно большие добавки, н ее значения далеки от мпнпмума функцнп 1(х). Другпмп словами, при песоблюдеипи ограничений-неравенств налагается «штраф». Отсюда и термин «метод штрафных функций». Теперь рассмотрим случай, когда в задаче оптимизацпи заданы ограннчения двух типов — равенства и неравенства: гл. О. мнтод1>1 оптпмпз.гнпп цпп, для которой формулируется задача безусловной оптимизации во всем и-мерном -пространстве, принимают функцию Х Р (х, Я = ~(х) + — ~,~~ д'; (х) + ~ 6',- (х) (1 — ваап й, (х)),, Ь=~ 3= — т (6.14) Здесь взята такая штрафная функция, что прп выполнении условий (6 13) опа обращается в нуль, Если же эти условия нарушены (т.
е. д;(х) Ф О, Ь,(х) ~ О и ядп Ь;(х) = = — 1), то штрафная функция положительна. Она увеличивает целевую функцию ~(х) тем больше, чем больше нарушаются условия (0.13). При малых значениях параметра р вне области й функция Г(х, р) сильно возрастает. Поэтому ее минимум может быть либо внутри б, либо снаружи волпзп границ этой области.
В первом случае минимумы функций Г(х, р) и /(х) совпадают, поскольку дополнительные члены в (6.14) равны нулю. Если минимум функции Г(х, Д) находится вне б, то минимум целевой функции ~(х) лежит на границе В. Можно при этом построить последовательность ~, — О такую, что соответствующая последовательность минимумов функции Г(х, р) будет стремиться к минимуму функции ~(х). Таким ооразом, задача оптимизации для целевой функции /(х) с ограничениями (6.13) свелась к последовательности задач безусловной оптимизации для вспомогательной функции (6.14), решение которых может быть проведено с помощью методов спуска, Прн этом строится птерацпопньш процесс прп ~ — О.
Укрупненная блок-схема решения задачи математического программирования с использованием метода штрафных функций представлена на рис. 34. В качестве исходных данных вводятся начальное приближение искомого вектора х = 1х~, х2... „х„1, начальное значение параметра р и некоторое малое число е, характеризующее точйость расчета. На каждом шаге итерационного процесса определяется оптимальное значение т'" вектора х, прн этом в качестве начального прпблгпкеппя принимается результат предыдущей итерации.
Значения параметра ~ каждый раз уменьшаются до тех пор, пока значение штрафной функции не станет заданной малой величиной. й'4. ЗАДХ11П С ОГРЛЕП1чггНПЯМИ В этом случае точка х* достаточно близка к границе ооласти 0 и с необходимой точностью описывает оптимальные значения проектных параметров, Если точка ътинимума находится внутри области й, то искомый результат будет получен сразу после первого шага, поскольку в данном случае ер(х") = О. Рис. 34, Блок-схема метода штрафных функций 2. Линейное программирование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
