2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Максимум линейной функции на выпуклом компакте, угловая точк
Сообщение10.10.2010, 21:07 
Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке (такой точке, которая не представима в виде линейной комбинации точек, сумма коэффициентов при которых - единица)?
Если рассуждать от противного, у меня выходит лишь вот что:
$x_0$ - точка максимума, не является угловой, след. $x_0=ax_1+(1-a)x_2$, тогда $f(x_0)=af(x_1)+(1-a)f(x_2)\leqslant \max  f(x), $ по всем x из множества, то есть никакого противоречия нет.

 
 
 
 Re: Угловая точка
Сообщение10.10.2010, 21:11 
hol23 в сообщении #360838 писал(а):
Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке

А это просто неправда. Это правда лишь тогда, когда тот компакт -- не просто компакт, но некий многогранник.

 
 
 
 Re: Угловая точка
Сообщение10.10.2010, 21:21 
О, ясно, у меня именно это и не клеилось. Спасибо!

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 08:26 
hol23 в сообщении #360838 писал(а):
Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке

Утверждение верное. Используйте теорему Крейна-Мильмана

-- Mon Oct 11, 2010 09:26:52 --


 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 10:22 
Аватара пользователя
И всё-таки, что такое "угловая точка" выпуклого множества? Точка, которая совпадает с одним из концов любого отрезка, лежащего в нашем выпуклом множестве и содержащего эту точку? Либо что-то другое?

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 15:37 
Угловая точка = крайняя точка, т.е. точка не являющаяся внутренней точкой никакого отрезка, лежащего в данном множеств http://en.wikipedia.org/wiki/Extreme_point.

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 16:04 
Аватара пользователя
А зачем тогда Крейн-Мильман? Ограничение линейного функционала на отрезок --- линейная функция на одномерном пространстве...

-- Пн окт 11, 2010 20:09:25 --

Даже не так. Уровень линейного функционала --- аффинное многообразие, и у каждого компактного выпуклого множества есть угловая точка.

-- Пн окт 11, 2010 20:15:20 --

Естественно, данная в задаче линейная функция должна быть непрерывной. Этого в условии нет. А вот требуется ли это по существу --- надо подумать...

Предлагаю такую формулировку задачи. Пусть $X$ --- нормированное пространство, $Y \subseteq X$ --- выпуклое компактное подмножество $X$, $f : X \to \mathbb{R}$ --- линейный функционал (не обязательно непрерывный). Известно, что $f$ достигает максимума на $Y$ (то есть найдётся $y_0 \in Y$, такое что $f(y) \leqslant f(y_0)$ для всех $y \in Y$). Доказать, что найдётся угловая точка $z \in Y$, такая что $f(y_0) = f(z)$.

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 16:18 
Профессор Снэйп в сообщении #361033 писал(а):
Ограничение линейного функционала на отрезок

На какой отрезок?...

hol23 в сообщении #360838 писал(а):
Если рассуждать от противного, у меня выходит лишь вот что:

Да, я врубился (меня сбил с толку странный термин "угловая точка"). Естественно, от противного ничего и не докажешь, т.к. утверждение сформулировано неверно (или Вы неверно его понимаете). Должно быть так: "среди точек, в которых достигается максимум, есть хоть одна угловая".

Тогда всё вроде просто. Пусть $K$ -- компакт и $M$ -- множество всех его точек, в которых достигается максимум, т.е. пересечение $K$ с подпространством $L=\{f(x)=\max\}$. Это -- тоже компакт и, следовательно, содержит хотя бы одну "угловую" (для самого себя) точку. Вот она-то и будет искомой "угловой" точкой также и для $K$, поскольку $K$ лежит по одну из сторон того подпространства $L$.

Профессор Снэйп в сообщении #361033 писал(а):
у каждого компактного выпуклого множества есть угловая точка.

А зачем выпуклого?

Профессор Снэйп в сообщении #361033 писал(а):
Естественно, данная в задаче линейная функция должна быть непрерывной. Этого в условии нет. А вот требуется ли это по существу --- надо подумать...

