1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 8
Текст из файла (страница 8)
Тогда xk → x∗при k → ∞ и метод Ньютона имеет квадратичную скорость сходимостиkk∗2kx − x k ≤ (2l/L)q .-33•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ПОКООРДИНАТНОГО СПУСКАОбласть применения: минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление производных слишком трудоемко.Наиболее эффективен, когда функция являетсягладкой. Метод не требует знания градиента, носходимость можно гарантировать лишь для гладких функций.-34•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ПОКООРДИНАТНОГО СПУСКАf (x) −→ inf nx∈R(1)Пусть ei = (0, .
. . , 0, 1, 0, . . . , 0) – i-ый единичный координатный вектор,x0 – начальное приближение, α0 > 0 – начальная длина шага.Пусть xt ∈ Rn – текущее приближение,αt > 0 – текущая длина шага,λ, 0 < λ < 1 – фиксированное число.-35•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ПОКООРДИНАТНОГО СПУСКАМетод покоординатного спуска – итеративный процесс. Все итерации разбиты на группы. Каждаягруппа содержит столько итераций сколько координатных векторов.
k-ая группа начинается с итерации с номером (k−1) n+1. Последняя итерацияэтой группы имеет номер kn.Опишем итерацию с номером t, где(k − 1) n + 1 ≤ t ≤ kn.(2)-36•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИТЕРАЦИЯ TЕслиf (xt−1 +αt−1 et−(k−1)n) < f (xt−1), (3)то положимxt = xt−1 + αt−1 et−(k−1)n, αt = αt−1.(4)-37•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИТЕРАЦИЯ TЕслиf (xt−1 −αt−1 et−(k−1)n) < f (xt−1), (5)то положимxt = xt−1 − αt−1 et−(k−1)n, αt = αt−1.(6)Если выполняется (3) или (5), то итерация t —удачная.-38•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИТЕРАЦИЯ TЕсли итерация t неудачная, то положим:xt = xt−1,λαt−1, если t = kn, и все итерациигруппы неудачны,αt =αt−1, если t 6= kn или были удачныеитерации внутри группы(7)-39•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ПОКООРДИНАТНОГО СПУСКАПусть в k-ой группе не оказалось ни одной удачнойитерации и шаг дробится.
В этом случае выполняются неравенстваf (xt−1 + αt−1 ei) ≥ f (xt−1),f (xt−1 − αt−1 ei) ≥ f (xt−1),для всех i = 1, . . . , n.(8)-40•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетод покоординатного спускаТеорема 22. Пусть функция f (x) выпукла наRn и f ∈ C 1(Rn), а начальное приближениетаково, что множество M (x0) = {x ∈ Rn :f (x) ≤ f (x0)} ограничено.Тогда последовательность xk имеет хотя бы однупредельную точку и любая предельная точка этойпоследовательности есть оптимальное решение задачи.-41•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 11ОбзорЭкономическая интерпретация теории двойственности, функции Лагранжа и условийКуна–ТаккераЗадачи классического вариационногоисчисления-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЭкономическая интерпретацияЭкономика "Робинзона Крузо":– Только одно лицо принимающее решение (ЛПР).– Одна целевая функция.Экономика "общественного обмена":– Несколько ЛПР принимающих решение (ЛПР).– У каждого ЛПР может быть своя целевая функция.– Вынуждены взаимодействовать для достижения результата.-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействие– Промышленность управляет уровнем производства x = (x1, · · · , xj , · · · , xn) продукции (n– количество видов продукции, xj – уровень производства j-го вида продукции).– f (x1, .
. . , xn) – издержки производства призаданном его уровне x.– Пусть ϕ1i (x) – расход ресурса i при уровне производства x, bi объём i-го ресурса, i = 1, · · · , m.ϕi(x) = ϕ1i (x) − bi.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействие– ϕi(x) ≤ 0 ≡ остаются излишки сырья, ϕi(x) >0 ≡ первоначального количества сырья bi недостаточно для достижения уровня производства, равного x.– Промышленность стремится минимизироватьсвои издержки, возникающие при производстве продукции для рынка, а также при покупке сырья,недостающего для производства. Частично промышленность может уменьшить свои издержки за счётпродажи тех ресурсов, которые в избытке.-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействие– Рынок управляет ценами на ресурсы, которыепромышленность приобретает или продаёт на рынке.
Пусть λi ≥ 0 – цена, по которой единицасырья вида i покупается или продаётся на рынке,i = 1, · · · , m.– Рынок стремится максимизировать свою прибыль, которая складывается из дохода, который онполучает, при продаже ресурсов производству и затрат, которые он несёт при покупке избыточныхдля промышленности ресурсов.-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеИгра:Игрок – промышленность выбирает уровень производства продукции x = (x1, · · · , xj , · · · , xn).Игрок – рынок выбирает цены на ресурсы λi ≥0, i = 1, · · · , m.Итог игрыmXL(x, λ) = f (x) +λiϕi(x)i=1-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеИтак:1.
Итог игры (значение функции Лагранжа) неможет быть однозначно определён ни промышленностью, ни рынком.2. С точки зрения первого игрока – промышленности, значение функции Лагранжа представляетсобой суммарные издержки производства. Они складываются из издержек на производство конечнойпродукции f (x), затрат на покупку недостающего для производства сырья и дохода от продажиизлишков сырья.•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействие3.
С точки зрения второго игрока – рынка, значение функции Лагранжа представляет собой прибыль рынка, которая складывается из доходов запродажу сырья производству и продажу промышленной продукции, которые не могут быть нижеиздержек производства (доход промышленности отпродажи излишков сырья для рынка затраты).-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеПроблема:1. Интересы игроков сосредоточены на одном итом же объекте: на функции L(x, λ).2. Но цели прямо противоположны: первый хочетминимизировать, второй максимизировать.3. Основная проблема в том, что ни один не контролирует значение величины L(x, λ). Т.е. необходимо сделать два выбора x и λ для того, чтобызначение функции Лагранжа определилось. И вдобавок их выборы независимы.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеВыход: Рассмотреть игры, связанные с данной,но в которых не возникает неопределёности.Мажорантная игра: Первый игрок фиксируетуровень производства x, а рынок максимизируетсвой доход: sup L(x, λ).
Т.е. рынок формируетλ≥0целевую функцию g(x) прямой задачи. Зная этоПроизводитель стремится выбрать такой план игры, чтобы найтиν1 = inf sup L(x, λ).x λ≥0•First-10•Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеМинорантная игра: Второй игрок выбирает цены λ ≥ 0, а производство ищет минимум издержек: inf L(x, λ).
Т.е. промышленность формируxет целевую функцию h(x) двойственной задачи.Зная это рынок стремится выбрать такие цены,чтобы найтиν2 = sup inf L(x, λ).λ≥0 x-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеТаким образом, в мажорантной игре решается прямая задача, а в минорантной игре двойственнаязадача.Т.к. ν2 ≤ ν1, то промышленности более интересна 2 игра, а рынку 1 игра. Поэтому, если неравенство строгое,то ситуация неустойчивая, неравновесная.
Каждый из игроков стремится отдать инициативу и сыграть в "свою"игру.-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеЕсли у функции Лагранжа имеется седловая точка (x∗, λ∗), то это означает, что в рассматриваемой модели существует экономическое конкурентное равновесие, при которомmax L(x∗, λ) = min L(x, λ∗)xλс уровнем производства x∗ и ценами на сырьё λ∗.-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеЭто означает, что никакое изменение уровня производства x промышленностью не может уменьшитьиздержки производства.
А с другой стороны этоозначает, что никакая игра с ценами на сырьё неможет увеличить эти издержки.-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПромышленность – рынок: конкурентное взаимодействиеНа эту ситуацию можно взглянуть и с позиций рынка. То есть, никакое изменение уровня производства x промышленностью не может уменьшить доходы рынка, а с другой стороны никакие манипуляции с ценами на сырьё не могут увеличить эти доходы.
Таким образом, состояние равновесия приводит к устойчивому рынку.-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема 10 (Необходимые условия оптимальности Куна–Таккера). Пусть x∗ — локальный экстремум задачи (1), (2), f ∈ C 1,01ϕi ∈ C , i = 1, m, вектора ϕi(x∗), i ∈I(x∗), линейно независимы. Тогда найдутся такие множителиλ∗i ≥ 0, i = 1, m,(1)чтоmX00∗∗(2)−f (x ) =λi ϕi(x∗),i=1λ∗i ϕi(x∗) = 0, i = 1, m.(3)-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЭкономическая интерпретация условий (1) –(3) в рамках концепцииустойчивого рынка.1.
Условия (1) тривиальны, т.к. величины λ∗i играют роль цен.2. Из определения седловой точки имеем:L(x∗, λ∗) = min L(x∗, λ∗).xТ.е. вектор x∗ экстремум функции L(x, λ∗) ⇒mX∂L(x, λ∗) 0∗ 0∗∗λ=f(x)+ ∗i ϕi (x ) = 0.x∂xi=1С экономической точки зрения величина −f 0(λ∗) – маргинальные изmP0держки от производства продукции, аλiϕi(x∗) – маргинальныеi=1доходы от продажи сырья.
Т.е. в точке оптимума маргинальные издержки совпадают с маргинальными доходами, в чём и заключаетсяэкономический смысл соотношений (2).-17•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit3. Очевидно, что в рамках устойчивого рынкане может быть недостатка какого-нибудь ресурса(смотрите доказательство теоремы 1 и определение минорантной игры). Таким образом при анализе соотношений (3) остаётся рассмотреть случай0ϕi(x∗) < 0 и λ∗ > 0Тогда рынок может увеличить издержки производства уменьшая цену i-го ресурса. Это противоречит равновесности рынка.-18•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛекция № 12Задачи классическоговариационного исчисления 5 мая 2014Постановка задачи J ( x (⋅), u(⋅)) → inf(sup), (1) G1 (t , x (t ), x& (t ), u(t )) = 0, G2 (t , x (t ), x& (t ), u(t )) ≤ 0, (2) u(t ) ∈ U (t ) ∈ R r , (3) (t0 , x (t0 ), t1 , x (t1 )) ∈ Γ , (4) Граничные условия (4)– закрепленные, когда значения траектории закреплены на обоихконцах отрезка [t0 , t1 ], при этом сам отрезок предполагается фиксированным: x (t0 ) = x0 , x (t1 ) = x1;– периодические, когда отрезок [t0 , t1 ] фиксирован и фазовая траектория принимает равные значения на концах.25 мая 2014Задача Лагранжа с ограничениями в разрешенной формеи фазовыми ограничениями типа равенств и неравенств называют следующую задачу:J ( x (⋅)) =t1∫ f (t , x(t ), u(t )) dt → inf,(5)t0x& = ϕ (t , x (t ), u(t )) ,(6)g1 (t , x (t )) = 0 , g 2 (t , x (t )) ≤ 0 ,(7)h0 (t0 , x (t0 )) = 0 , h1 (t1 , x (t1 )) = 0 ,(8)u(t ) ∈ U .(9)Пара называется допустимой в задаче, если она удовлетворяет ограничениям (6) и (7) и граничным условиям (8).35 мая 2014Соглашения и определения:ВзадачеЛагранжа(5)–(9)времяфиксировано;( x (t ), u(t )) ∈ C1n ([t0 , t1 ]) × C r ([t0 , t1 ]) .
Исследование простейших задачпроводится в банаховых пространствах C1n ([t0 , t1 ]) .Локальный минимум в пространстве C1n × C r в случае задачи Лагран-жа, или в пространстве C1n в случае простейших задач, называется слабым:Пара ( x* (⋅), u* (⋅)) доставляет слабый локальный минимум функционалу J ( x (⋅), u (⋅)) в задаче (5) – (9), если найдется такое число ε > 0, чтодля любой допустимой пары ( x (⋅), u (⋅)) ∈ C1n × C r такой, чтоx (⋅) − x* (⋅) 1 < ε , u(⋅) − u* (⋅) 0 < ε ,выполняется неравенствоJ ( x (⋅), u(⋅)) ≥ J ( x* (⋅), u* (⋅)) .45 мая 2014Соглашения и определения:Локальный экстремум по x в топологии пространства C1n называетсясильным:допустимая пара ( x∗ (⋅), u∗ (⋅)) дает сильный локальный минимум функционалу J в задаче (6) – (9), если найдется такое число ε > 0 , что длялюбой допустимой пары ( x (⋅), u (⋅)) , для которойx (⋅) − x∗ (⋅) 0 < ε ,выполняется неравенствоJ ( x (⋅), u(⋅)) ≥ J ( x∗ (⋅), u∗ (⋅)) .Аналогичным образом определяется сильный минимум для простейшейвекторной задачи (5).55 мая 2014Элементарный вывод необходимых условий экстремума для простейших задач классического вариационного исчисления: необходимые условия Эйлера⎫J ( x (⋅)) = ∫ L(t , x (t ), x& (t )) → inf,⎪⎬t0⎪( x (t0 ), x (t1 )) ∈ Γ.⎭t1(10)L(t , x, y ) непрерывно дифференцируема в некоторой области U пространства R 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
