Редактирование: Тигры, 01 лекция (от 04 сентября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
* '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_04.ogg | * '''Аудиозапись:''' http://esyr.org/lections/audio/game_theory_2008_winter/GT_08_09_04.ogg | ||
- | + | Раздел 1. Антгонистические игры (АИ) | |
- | В АИ | + | В АИ принимют учстие 2 игрока --- первый и второй игрок. Игр опредлеляется тремя элементами: множество стртегий первого игрока X. Его иногд называют множеством чистых стратегий. Y --- множество стртегий второго игрока. K(x, y), X ∈ X, y ∈ Y --- плтёжня функция. Почти всегда будем предполагать, что X и Y --- компктное множество в конечномерном евклидовом прострнствее. |
- | Как | + | Как происх игра: первый игров принимет стртегию x, второй --- y и выч. K(x, y). И выигрыш первого игрока --- K(x, y), выигрыш второго --- -K(x, y). В этом и закл. антагонизм, поск. дин хчет макс. K, другой --- минимизировать. Как искать стратегию 1 игроку --- если бы он знал, какую стртегию выберет второй игрок. то задча свелась к максимизции функции. Но мы будем рассм. случай, кгд каждый игрок не знет, какую стратегию выберет второй. Получилась неопр. И надо понять, что в этм случае делть. В основе принятия решений в этом случае лежит метд, рзщрб. Г., лежитм метд нилуч. гарант. рез-та. В этм случае, каждый игрок выбирает стртегию, которая приносит мкс. выигрыш в худшем случае. |
- | Рассмотрим | + | Рассмотрим чстный случай, кторый позв. понять суть метода --- когда X и Y --- конечные множества. Будем считать, что все стратегии занумерованы от 1 д n и от 1 до m соответственно. И платёжную функцию буждем обозн. как K(i, j), i = 1..n, j = 1..m. Посмотрим, как работает принцип наилуч. гарант. рез-та: предп, что игрок выбрал стратегию i. Тогда его выигрыш будет в худшем случае min_j K(i, j), j=1..m. В этм случае он джолжен его мкксимизировать, то есть max_i min_j K(i, j)= min_j K(i_0, j). Эта стратегия существует, мкксимум есть, таких стратегий мжет быть неск., и любая ткая стратегия принесёт ему лучший результат. Эту стртегию будем обозн. _I_, нижней ценой игры, нижнее значение игры. |
- | Второй игрок. | + | Второй игрок. Предп, он принял стратегоию j. Худший для него вариант --- max_j K(i, j), j=1..m. Выбирать н будет стртегию, которая минимизирует этот максимум --- min_i max_j K(i, j)= max_j K(i, j_0). Эта стртегия сущ., минимум есть, Эту стртегию будем обзн. верхней ценой игры ~I~. |
- | + | Теорем 1. _I_ ≤ ~I~. Математически это доказывается просто. Зафикс. произв. пару i, j. min_j K(i, j) ≤ K(i, j) ≤ max_i K(i, j). Отсюда следует, что min_j K(i, j) ≤ max_i K(i, j) при всех i, j. Если это верно при всех i, то мжно взять максимуи, и он будет верен при любой правой части: max_i min_j K(i, j) ≤ max_i K(i, j). Вспоним также, что это соотн. верно при любых j, тогда можно взяьт мирнимум по j, и получаем _I_ ≤ ~I~. | |
- | Посмотрим смысловую | + | Посмотрим смысловую чсть теоремы. Нижняя цена --- тот выигрыш, который грантировн первому игроку, когда он не знает, как действует второй. Теперь посмотрим на верхнюю цену, это лучшая цена для второго игрка, но можно интерп. иначе: пусть первый игрок всегда знает, как действует втрой, то есть, он знает j. Тогда он будет искать max_i K(i, j), и тогда в худшем случае он плоучит min_j max_i K(i, j), то есть, ~I~. То есть, кгда игрок знет действия противника, то его выигрыш будет не меньше, чем кгда он знает. |
- | + | Рзность ~I~ - _I_ называется ценой инфрмции. Если верх. и ниж. цены совп., то игроку нет никакой разницы, будут его инф. или нет. А если разность больше нуля, то инфй. имеет цену. | |
- | Рассмотрим примеры. Конечные игры они | + | Рассмотрим примеры. Конечные игры они здаются в иде матрицы. Рассм. ткй пример: |
{| | {| | ||
|1 | |1 | ||
Строка 27: | Строка 27: | ||
|1 | |1 | ||
|} | |} | ||
- | Номер строки --- стратегия первого игрока, номер столбца --- | + | Номер строки --- стратегия первого игрока, номер столбца --- стртегия второго. То есть, i=1..2, j=1..3. Как будет действ. первый игрок в усл. неопри.: Если первый игрок применяет первую стртегию, то он длжен рассчитывать на худший выигрыш, на 0, в втором случае получае 1. Тгда по принципу нилучш. гарант. рез-та н выбирает вторую стратегию, и нижняя граница --- 1. |
- | + | Втрой игрок. Если применит первую, то проигрыш 2 ед., если вторую --- 4 единицы, если третью --- 1 единица. В такм случае ~I~ = 1. Здесь _I_ = ~I~ | |
Рассмотрим ещё одни пример: | Рассмотрим ещё одни пример: | ||
Строка 43: | Строка 43: | ||
_I_ = 1, ~I~ = 2. Здесь уже _I_ < ~I~ | _I_ = 1, ~I~ = 2. Здесь уже _I_ < ~I~ | ||
- | Перейдём к случаю, кгда X, Y --- | + | Перейдём к случаю, кгда X, Y --- беск. множества. |
- | В | + | В этм случае первый игрок мжет раск. на выигрыш inf_y ∈ Y K(x, y). Чт должен делать игрок --- макс. эту вел-ну, и она в итоге наз. нижней ценой _I_. Пусть супремум достигется в x_0, то есть _I_ = inf_y ∈ Y K(x_0, y). Аналогично для второго игрока inf_y ∈ Y sup_x ∈ X K(x, y) = ~I~ = sup_x ∈ X K(x, y_0) |
- | + | Терема 2. Аналогична первой, кторую мы доказали: _I_ ≤ ~I~ в случае беск. ант. игр. | |
- | + | Док-во. | |
* inf_y ∈ Y K(x, y) ≤ K(x, y) ≤ sup_x ∈ X K(x, y) | * inf_y ∈ Y K(x, y) ≤ K(x, y) ≤ sup_x ∈ X K(x, y) | ||
* inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y) | * inf_y ∈ Y K(x, y) ≤ sup_x ∈ X K(x, y) | ||
Строка 55: | Строка 55: | ||
* _I_ ≤ ~I~ | * _I_ ≤ ~I~ | ||
- | + | Терема 3. Если K(x, y) --- непр. на X×Y функция, где X, Y --- компакты, то такие функции _w_(x) = min_{y ∈ Y} K(x, y) и ~w~(x) = max_{x ∈ X} K(x, y) --- нерперывны. | |
- | + | Эт позволит писать min/max вместо inf/sup. | |
Докажем первую часть. | Докажем первую часть. | ||
- | + | Поск ... непр, то ∀ ε > 0: ∃ δ ρ((x_1, y_1), (x_2, y_2)) ≤ δ ⇒ |K(x_1, y_1) - K(x_2, y_2)| ≤ ε | |
- | + | Зафикс. ε > 0. δ gt; 0 x_!, x_2 ∈ X,: ρ(x_!, x_2) ≤ δ | |
min_{y ∈ Y} K(x, y) = K(x_1, y(x)) | min_{y ∈ Y} K(x, y) = K(x_1, y(x)) | ||
Строка 69: | Строка 69: | ||
_w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) ≤ K(x_1, y(x_2)) - K(x_2, y(x_2)) ≤ ε | _w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) ≤ K(x_1, y(x_2)) - K(x_2, y(x_2)) ≤ ε | ||
- | Оценим эту | + | Оценим эту разнсть по=другому: |
- | _w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) & | + | _w_(x_1) - _w_(x_2) = K(x_1, y(x_1)) - K(x_2, y(x_2)) ≤ K(x_1, y(x_2)) - K(x_1, y(x_2)) ≥ -ε |
- | Из этих двух сотношений получили то, что | + | Из этих двух сотношений получили то, что хтели: |_w_(x_1) - _w_(x_2)| ≤ ε, отсвюда следует, что _w_ непр. по X. |
Следствие. Если _w_, ~w~ непрерывны, то нижняя цена _I_ = max_{x ∈ X} min_{y ∈ Y} K(x, y), аналогично ~I~ = min_{y ∈ Y} max_{x ∈ X} K(x, y) | Следствие. Если _w_, ~w~ непрерывны, то нижняя цена _I_ = max_{x ∈ X} min_{y ∈ Y} K(x, y), аналогично ~I~ = min_{y ∈ Y} max_{x ∈ X} K(x, y) | ||
- | Перейдём к одному из | + | Перейдём к одному из основополгающих понятий теории АИ --- понятие седловой точки. |
- | Мы | + | Мы рассм. АИ на мн. стратегий X×Y. |
- | + | Пра (x, y) наз. седловой точкой игры (функции), если K(x, y_0) ≤ K(x_0, y_0) ≤ K(x_0, y) при всех ∀ x ∈ X, y ∈ Y. | |
- | Что | + | Что озн. наличие седл. точки: если первый игрок будет откл. от x_0, то его выигрыш может только уменьш, а если вторй игр. будет откл., то его проигрыш будет тлько увел. |
- | Сейчас мы докажем, что это и есть оптимальные стратегии, и цена | + | Сейчас мы докажем, что это и есть оптимальные стратегии, и цена инф. равна 0. А если силовой точки нет, т верхняя цена оказывается строго больше нижней, и цена инф. строго неотр. |
- | Рассмотрим | + | Рассмотрим случайк конечнй игры и перепишем усл. седловй точки: K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) при ∀ i = 1..n, j = 1..m. |
Рассмотрим следующую платёжную матрицу: | Рассмотрим следующую платёжную матрицу: | ||
{| | {| | ||
|1 | |1 | ||
- | | -3 | + | |-3 |
- | | -2 | + | |-2 |
|- | |- | ||
|1 | |1 | ||
Строка 104: | Строка 104: | ||
|} | |} | ||
- | + | Чт такое седл. элемент --- элемент, кторый максимальный в стлбце и минимальный в строке. В данной матрице элемент (i=3, j=1) минимален. Теперь в этой матрице обр. внимание на следующее: вычислим _I_ и ~I~: _I_ = 2, ~I~ = 2. Здесь верхняя цена равна нижней. | |
- | Теперь | + | Теперь рассм. другую матрицу: |
2 3 4 1 | 2 3 4 1 | ||
5 2 2 3 | 5 2 2 3 | ||
4 1 3 2 | 4 1 3 2 | ||
- | Оценим здесь _I_ и ~I~: _I_ = 2, ~I~ = 3. Здесь | + | Оценим здесь _I_ и ~I~: _I_ = 2, ~I~ = 3. Здесь верх. цена оказалась больше, чем нижняя. |
- | Обобщим это: если | + | Обобщим это: если седл. тчка сущ., т цены совп, иначе верх. бльше нижней. |
- | + | Теорема 4. В матричной ант. игре седлвая точка существует тогда и только тогда, когда _I_=~I~. Если (i_0, j_0) --- силовая точка, то K(i_0, j_0) = _I_=~I~. И i_0, j_0 --- наилучшие гарант. стратегии. | |
- | + | Доказательство. Первя часть. a) Предпложим, чт нижняя цена равна верхней. Пусть i_0 и j_0 --- оптимальные гарант. стратегии. Тогда из опр. имеем следующее: max_i min_j K(i, j) = min_j K(i_0, j). Это нижняя цена игры. В свю чередь, min_j K(i_0, j) ≤ K(i_0, j). В свю очередь, ~I~ = min_j max_i K(i, j) = max_i K(i, j_0) и поск. мы ерём максимум, то Kmax_i K(i, j_0) ≥ K(i, j_0). Но _I_ = ~I~, тогда K(i, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m. Покажем, что i_0, j_0 --- седловя точка. Откуда это следует? но верн при всех i, в частнсти, при i_0: i=i_0: K(i_0, j_0) ≤ K(i_0, j), оно верно при j=j_0: K(i, j_0) ≤ K(i_0, j_0). Отсюда получаем K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m, то есть (i_0, j_0) --- седловая точка. | |
- | Вторая часть первой части | + | Вторая часть первой части теремы. Необх. условие. (i_0, j_0) --- седловая точка. Тогда по определению K(i, j_0) ≤ K(i_0, j_0) ≤ K(i_0, j) ∀ i = 1..n, j = 1..m |
* max_i K(i, j_0) ≤ K(i_0, j_0) ≤ min_j K(i_0, j) | * max_i K(i, j_0) ≤ K(i_0, j_0) ≤ min_j K(i_0, j) | ||
* min_j max_i K(i, j) ≤ K(i_0, j_0) ≤ max_i min_j K(i, j) | * min_j max_i K(i, j) ≤ K(i_0, j_0) ≤ max_i min_j K(i, j) | ||
* ~I~ ≤ _I_ | * ~I~ ≤ _I_ | ||
- | Но мы знаем | + | Но мы знаем терему 1, из которой _I_ ≤ ~I~, тсюда _I_=~I~ |
- | Первая | + | Первая чсть теор. доказана полностью. Псмтрим, что мы плучили. Поск. _I_=~I~ то там везде имеет место равенство, и, таким бразом, мы доказали вторую чсть теоремы. |
- | + | Теорема 5. Если ∃ стртегии i_0, j_0 и константа ''v'' такие, что K(i, j_0) ≤ ''v'' ≤ K(i_0, j) при ∀ i=1..n, j=1..m, то пара i_0, j_0 обр. седл. точку и ''v'' = K(i_0, j_0) | |
- | + | Доказательство. Из усл. теоремы следует, чт K(i, j_0) ≤ K(i_0, j) при ∀ i=1..n, j=1..m, а мы только что доказали, что из этого следует, что (i_0, j_0) --- седловая точка. Т.о. дказхали первую чсть. | |
- | + | Поск. можно взять i,j любые, т мжн взять i=i_0, j=j_0, и получаем K(i_0, j_0) ≤ ''v'' ≤ K(i_0, j_0) ⇒ ''v'' = K(i_0, j_0) | |
- | На этом с | + | На этом с матр. играми пока всё. Взвр. к беск. играм. |
Рассматриваем K(x, y) на X×Y. | Рассматриваем K(x, y) на X×Y. | ||
- | + | Теорем 6. Игра K(x, y) имеет седл. тчку т. и тт., когда max_{x ∈ X} inf_{y ∈ Y} K(x, y) = min_{y ∈ Y} sup_{x ∈ X} K(x, y) (то есть тчка эта дстигется). 2) (x_0, y_0) -- ct ⇒ K(x_0, y_0) = max_x inf_y K(x, y) = min_y sup_x K(x, y) | |
- | + | Доказательство. 1) x_0, y_0. min_x inf_y K(x, y) = inf_y K(x_0, y) ≤ K(x_0, y) ∀ y ∈ Y | |
* min_y sup_x K(x, y) = sup_x K(x, y_0) ≥ K(x, y_0), ∀ x ∈ X | * min_y sup_x K(x, y) = sup_x K(x, y_0) ≥ K(x, y_0), ∀ x ∈ X | ||
- | * Эти две вещи равны, | + | * Эти две вещи равны, пэтму полчуаем K(x, y_0) ≤ K(x_0, y) ∀ x ∈ X, y ∈ Y |
* x=x_0: K(x_0, y_0) ≤ K(x_0, y) | * x=x_0: K(x_0, y_0) ≤ K(x_0, y) | ||
* y=y_0: K(x, y_0) ≤ K(x_0, y_0) | * y=y_0: K(x, y_0) ≤ K(x_0, y_0) | ||
- | + | тсюда СТ. | |
2) (x_0, y_0) --- СТ | 2) (x_0, y_0) --- СТ | ||
- | * ( | + | * (аналгично Т4) |
- | Что мы получили, на самом деле. Мы на самом деле | + | Что мы получили, на самом деле. Мы на самом деле плучили равенство. Что это означает? Это означает, что ... |
* (аналогично Т4) | * (аналогично Т4) | ||
- | Это | + | Это озн., чт inf достигется в y=y_0, указнный supдостигается при x=x_0. Это значит, что мы мжем записать min_y sup_x K(x, y) = max_x inf_y K(x, y) |
+ | |||
+ | Т.. теорема ок. плностью. | ||
- | + | <!-- перерыв --> | |
(Про экзамен) <!-- лектор - мудак --> | (Про экзамен) <!-- лектор - мудак --> | ||
Строка 184: | Строка 186: | ||
K(x, y) = 1 - (x-y)^2 X=Y=[0, 1] | K(x, y) = 1 - (x-y)^2 X=Y=[0, 1] | ||
- | _w_(x) = min_{y ∈ [0, 1]} = {1-x^2, x > 0.5 (y=0); 1-(1-x)^2, x≤ 0.5 (y=1)} Теперь он должен взять максимум от этой величины. | + | _w_(x) = min_{y ∈ [0, 1]} = {1-x^2, x > 0.5 (y=0); 1-(1-x)^2, x≤ 0.5 (y=1)} Теперь он должен взять максимум от этой величины. Псмтрим графически, что здесь плучется. То есть, наилуч. стратиегия для первог игрока --- x_0 = 1/2. Это в случае, когд игрок не информирован. |
- | Заметим, что здесь же мы описали, как будет действовать второй игрок, | + | Заметим, что здесь же мы описали, как будет действовать второй игрок, когд он информирован. |
- | Как должен действовать, как будет | + | Как должен действовать, как будет дейтсввать второй, когд он не инфрмирован (как должен действовать первый, когд он информирован). |
* 1-x^2=1-(1-x)^2 | * 1-x^2=1-(1-x)^2 | ||
Строка 196: | Строка 198: | ||
~w~(y) = max_y | ~w~(y) = max_y | ||
- | Получили, что ~w~ > _w_, | + | Получили, что ~w~ > _w_, значмит, седловой тчки нет. |
- | Следующие | + | Следующие дв примера более конкретны. Они имеют в литературе название "дуэльные игры". |
- | Первая дуэль | + | Первая дуэль назывется "бесшумная дуэль". Два игрока сближаются и могут произвести один выстрел. Произвести выстрелы они могут в сомент времени x,y ∈ [0, 1]. Дальше известны функции меткости: p(x), q(y). Что таке p(x) --- вероятнсть поржения первым игроком вторго игрока, если он произв. выстрел в ммент времени x. Функция меткости возрастающая. |
- | Платёж следующий: 1, если 1 игрок | + | Платёж следующий: 1, если 1 игрок празил второго, -1 если наоборот, 0 в двух стльных случаях. Берётся матожидание. Если x<y, т есть первый игрк стреляет первым. Вспомним, что такое матжидание --- берётся сумма произв. арг. на вер. То есть, 1*p(x) + (1-p(x))*q(y)*(-1) + 0 * (...) В итоге получается p(x) - (1-p(x))*q(y) (кгда x<y). Когда x=y, то получаем p(x)(1-q(x)) - (1-p(x))q(x). Когда x>y, полоучается -q(y)+(1-q(y))p(x). |
- | Эти дуэли бесшумные, | + | Эти дуэли бесшумные, поск. если первый игрк произв. выстрел и промхивается, то втрй игрок это не слышал. В шумняых, если первый выстрелил и прмазал, то второй будет стрелять не в момент времени y, а в момент 1, когда верятность макс.. В случае, если p(x) = x, q(y) = y, получим |
x-y+xy, x<y | x-y+xy, x<y | ||
K(x, y) = 0, x=y | K(x, y) = 0, x=y | ||
Строка 210: | Строка 212: | ||
Посчитаем выигрыш. стратегии. | Посчитаем выигрыш. стратегии. | ||
- | + | Рассм, как выглядит функция при фикс. x. | |
_w_(x) = inf_y K(x, y) = min(-x_2, 2x-1), max_x _w_(x) | _w_(x) = inf_y K(x, y) = min(-x_2, 2x-1), max_x _w_(x) | ||
- | x=sqrt(2)-1 --- | + | x=sqrt(2)-1 --- опт. знач. джля первого игрока, и нижняя цена игрока _I_=2sqrt(2)-3, если то же саме повторить за второго игрока, т полочим, что ~I~=3-2sqrt(2) и y=sqrt(2)-1 |
+ | |||
+ | <!-- педедыв --> | ||
- | Вторая модель --- шумная дуэль. | + | Вторая модель --- шумная дуэль. Отличется от бесшумнй только тем, чт если один из игроков произв. выстрел и прмахивается, то второй игрок об этом узнаёт. Поэтому, когдо он узнаёт, то стрелять он будет в ммент, когда будет максимально, в момент 1. |
Посчитаем вероятности: | Посчитаем вероятности: | ||
Строка 236: | Строка 240: | ||
Аналогично для первого игрока _I_=0, x=1/2 | Аналогично для первого игрока _I_=0, x=1/2 | ||
- | + | Плучили седловую точку (1/2, 1/2). | |
- | Игра с | + | Игра с ... времени. Есть два игрока --- пдлодка и обороняемый объект. Игра присх. след. обрзом: подлдка всплываем, а объект в момент времени y выпуск. осветительную ракету освещает акватриум на отрезке y, y+d, если лодка всплывёт в этом интервале, то она будет уничтжена, иначе она уничт. объект. Если лодка уничт. бъект, то платёж 1, иначе платеж 0 |
- | Здесь | + | Здесь плат. функция выглядит след. образом: |
1, x<y или y > y+d | 1, x<y или y > y+d | ||
K(x, y) = 0, x ∈ [y, y+d] | K(x, y) = 0, x ∈ [y, y+d] | ||
- | В | + | В любй момент минимум 0, пэтому Нижняя цена равна 0, поэтму птимальным является любй момент. То же для втрого игрока --- в любом случае максимум 1, ~I~=1, тчка любая, и седловой точки здесь нет. |
- | + | Перехдим к вопросу, связанному с существованию седловых точек. Покжем алгоритм поиска седловых точек. Сейчас более глубок изучим этт вопрос. Для этг понадобится вспомнить нек-рые утверждения из мат. анализа, связнные с вып. функций. | |
- | + | Определение 1. Мнжество Y называется выпуклым, если &orall; y_1, y_2 ∈ Y, α ∈ (0,1): αy1+(1-α)y_2 ∈ Y. | |
- | + | Определение 2.1 Функция f(y), y∈ Y наз. выпуклой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) ≤ αf(y1)+(1-α)f(y_2) | |
- | + | Опр. 2.2 Функция f(y), y∈ Y наз. строго выпуклой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) < αf(y1)+(1-α)f(y_2) | |
- | + | Определение 2.3 Функция f(y), y∈ Y наз. вогнутой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) ≥ αf(y1)+(1-α)f(y_2) | |
- | + | Опр. 2.4 Функция f(y), y∈ Y наз. строго вогнутой, если для ∀ y_!, y_2 ∈ Y (y_1 ≠ y_2) , α ∈ (0, 1), f(αy1+(1-α)y_2) > αf(y1)+(1-α)f(y_2) | |
Утверждения. | Утверждения. | ||
* Сумма двух выпуклых функций есть выпуклая функция | * Сумма двух выпуклых функций есть выпуклая функция | ||
- | * Сумма | + | * Сумма вып. и строго вып. --- строго вып. |
- | * Аналогично для | + | * Аналогично для вгнутых. |
- | Доказать | + | Доказать самост. |
- | * Строго | + | * Строго вып. функция на вып. м-ве имеет ровно дну тчку минимума |
- | * Строго | + | * Строго вогн. функция на вып. мн-ве имеет ровно одну т. максимума |
- | Пусть дана f(x), x --- вектор (x_1, ..., x_n), если f ' '(x) --- | + | Пусть дана f(x), x --- вектор (x_1, ..., x_n), если f''(x) --- неотр. опред. фрма, то f(x) явл. вып. функцией. Если плож., то строго вып. Если неполож. опр., то вогнутая, если отрицательно опр., то строго вгнутая. |
- | Рассмотрим пример. f(x_1, ..., x_n) = x_1^2 + x_2^2 + ... + x_n^2. Пкажем, что | + | Рассмотрим пример. f(x_1, ..., x_n) = x_1^2 + x_2^2 + ... + x_n^2. Пкажем, что эт строго вып. функция. Найдём f'(x) = (δf/δx_1, ..., δf/δx_n)=(2x_1, ..., 2x_n). |
( δ^2f/δx_1δx_1, ..., δ^2f/δx_1δx_n ) (2 ... 0 ) | ( δ^2f/δx_1δx_1, ..., δ^2f/δx_1δx_n ) (2 ... 0 ) | ||
f''(x)=( ... ) = ( ... ) | f''(x)=( ... ) = ( ... ) | ||
( δ^2f/δx_nδx_1, ..., δ^2f/δx_nδx_n ) (0 ... 2 ) | ( δ^2f/δx_nδx_1, ..., δ^2f/δx_nδx_n ) (0 ... 2 ) | ||
- | Эта | + | Эта фрма полож. опр. Значит, функция строго вып. |
{{Тигры}} | {{Тигры}} | ||
+ | {{Lection-stub}} |