Видимо, да, иначе максимум может просто вообще не достигаться. Или если даже достигается, то пересечение может не быть компактом.

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 16:49 
ewert в сообщении #361039 писал(а):
Тогда всё вроде просто. Пусть $K$ -- компакт и $M$ -- множество всех его точек, в которых достигается максимум, т.е. пересечение $K$ с подпространством $L=\{f(x)=\max\}$. Это -- тоже компакт и, следовательно, содержит хотя бы одну "угловую" (для самого себя) точку. Вот она-то и будет искомой "угловой" точкой также и для $K$, поскольку $K$ лежит по одну из сторон того подпространства $L$.

(выделение мое)
Позволю себе поясняющий комментарий к Вашему рассуждению. Если бы $x_0$ была внутренней точкой отрезка $[a,b]\subset K$, то так как $f(x_0)$ -- максимум, имеем $f(a)=f(b)=f(x_0)$, а значит, $[a,b]\subset M$. Противоречие с тем, что $x_0$ -- крайняя точка $M$.

Профессор Снэйп в сообщении #361033 писал(а):
А зачем тогда Крейн-Мильман?

Чтобы быть увереным, что у $M$ найдется крайняя точка.

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 17:05 
Padawan в сообщении #361049 писал(а):
Профессор Снэйп в сообщении #361033 писал(а):
А зачем тогда Крейн-Мильман?
Чтобы быть увереным, что у $M$ найдется крайняя точка.

Зависит от того, где мы работаем. В строго нормированном пространстве компакт имеет крайние точки безо всяких теорем -- просто потихоньку сдуваем-раздуваем шарик. Правда, в нестрого нормированном -- не знаю...

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 17:43 
Аватара пользователя
ewert в сообщении #361054 писал(а):
просто потихоньку сдуваем-раздуваем шарик.

Насчёт "раздувания" не совсем понял. Поясните.

ewert в сообщении #361054 писал(а):
Правда, в нестрого нормированном -- не знаю...

А в каком тогда? Мультинормированном? Топологическом, у которого топология согласована со структурой векторного простанства (не помню, каким словом называется)?

ewert в сообщении #361039 писал(а):
Видимо, да, иначе максимум может просто вообще не достигаться. Или если даже достигается, то пересечение может не быть компактом.

Не знаю... Мне кажется, компактность + линейность --- довольно сильное сочетание свойств. Так, например, ограничение линейного функционала на любое конечномерное подмножество непрерывно. А на компактное? Учитывая, что достижимость максимума дана в условии...

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 19:35 
Утв. Пусть $E$ -- локально выпуклое пространство и $K\subset E$ -- выпуклый компакт. Линейная функция $f:E\to\mathbb{R}$ непрерывна. Тогда $f$ достигает максимума на $K$ в крайней точке множе множества $K$.

Док-во. Пусть $x'\in K$ -- точка максимума $f$. По теореме К-М $$x'=\sum_{i=1}^n\psi_ix_i,\quad \psi_1+\ldots+\psi_n=1,\quad \psi_i\ge 0$$
$\{x_i\}$-- крайние точки
После этого задача делается конечномерной: остается заметить, что $f(x')=\max_P f$ где $P$ --
конечномерный многогранник
$$\{u_1x_1+\ldots+u_nx_n\mid u_1+\ldots+u_n=1,\quad u_i\ge 0\}$$
поэтому очевидно, что $f(x')=f(x_k)$ при некотором $k$.

PS Если считать, что максимум существует по условию, то непрерывность $f$ закладывать не надо.

 
 
 
 Re: Угловая точка
Сообщение11.10.2010, 21:19 
Профессор Снэйп в сообщении #361066 писал(а):
Насчёт "раздувания" не совсем понял. Поясните.

Нет, ну банальность имелась в виду. Находим максимум расстояний от начала координат до точек на компакте (он достигается, т.к. расстояние -- непрерывная функция точки). Тогда любая точка, где этот максимум достигается -- крайняя для компакта (если, конечно, норма -- строгая).

А Крейн-Мильман -- не для белого человека. Ну их, этих выборОв.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group