2014 dxdy logo

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

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




 
 Минимизация функции на выпуклом множестве
Сообщение27.05.2009, 17:11 
Аватара пользователя
Закоротило, месяц назад это казалось мне очевидным, но теперь не могу вспомнить почему это так.
Функция $f:\mathbb R^n \rightarrow \mathbb R$ выпуклая, множество $\Omega$ выпукло.
Доказать, что в $(f'(x^*),x-x^*)\ge0  \forall x\in\Omega$ (скалярное произведение) - достаточное условие минимума $f(x)$ в точке $x^*$ на этом множестве.

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 17:40 
Аватара пользователя
Здесь производная функции- это ее градиент, он сам и все направления, образующие с ним нетупой угол, указывают направления неубывания функции.
Выписанное Вами условие как раз и означает, что, отправляясь от данной точки в множество по любому возможному направлению, мы обязательно идем по направлению неубывания функции.

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 17:56 
Аватара пользователя
Brukvalub в сообщении #217626 писал(а):
Здесь производная функции- это ее градиент, он сам и все направления, образующие с ним нетупой угол, указывают направления неубывания функции.
Выписанное Вами условие как раз и означает, что, отправляясь от данной точки в множество по любому возможному направлению, мы обязательно идем по направлению неубывания функции.

но тогда ведь не нужна выпуклость функции :?

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 17:59 
Аватара пользователя
Тогда, возможно, штришок сверху справа от функции означает не градиент, а какой-нибудь иной объект, присущий именно выпуклым функциям, типа субдифференциала?

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 18:06 
Аватара пользователя
Brukvalub в сообщении #217632 писал(а):
Тогда, возможно, штришок сверху справа от функции означает не градиент, а какой-нибудь иной объект, присущий именно выпуклым функциям, типа субдифференциала?

это градиент (в том смысле, что функция дифференцируема, если ее приращение представимо в виде $f(u+h)-f(u)=(f'(u),h)+o(u,h)$)
В общем случае, вышеуказанное неравенство - необходимое условие. А вот в случае выпуклой функции еще и достаточное. У меня есть пометка, что это прямым образом следует из выпуклости функции. Но как именно - не помню :D

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 19:11 
Аватара пользователя
Тогда так: перепишем условие выпуклости в виде $\[f(x + t(z - x)) - f(x) \le t(f(z) - f(x))\;;\;0 < t \le 1.\]$
Из дифференцируемости, скажем, по Гато, следует, что
$\[\left\langle {f'(x)\;,\;t(z - x)} \right\rangle  + \bar o_{(z - x)} (t) \le t(f(z) - f(x))\]$. Деля обе части на t и переходя к пределу, получаем неравенство $\[
\left\langle {f'(x)\;,\;(z - x)} \right\rangle  \le f(z) - f(x)
\]$
, что и доказывает достаточность условия для выпуклой функции.

 
 
 
 Re: Минимизация гладкой функции на выпуклом мн-ве
Сообщение27.05.2009, 20:37 
Аватара пользователя
Brukvalub в сообщении #217643 писал(а):
Тогда так: перепишем условие выпуклости в виде $\[f(x + t(z - x)) - f(x) \le t(f(z) - f(x))\;;\;0 < t \le 1.\]$
Из дифференцируемости, скажем, по Гато, следует, что
$\[\left\langle {f'(x)\;,\;t(z - x)} \right\rangle  + \bar o_{(z - x)} (t) \le t(f(z) - f(x))\]$. Деля обе части на t и переходя к пределу, получаем неравенство $\[
\left\langle {f'(x)\;,\;(z - x)} \right\rangle  \le f(z) - f(x)
\]$
, что и доказывает достаточность условия для выпуклой функции.

тоже сойдет, спасибо )

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


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