Минимум выпуклой вниз функции

Verochka

   чем он отличается от минимума обыкновенной?
   тем, что на интервале выпуклоси вниз он — единственный, в частности, если ф-я выпукла вниз на всей оси ОХ, то она имеет единственный минимум?
   Еще есть какие-нибудь особенности?

Vlad128

У просто выпуклой не один.
Обыкновенная — какая? Полунепрерывная снизу?
Минимизирующее множество выпукло, вот этим отличается.

Verochka

Обыкновенная — какая? Полунепрерывная снизу?
например, кусочно-дифференцируемая.
ну вот допустим, мы начали искать минимум функции на интервале, а функция очень геморная. Облегчает ли нам поиск тот факт, что она выпуклая вниз? Или нам известно только то, что минимум на интервале должен быть один, больше ничего?
Минимизируеющее множество выпукло, вот этим отличается.

как понять эту фразу? То, что множество, на котором мы ищем минимум, выпукло?

Vlad128

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

Vlad128

как понять эту фразу? То, что множество, на котором мы ищем минимум, выпукло?
Минимум можно не только на интервалах искать, можно на множествах в пространствах большей размерности, можно вообще на функциональных пространствах, ты же в первом посте не говорил про то, что тебе программа нужна.
Вот рассмотри такую функцию: max{ 0, |x| - 5 }. Она внутри отрезка [-5;5] равна нулю. Она выпуклая. Она кусочно-(черт с ним) дифференцируема. Минимум достигается на всем отрезке [-5; 5]. Этот отрезок — минимизирующее множество. Оно выпукло. Вообще на прямой выпукло равносильно является интервалом, пустым множеством, лучем или прямой. Так вот если функция выпуклая, то по-другому быть и не может.

Verochka

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

Vlad128

да, одной переменной.
но гугль что-то ничего не дает.
Придумай сам. Делишь отрезок на три равные части — дальше методом прикладывания мозга понимаешь в какой из крайних третей минимум находиться не может, дальше рекурсивно. Точность оценивается элементарно размером отрезка.
а при теоретических нахождениях нет никаких преимуществ?
При теоретических если у тебя там разговор про дифференцируемость, ищи производную.
и есть ли что-нибудь для функции многих переменных?
Насколько подобное? Тут сотни, тыщи методов. От "обыкновенных" градиентных, до методов случайного блуждания и генетических алгоритмов.

Verochka

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

пасиба

Vlad128

минимум всего один.
Так. Ты пример про max{ 0, |x|-5 } прочитал?

Verochka

    про метод трихотомии тоже понял.
    можно послеждний вопрос? Почему отрезка три, а не 2 или не 4? Это принципиально?
Так. Ты пример про max{ 0, |x|-5 } прочитал?

да, прочитал.

Vlad128

Ладно, не буду тебя мучить. Есть понятие выпуклой функции, а есть еще строгая выпуклость. Советую прочитать.

Vlad128

Когда придумаешь решение, сам поймешь, почему не 2. Почему не четыре или больше тоже, в принципе, догадаешься.

gr_nik

и есть ли что-нибудь для функции многих переменных?
В порядке шутки:
зашёл по ссылке в соседнем треде, там есть целый курс лекций Convex Optimization-1
http://academicearth.org/courses/convex-optimization-i
Посмотри, если хочешь просветиться. Как видишь, в двух словах тут всего не рассказать.
Ну и целые книжки есть по выпуклой оптимизации.
Оставить комментарий
Имя или ник:
Комментарий: