2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: экстремальные точки множества
Сообщение14.09.2010, 22:54 
Аватара пользователя
Alexey1 в сообщении #352421 писал(а):
Эта точка множества которая не может быть представлена как линейная комбинация двух других точек множества, то есть $x$ - экстремальная точка $X$, если $\not{\exists} z,y \in X, \ \not \exists \lambda \in (0,1), \ x = \lambda z+(1-\lambda)y$.

ну да)) только, кажется, такие точки называются "крайними"... как в теореме Крейна-Мильмана

А решение: афинный образ выпуклой оболочки конечного числа точек есть выпуклая оболочка образов этих точек...

 
 
 
 Re: экстремальные точки множества
Сообщение15.09.2010, 02:29 
Да, но автор темы хочет знать при каких условиях на матрицу $A$ экстремальные точки множества $Y$ соответствуют экстремальным точкам множества $X$. Понятно, что $A$ здесь не может быть произвольной. Например, если
$X=\{(x_1,x_2) \ : \ x_1,x_2 \geq 0, \ x_1+x_2 \leq 1\}$,
$A=\left[\begin{array}{ll}
1 & 1\\
0 & 0\\
\end{array}\right]$,
тогда $Y=\{y \in \mathbb R^2 \ : \ y=Ax, \ x \in X\}$ есть просто множество $[0,1]$ (компонента $y_1$) с двумя экстремальными точками $\{0,1\}$, и все точки множества $X$ удовлетворяющие уравнению $x_1+x_2=1$ (среди этих точек только две экстремальных $\{(1,0),(0,1)\}$) отображаются в точку $1$.

 
 
 
 Re: экстремальные точки множества
Сообщение15.09.2010, 18:45 
Аватара пользователя
Alexey1 в сообщении #352607 писал(а):
Да, но автор темы хочет знать при каких условиях на матрицу $A$ экстремальные точки множества $Y$ соответствуют экстремальным точкам множества $X$.

Ответ на этот вопрос: ${\rm{rk}}\,A=n$,
но я так понял, что автор темы хочет ДОКАЗАТЬ, что в прообразе экстремальной точки при линейном отображении всегда найдется экстремальная точка.

 
 
 
 Re: экстремальные точки множества
Сообщение15.09.2010, 21:02 
Если прочитать только это,
Anya90 в сообщении #351801 писал(а):
Нужно доказать, что если $y$ - экстремальная точка $Y$, то $y=Ax$, где $x$ - экстремальная точка $X$.
то можно подумать так как подумали Вы. Но вот после этого,
Anya90 в сообщении #351801 писал(а):
Рассуждения: предположим противное, т.е. $y$ - экстремальная точка $Y$, $y=Ax$, но здесь $x$ не является экстремальной точкой $X$.
следует, что если $y$ экстремальная точка, то $x$ тоже экстремальная точка.
Я пытался узнать, что надо сделать, доказать утверждение или подогнать утверждение под доказательство, но автор сообщения на это не ответил.

 
 
 
 Re: экстремальные точки множества
Сообщение15.09.2010, 21:43 
Аватара пользователя
Alexey1 в сообщении #352841 писал(а):
Я пытался узнать, что надо сделать, доказать утверждение или подогнать утверждение под доказательство, но автор сообщения на это не ответил.

мне кажется разумным доказывать исходное утверждение, потому что про $A$ там ничего не спрашивается... да и в приведенном "доказательстве" имеется типичная ошибка первокурсника (квантор всеобщности вместо квантора существования)

 
 
 
 Re: экстремальные точки множества
Сообщение15.09.2010, 23:02 
По вопросам которые задавались, складывается впечатление, что надо понять именно данное доказательство. В частности,
Anya90 в сообщении #351801 писал(а):
В этом доказательстве мне непонятно, как мы можем знать, что $Ax_1\neq Ax_2$. Кто-нибудь может помочь? Спасибо.
Но в любом случае, это уже болтовня пошла.

 
 
 
 Re: экстремальные точки множества
Сообщение18.09.2010, 02:07 
Спасибо всем за участие в теме и помощь, хоть для меня задача так и осталась нерешенной. Я осознала, правда, что в данном случае матрица $A$ может быть и с абсолютно одинаковыми элементами, т.е. линейная независимость столбцов не гарантирована.
Ограничения на матрицу: сумма элементов каждого столбца = 1, все элементы из отрезка [0,1].
Доказать нужно, как и написано, что если $y$ - экстремальная точка $Y$, то $Y=Ax$, где $x$ - экстремальная точка $X$.

Как в таком случае доказать, что $x$ - экстремальная точка, мне непонятно. Доказательство, которое приводилось, - это совместная попытка (моя и подруги), но меня озадачил тот факт, что $Ax_1$ м.б. равно $Ax_2$. Так что не знаю, как это назвать - решением задачи или подгонкой под ответ.
Ответ-то понятен - $x$ д.б. экстремальной точкой, только непонятно, как это доказать.

paha в сообщении #352556 писал(а):
А решение: афинный образ выпуклой оболочки конечного числа точек есть выпуклая оболочка образов этих точек...


Простите, я получаю инженерное (а не классическое математическое) образование, и эта фраза мне непонятна вообще.
Все, что нам давали пока, - это определение выпуклых множеств и экстремальных точек. Нельзя ли как-то попроще это переформулировать для "чайников"?

 
 
 
 Re: экстремальные точки множества
Сообщение18.09.2010, 12:06 
Аватара пользователя
Ну, смотрите. Крайние точки множества $X$ -- это начало координат и точки $A_i=(0,\ldots,0,K,0,\ldots,0)$ (все координаты нулевые, кроме $i$-ой, которая равна $K$). Обозначим $e_i=OA_i$ -- эти $n$ векторов образуют базис в $\mathbb{R}^n$. Любая точка множества $X$ имеет вид $x=\sum t_ie_i$, где $t_i\in [0;1]$, т.е. $X$ -- выпуклая оболочка своих (крайних) точек $O,e_1,e_2,\ldots,e_n$.

Таким образом $y=Ax=\sum t_i (Ae_i)$ -- множество $Y$ является выпуклой оболочкой точек $O,Ae_1,Ae_2,\ldots,Ae_n$, среди которых ВСЕ крайние.

-- Сб сен 18, 2010 13:08:04 --

в прообразе крайней точки могут быть и не крайние... Но крайние обязательно найдутся

 
 
 
 Re: экстремальные точки множества
Сообщение18.09.2010, 19:10 
Спасибо большое за ответ. Понятно все до слов:

paha в сообщении #353687 писал(а):
Таким образом $y=Ax=\sum t_i (Ae_i)$ -- множество $Y$ является выпуклой оболочкой точек $O,Ae_1,Ae_2,\ldots,Ae_n$, среди которых ВСЕ крайние.


Ясно, что $Y$ - выпуклая оболочка точек $O,Ae_1,Ae_2,\ldots,Ae_n$, но непонятно, почему среди них ВСЕ крайние.

Когда я пробую это на примерах - да, все так и получается, но как это доказывается в общем случае?

 
 
 [ Сообщений: 24 ]  На страницу Пред.  1, 2


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