|
bogomol
|
|
old hand
|
|
|
|
|
|
|
Рег.: 26.08.2006
|
|
Сообщений: 813
|
|
|
|
Рейтинг: 1118
|
|
минимум выпуклой вниз функции
03.06.2009 20:23
|
|
|
чем он отличается от минимума обыкновенной?
тем, что на интервале выпуклоси вниз он - единственный, в частности, если ф-я выпукла вниз на всей оси ОХ, то она имеет единственный минимум?
Еще есть какие-нибудь особенности?
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 20:30
|
|
|
У просто выпуклой не один.
Обыкновенная - какая? Полунепрерывная снизу?
Минимизирующее множество выпукло, вот этим отличается.
|
|
|
bogomol
|
|
old hand
|
|
|
|
|
|
|
Рег.: 26.08.2006
|
|
Сообщений: 813
|
|
|
|
Рейтинг: 1118
|
|
|
В ответ на:
Обыкновенная - какая? Полунепрерывная снизу?
например, кусочно-дифференцируемая.
ну вот допустим, мы начали искать минимум функции на интервале, а функция очень геморная. Облегчает ли нам поиск тот факт, что она выпуклая вниз? Или нам известно только то, что минимум на интервале должен быть один, больше ничего?
В ответ на:
Минимизируеющее множество выпукло, вот этим отличается.
как понять эту фразу? То, что множество, на котором мы ищем минимум, выпукло?
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:18
|
|
|
Если ты про функцию одной переменной, строго выпуклую вниз, то есть метод трихотомии. Наверное это то, что тебя интересует.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:24
|
|
|
Quote:
как понять эту фразу? То, что множество, на котором мы ищем минимум, выпукло?
Минимум можно не только на интервалах искать, можно на множествах в пространствах большей размерности, можно вообще на функциональных пространствах, ты же в первом посте не говорил про то, что тебе программа нужна.
Вот рассмотри такую функцию: max{ 0, |x| - 5 }. Она внутри отрезка [-5;5] равна нулю. Она выпуклая. Она кусочно-(черт с ним) дифференцируема. Минимум достигается на всем отрезке [-5; 5]. Этот отрезок - минимизирующее множество. Оно выпукло. Вообще на прямой выпукло равносильно является интервалом, пустым множеством, лучем или прямой. Так вот если функция выпуклая, то по-другому быть и не может.
|
|
|
bogomol
|
|
old hand
|
|
|
|
|
|
|
Рег.: 26.08.2006
|
|
Сообщений: 813
|
|
|
|
Рейтинг: 1118
|
|
|
да, одной переменной.
но гугль что-то ничего не дает.
а при теоретических нахождениях нет никаких преимуществ?
и есть ли что-нибудь для функции многих переменных?
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:31
|
|
|
Quote:
да, одной переменной.
но гугль что-то ничего не дает.
Придумай сам. Делишь отрезок на три равные части - дальше методом прикладывания мозга понимаешь в какой из крайних третей минимум находиться не может, дальше рекурсивно. Точность оценивается элементарно размером отрезка.
Quote:
а при теоретических нахождениях нет никаких преимуществ?
При теоретических если у тебя там разговор про дифференцируемость, ищи производную.
Quote:
и есть ли что-нибудь для функции многих переменных?
Насколько подобное? Тут сотни, тыщи методов. От "обыкновенных" градиентных, до методов случайного блуждания и генетических алгоритмов.
|
|
|
bogomol
|
|
old hand
|
|
|
|
|
|
|
Рег.: 26.08.2006
|
|
Сообщений: 813
|
|
|
|
Рейтинг: 1118
|
|
|
А, все, понял. Только численно можно какое-либо преимущество получить.
А аналитически это ничего не дает, кроме того факта, что на множестве этот минимум всего один.
пасиба ))
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:37
|
|
|
Quote:
минимум всего один.
Так. Ты пример про max{ 0, |x|-5 } прочитал?
|
|
|
bogomol
|
|
old hand
|
|
|
|
|
|
|
Рег.: 26.08.2006
|
|
Сообщений: 813
|
|
|
|
Рейтинг: 1118
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:37
|
|
|
про метод трихотомии тоже понял.
можно послеждний вопрос? Почему отрезка три, а не 2 или не 4? Это принципиально?
В ответ на:
Так. Ты пример про max{ 0, |x|-5 } прочитал?
да, прочитал.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:38
|
|
|
Ладно, не буду тебя мучить. Есть понятие выпуклой функции, а есть еще строгая выпуклость. Советую прочитать.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:38
|
|
|
Когда придумаешь решение, сам поймешь, почему не 2. Почему не четыре или больше тоже, в принципе, догадаешься.
|
|
|
Leg
|
|
old hand
|
|
|
|
|
|
|
Рег.: 02.08.2005
|
|
Сообщений: 886
|
|
Из: терний к звездам
|
|
Рейтинг: 1465
|
|
Re: минимум выпуклой вниз функции
[re: bogomol]
03.06.2009 21:47
|
|
|
В ответ на:
и есть ли что-нибудь для функции многих переменных?
В порядке шутки:
зашел по ссылке в соседнем треде, там есть целый курс лекций Convex Optimization-1
http://academicearth.org/courses/convex-optimization-i
Посмотри, если хочешь просветиться. Как видишь, в двух словах тут всего не рассказать.
Ну и целые книжки есть по выпуклой оптимизации.
|
|
Список
Плоский
Дерево
