1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 6
Текст из файла (страница 6)
Из условий теоремы следует, что g > 0 и, следовательно,f ( x k +1 ) £ f ( x k ) .Кроме того, для любой итерации k выполняется неравенствоf ( x k +1 ) £ f ( x 0 ) - gkå2f ¢( x i ) .i =0Поэтому, учитывая ограниченность функции f на множестве R n , получаемдля любого s Î N оценку сверху для частичных сумм:s2f ( x 0 ) - f ( x s +1 ) f ( x 0 ) - f *£.å f ¢( x k ) £ggk =0Откуда и следует сходимость к нулю градиента f ¢( x k ) при k ® ¥ . ▄В условиях теоремы 2 градиентный метод обеспечивает сходимость последовательности { f ( x k )}kÎN либо к точной нижней грани inf n f ( x ) , еслиxÎRфункция f (x ) не имеет минимума, либо к значению f ( x * ) , где x* = lim x kk ®¥и f ¢( x * ) = 0 , если такой предел существует. Существуют примеры, когда вточке x * реализуется седло, а не минимум.
Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции. Для оценки скорости сходимости методапредположений теоремы 2 недостаточно. Сделаем это в случае, когда f (x ) –сильно выпуклая функция.27Теорема 3 (вторая теорема сходимости). Пусть функция f дифференцируема в R n , является сильно выпуклой, выполняется условие Липшица дляградиента функции и длина шага a удовлетворяет условию 0 < a < 2 L .
Тогдаx k ® x * при k ® ¥ и x k - x * £ Cq k , 0 £ q < 1 .Доказательство. Воспользуемся неравенством, полученным при доказательстве теоремы 2:2f ( x k +1 ) £ f ( x k ) - a (1 - La / 2) f ¢( x k ) .По лемме 1.1 существует глобальный минимум x * функции f . Используя(1.7), получимf ( x k +1 ) £ f ( x k ) - la (2 - La )( f ( x k ) - f ( x * )) .Вычитая из обеих частей неравенства величину f ( x * ) , получимf ( x k +1 ) - f ( x * ) £ (1 - la ( 2 - La )( f ( x k ) - f ( x * )).(14)Обозначим через q1 коэффициент при выражении ( f ( x k ) - f ( x * )) . Индукцией легко показать, чтоf ( x k +1 ) - f ( x * ) £ q1k +1 ( f ( x 0 ) - f ( x * )) .Проверим, что q1 ³ 0 . Функция f является сильно выпуклой.
Значит, она неможет быть константой и имеется возможность выбрать начальную точку x 0так, чтобы f ( x 0 ) > f ( x * ) . Из неравенства (14) при k = 0 имеем0 £ f ( x1 ) - f ( x * ) £ q1 ( f ( x 0 ) - f ( x * )) ,откуда и следует требуемое неравенство.Так как q1 < 1 , то f ( x k ) ® f ( x * ) при k ® ¥ . Учитывая, что f ¢( x * ) = 0 ,из (11) при подстановках y = x k - x * и x = x * получим( f ( x k ) - f ( x* )) ³ l || x k - x* ||2 / 2 .Следовательно,|| x k - x * ||2 £ 2q1k ( f ( x 0 ) - f ( x * )) / l .Последнее неравенство дает линейную оценку скорости сходимости метода|| x k - x * ||£ Cq k ,где C = 2( f ( x 0 ) - f ( x * )) l , q = q1 .
Отсюда также следует сходимостьпоследовательности {x k }kÎN к единственной точке минимума x * . ▄§ 4. Метод НьютонаПерейдем к изложению метода второго порядка, использующего вторыечастные производные минимизируемой функции f (x ) . Рассматриваемый28далее метод является прямым обобщением метода Ньютона для отысканиярешения системы уравнений j ( x ) = 0 , где j : R n ® R n . Возьмем линейнуюаппроксимацию функции j (x ) в окрестности точки x k и перепишем векторное уравнение в следующем виде:j ( x ) = j ( x k ) + j ¢( x k )( x - x k ) + o( x - x k ) = 0 .Отбрасывая последний член в этом разложении, получим линейную системууравнений относительно нового приближения x k +1 .
Таким образом, методНьютона для отыскания решения системы уравнений описывается следующей формулой:x k +1 = x k - (j ¢( x k )) -1j ( x k ) .Пусть функция j (x ) является градиентом некоторой функции f (x ) . Формула метода Ньютона для решения уравнения f ¢( x ) = 0 выглядит так:x k +1 = x k - ( f ¢¢( x k )) -1 f ¢( x k ) .В этом случае метод Ньютона можно интерпретировать как поиск точки минимума квадратичной аппроксимации функции f (x ) в окрестности точкиxk .Пусть последовательность {x k }kÎN получена с помощью метода Ньютонаи точка x * – глобальный минимум функции f .
Следующая теорема даетусловия квадратичной скорости сходимости метода.Теорема 4. Пусть дважды непрерывно дифференцируемая функция fсильно выпукла с константой l > 0 , вторая производная удовлетворяет условию Липшицаf ¢¢( x ) - f ¢¢( y ) £ L x - y для любых x, y Î R n ,и q = L f ¢( x 0 ) 2l 2 < 1 . Тогда x k ® x * при k ® ¥ , и метод Ньютона имеетквадратичную скорость сходимостиx k - x * £ ( 2l L) q 2k .Доказательство.
Воспользуемся следующей формулой конечных приращений:1g ( x + y ) = g ( x ) + g ¢( x ), y + ò ( g ¢( x + ty ) - g ¢( x )) dt .0Подставим вместо g производную функции f и, применяя неравенство Коши-Буняковского, получимf ¢( x + y ) - f ¢( x) - f ¢¢( x), y £ L y2922.[Тогда для x = x k и y = - f ¢¢( x k )]-1f ¢( x k ) имеемf ¢( x k +1) £ ( L 2)[f ¢¢(x )]2k -12f ¢( x k ) .Применяя лемму 1.3, получим2f ¢( x k +1 ) £ ( L 2l 2 ) f ¢( x k ) .Итерируя это неравенство по k , приходим к неравенствуf ¢( x k +1 ) £ ( 2l 2 L)( L f ¢( x 0 ) 2l 2 ) 21442443k +1.qОстается показать, чтоf ¢( x k +1 ) ³ l x k +1 - x * .Из сильной выпуклости имеем2f ¢( x ) - f ¢( y ), x - y ³ l x - y .Тогда при подстановке y = x * , x = x k +1 , учитывая равенство f ¢( x * ) = 0 , получим2l x k +1 - x * £ f ¢( x k +1 ), x * - x k +1 £ f ¢( x k +1 ) x * - x k +1 ,откуда следует требуемое неравенство.
▄30ГЛАВА 3ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГОПРОГРАММИРОВАНИЯВ этой главе рассматривается задача минимизации линейной целевойфункции на множестве допустимых решений, которое также определяетсялинейными ограничениями. Подобные задачи составляют предмет линейногопрограммирования (ЛП). Любую задачу линейного программирования с помощью простых приемов можно привести к виду:(1)( c, x ) ® min(2)Ax = b ,(3)x³0.Задача (1)-(3) называется задачей линейного программирования в канонической форме. Далее рассматриваются только такие задачи.В первом параграфе содержится описание наиболее известного методарешения линейных задач – прямого симплекс-метода. В предлагаемом варианте метода вычисления организованы на основе симплекс-таблиц и элементарных преобразований.Во втором параграфе приводится более эффективный вариант симплексметода, известный под названием модифицированного симплекс-метода илиалгоритма с обратной матрицей.Третий параграф посвящен лексикографическому варианту симплексметода.
Важность этой модификации метода связана с явлением зацикливания, которое может возникать при решении вырожденных задач ЛП. В этомслучае базисному допустимому решению (б.д.р.) может соответствовать несколько базисов и при определенных условиях они начинают повторяться.Следовательно, симплекс-метод не может выйти из текущей вершины, бесконечное число раз повторяя одну и ту же итерацию. В предлагаемом варианте алгоритма эта проблема решена с помощью лексикографического правилавыбора ведущей строки.В вариантах симплекс-метода, рассматриваемых в предыдущих параграфах, предполагается, что известна начальная симплекс-таблица.
В четвертомпараграфе описывается метод искусственного базиса или двухфазовый симплекс-метод, который не требует информации о начальном б.д.р. На первомэтапе работы алгоритм находит начальное б.д.р. решаемой задачи, либо устанавливает несовместность ее ограничений. На втором этапе он либо находитоптимальное решение, либо устанавливает неразрешимость исходной задачииз-за неограниченности целевой функции.Пятый параграф посвящен описанию двойственного симплекс-метода.Можно считать, что этот метод есть прямой симплекс-метод, примененный кдвойственной задаче, записанной в канонической форме, и реализованный насимплекс-таблицах прямой задачи.31В шестом параграфе рассматривается лексикографический двойственныйсимплекс-метод. Особенность этой модификации метода состоит в том, чтопомимо лексикографического правила выбора ведущего столбца, которое гарантирует отсутствие зацикливания, алгоритм основывается на другом типесимплекс-таблиц.
Последнее обстоятельство делает удобным применениеэтого алгоритма в циклическом алгоритме Гомори.В седьмом параграфе представлена геометрическая интерпретация задачЛП, которая позволяет по-новому взглянуть на эти задачи и методы их решения.Восьмой параграф является иллюстрацией того, как интерпретация задачлинейного программирования используется для описания методов решениязадач ЛП.
Содержание параграфа составляет геометрическая интерпретацияпрямого симплекс-метода.§ 1. Прямой симплекс-методДанный параграф посвящен описанию и теоретическому обоснованиюсимплекс-метода [2, 3, 5, 6, 7, 9, 10, 11]. В отечественной литературе методизвестен также под названием метода последовательного улучшения плана[12]. Основы метода были сформулированы Данцигом в 1947. Его общепринятое название возникло из геометрической интерпретации задач, для решения которых он был впервые применен, и не отражает суть метода.Симлекс-метод является алгоритмом локального поиска, который применяется для решения задач ЛП. Действительно, рассмотрим вершины многогранного множества допустимых решений.
В качестве окрестности любой извершин возьмем множество соседних вершин, то есть вершин, каждая из которых соединяется ребром с данной вершиной. Проверяя текущую вершину,симплекс-метод за полиномиальное время определяет, является ли она локальным оптимумом или нет. Если получен локальный оптимум, то алгоритмзавершает свою работу. Так как задача линейная, то найденный локальныйоптимум является глобальным. Если текущая вершина не является оптимумом, то симплекс-метод отыскивает ребро, при движении по которому значение целевой функции убывает. Возможно два случая: ребро конечно или бесконечно. Симплекс-метод за полиномиальное время определяет, какой изслучаев реализовался.
Если ребро бесконечно, то алгоритм завершает своюработу, так как в этом случае задача неразрешима в силу неограниченностиснизу целевой функции. Если ребро конечно, то симплекс-метод вычисляетсоседнюю вершину, и следующая итерация начинается с этой вершины.1.1 Базис и базисное решениеПредположим, что матрица A имеет ранг m ( m £ n ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
