Максимум линейной функции на выпуклом компакте, угловая точк

[hol23]

Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке (такой точке, которая не представима в виде линейной комбинации точек, сумма коэффициентов при которых - единица)?
Если рассуждать от противного, у меня выходит лишь вот что:
$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 из множества, то есть никакого противоречия нет.

[ewert]

hol23 в сообщении #360838 писал(а):

Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке

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

[hol23]

О, ясно, у меня именно это и не клеилось. Спасибо!

[moscwicz]

hol23 в сообщении #360838 писал(а):

Почему линейная функция, заданная на выпуклом компакте, достигает максимум в некоторой угловой точке

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

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

[Профессор Снэйп]

И всё-таки, что такое "угловая точка" выпуклого множества? Точка, которая совпадает с одним из концов любого отрезка, лежащего в нашем выпуклом множестве и содержащего эту точку? Либо что-то другое?

[Padawan]

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

[Профессор Снэйп]

А зачем тогда Крейн-Мильман? Ограничение линейного функционала на отрезок --- линейная функция на одномерном пространстве...

-- Пн окт 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)$.

[ewert]

Профессор Снэйп в сообщении #361033 писал(а):

Ограничение линейного функционала на отрезок

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

hol23 в сообщении #360838 писал(а):

Если рассуждать от противного, у меня выходит лишь вот что:

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

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

Профессор Снэйп в сообщении #361033 писал(а):

у каждого компактного выпуклого множества есть угловая точка.

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

Профессор Снэйп в сообщении #361033 писал(а):

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

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

[Padawan]

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$ найдется крайняя точка.

[ewert]

Padawan в сообщении #361049 писал(а):

Профессор Снэйп в сообщении #361033 писал(а):

А зачем тогда Крейн-Мильман?

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

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

[Профессор Снэйп]

ewert в сообщении #361054 писал(а):

просто потихоньку сдуваем-раздуваем шарик.

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

ewert в сообщении #361054 писал(а):

Правда, в нестрого нормированном -- не знаю...

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

ewert в сообщении #361039 писал(а):

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

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

[moscwicz]

Утв. Пусть $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$ закладывать не надо.

[ewert]

Профессор Снэйп в сообщении #361066 писал(а):

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

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

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