Понятие унимодальной функции в одномерной оптимизации

[_hum_]

Какое все-таки самое правильное, естественное и общее (в порядке приоритетности) определение унимодальной функции для задач одномерной оптимизации? Куча определений, и все какие-то либо неестественные и необщие, наподобие

Цитата:

Непрерывная функция $f(x) $называется унимодальной на отрезке $[a, b] $если:

• точка $x^*$ локального минимума функции принадлежит отрезку $[a, b]$;

• для любых двух точек отрезка $x_1$ и $x_2$ , взятых по одну сторону от точки минимума, точке $x_1$ более близкой к точке минимума соответствует меньшее значение функции, т.е. при $x^*< x_1 < x_2 $ либо при $x_2< x_1 < x^*$ справедливо неравенство $f(x_1)< f(x_2)$.

либо неправильные, наподобие

Цитата:

унимодальная функция - функция, имеющая один экстремум на интервале

?

Попробовал дать свое:

Цитата:

кусочно-непрерывная функция $f$ на отрезке $[a,b]$ называется унимодальной, если она имеет на нем единственный экстремум (не путать с точкой экстремума!), и он является минимальным значением функции на отрезке.

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

[grizzly]

_hum_ в сообщении #1259770 писал(а):

Но что плохо, граничные точки как правило оказываются точками экстремума, а потому "портят всю малину". Что с ними делать?

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

PS. Было бы лучше, если бы Вы давали ссылки на источники с определениями. Тогда было бы понятно, в каком контексте Вы интересуетесь вопросом и насколько серьёзными источниками пользуетесь.

[_hum_]

grizzly в сообщении #1259871 писал(а):

Ну скажите, что функция имеет на отрезке единственную точку локального максимума (минимума).

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

grizzly в сообщении #1259871 писал(а):

Если для Ваших целей важно не рассматривать границы, добавьте "внутреннюю точку".

тоже не пойдет, потому что нужно в унимодальность включить еще и монотонные на отрезке функции.

grizzly в сообщении #1259871 писал(а):

PS. Было бы лучше, если бы Вы давали ссылки на источники с определениями. Тогда было бы понятно, в каком контексте Вы интересуетесь вопросом и насколько серьёзными источниками пользуетесь.

контекст - численные методы оптимизации одномерных функций. типовое определение унимодальности можно посмотреть тут: /wiki/Unimodality#Unimodal_function

[teleglaz]

_hum_ в сообщении #1260674 писал(а):

во-первых, требуется только единственность самого минимума (точек же минимума при это может быть много)

Неа. Да так и не получится.

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

Функция $f(x)$ называется унимодальной на отрезке $[a;b]$, если она достигает глобального минимума на $[a;b]$ в единственной точке $x^*$, причём слева от $x^*$ эта функция строго убывает, а справа от $x^*$ строго возрастает.

Для методов одномерной оптимизации данное определение вполне годится.

[grizzly]

_hum_ в сообщении #1260674 писал(а):

типовое определение унимодальности можно посмотреть тут: /wiki/Unimodality#Unimodal_function

Ну так там хорошее определение. Почему привели не его, а какие-то другие, которые Вам не понравились?

_hum_ в сообщении #1260674 писал(а):

во-первых, требуется только единственность самого минимума

Это называется слабой унимодальностью. Обычно (по умолчанию) рассматривают сильную. Из Вашей вики-ссылки это должно быть понятно.

Хорошо, давайте посмотрим Ваше определение:

_hum_ в сообщении #1259770 писал(а):

Цитата:

кусочно-непрерывная функция $f$ на отрезке $[a,b]$ называется унимодальной, если она имеет на нем единственный экстремум (не путать с точкой экстремума!), и он является минимальным значением функции на отрезке.

Это определение описывает класс постоянных на отрезке функций, если Вы разрешаете, чтобы минимальное значение было по совместительству и максимальным. Иначе это просто хитрый способ описания пустого множества функций.Глупости, для разрывных функций может быть всякое, конечно. Оно Вам нужно?

-- 31.10.2017, 10:41 --

_hum_ в сообщении #1260674 писал(а):

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

Так не бывает.Для разрывных бывает (но при чём здесь унимодальность?).

[_hum_]

teleglaz в сообщении #1260733 писал(а):

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

Функция $f(x)$ называется унимодальной на отрезке $[a;b]$, если она достигает глобального минимума на $[a;b]$ в единственной точке $x^*$, причём слева от $x^*$ эта функция строго убывает, а справа от $x^*$ строго возрастает.

Для методов одномерной оптимизации данное определение вполне годится.

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

grizzly в сообщении #1260734 писал(а):

Ну так там хорошее определение. Почему привели не его, а какие-то другие, которые Вам не понравились?

честно говоря, не заметил принципиальной разницы между этими определениями - и там, и там дается через монотонность около некоей точки

Цитата:

_hum_ в сообщении #1259770 писал(а):

Цитата:

кусочно-непрерывная функция $f$ на отрезке $[a,b]$ называется унимодальной, если она имеет на нем единственный экстремум (не путать с точкой экстремума!), и он является минимальным значением функции на отрезке.

Это определение описывает класс постоянных на отрезке функций, если Вы разрешаете, чтобы минимальное значение было по совместительству и максимальным. Иначе это просто хитрый способ описания пустого множества функций.Глупости, для разрывных функций может быть всякое, конечно. Оно Вам нужно?

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


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

[grizzly]

_hum_ в сообщении #1260758 писал(а):

честно говоря, не заметил принципиальной разницы между этими определениями - и там, и там дается через монотонность около некоей точки

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

_hum_ в сообщении #1260758 писал(а):

если отбросить проблему с "граничными экстремумами"

В каком смысле отбросить? С точностью до "отбросить проблемы" можно говорить всё что угодно.

[teleglaz]

_hum_ в сообщении #1260758 писал(а):

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

Ну дык это то же самое. Обычно характер монотонности определить "на практике" проще, чем наличие или отсутствие экстремумов (их то мы и ищем).

_hum_ в сообщении #1260758 писал(а):

ведет там около максимума

Какого максимума? Мы про минимум пока что.

Короче, если ваша кусочно-непрерывная функция достигает на отрезке $[a;b]$ глобального минимума в единственной точке $x^*$ и других экстремумов нет ("по каким-то соображениям"), то функция унимодальна. Соответственно, методы требующие унимодальности должны быть сходящимися.

Ну или действительно, функцию и отрезок в студию.

[grizzly]

Попробую себя в роли экстрасенса. Вы хотите, чтобы такие функции были унимодальными?

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

[_hum_]

teleglaz в сообщении #1260782 писал(а):

Короче, если ваша кусочно-непрерывная функция достигает на отрезке $[a;b]$ глобального минимума в единственной точке $x^*$ и других экстремумов нет ("по каким-то соображениям"), то функция унимодальна. Соответственно, методы требующие унимодальности должны быть сходящимися.

в таком варианте не будет унимодальной (и соответственно, к ней нельзя будет де-юре применить методы поиска) такая простейшая функция, как $ y = x^2$ на отрезке $[-1,1]$ (потому как концы отрезка являются токами экстремума).
к тому же вы почему-то ведете речь про сильную унимодальность, тогда как для методов поиска достаточно и слабой.

grizzly в сообщении #1260789 писал(а):

Вы хотите, чтобы такие функции были унимодальными?

да.
вообще, суть в том, что мне предстоит объяснять тему "численные методы 1-d оптимизации" инженерам, довольно далеким от математики. потому я хотел:
1) определить максимально широкий класс функций, с которыми им придется столкнуться в задачах, и для которых методы (дихотомии, золотого сечения, фибаначчи) работали бы (чтоб не заморачивать им голову нюансами проверки принадлежности функции разным классам);
2) не вводить слишком математических определений, чтоб они могли легко воспринять понятие.

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

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

[grizzly]

_hum_ в сообщении #1260924 писал(а):

grizzly в сообщении #1260789 писал(а):

Вы хотите, чтобы такие функции были унимодальными?

да.

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

-- 31.10.2017, 22:31 --

Я считаю, что сказанное выше справедливо во всех отношениях (с точки зрения математики, оптимизации, методики преподавания), но по остальным вопросам не могу ничего посоветовать.

[_hum_]

grizzly

так а с вашей точки зрения,
1) в чем смысл тогда вообще вводить понятие унимодальной функции? (даже в тервере, судя по статье wiki/Unimodality, они вводятся не так, как в указанных определениях)
2) в чем смысл работать с ними в теории оптимизации (ведь нестрогая унимодальность атоматически перечеркивает единственность точки минимума, а потому, какой смысл ограничиваться в оптимизации только теми, у которых множество точек минимума - линейно связное?)
3) как называется "мой" класс функций - "униминимальные"? :)
4) что делать с точками экстремумов на границах отрезка (они портят все определение даже классической унимодальности, а хотелось определение, в котором бы они не были проблемой, ибо такое сплошь и рядом в задачах оптимизации).

p.s. кстати, по определению из вики:

Цитата:

A function $f(x)$ is a weakly unimodal function if there exists a value $m$ for which it is weakly monotonically increasing for $x \leq m$ and weakly monotonically decreasing for $x \geq m$.

получается, что слабо унимодальные могут иметь много пологих мест, а значит, и много локальных (нестрогих) экстремумов...[такие для указанных методов оптимизации не пойдут]

[grizzly]

_hum_ в сообщении #1261021 писал(а):

1) в чем смысл тогда вообще вводить понятие унимодальной функции? (даже в тервере, судя по статье wiki/Unimodality, они вводятся не так, как в указанных определениях)

Да, согласен, что какая-то путанница есть. Они в разделе ТВ так и говорят, что если есть два пика -- больший и меньший, то строго унимодальное распределение принято считать бимодальным. Но только скорее наоборот -- общее определение унимодальности функции дано в соответствии с наиболее привычным употреблением в ТВ.

_hum_ в сообщении #1261021 писал(а):

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

На той же странице вики говорят про оптимизацию следующее:

Цитата:

Depending on context, unimodal function may also refer to a function that has only one local minimum, rather than maximum.[15] For example, local unimodal sampling, a method for doing numerical optimization, is often demonstrated with such a function. It can be said that a unimodal function under this extension is a function with a single local extremum.

Может и Вам лучше ограничиться в своём курсе демонстрацией методов на самом распространённом (в преподавании) варианте? То есть, работать с определением обычной (сильной) унимодальности. Этого будет достаточно, чтобы потом при необходимости суметь разобраться с более сложными вещами (увы, я в методах оптимизации не знаток, чтобы говорить об этом уверенно).

_hum_ в сообщении #1261021 писал(а):

4) что делать с точками экстремумов на границах отрезка (они портят все определение даже классической унимодальности, а хотелось определение, в котором бы они не были проблемой, ибо такое сплошь и рядом в задачах оптимизации).

В "сильном" определении функция имеет на отрезке один локальный минимум (максимум), тогда проблем с границами нет. При единственном локальном минимуме либо этот минимум будет на границе, либо границы функции будут локальными максимумами.

PS. В итоге я пришёл к тому, с чего начал в этой теме. Больше не чувствую морального права что-то Вам советовать по этой теме -- не так уж хорошо я в ней разбираюсь. Буду надеяться, что поддержав разговор я скорее помог, чем запутал :)

[teleglaz]

_hum_ в сообщении #1260924 писал(а):

в таком варианте не будет унимодальной (и соответственно, к ней нельзя будет де-юре применить методы поиска) такая простейшая функция, как $ y = x^2$ на отрезке $[-1,1]$ (потому как концы отрезка являются токами экстремума).

Это смотря что искать. Я так и не понял, что вы ищете: минимум или максимум. Если мы ищем минимум, то функция $ y = x^2$ на отрезке $[-1,1]$ будет унимодальной, если ищем максимум, то не будет. Унимодальность должна пониматься в смысле того экстремума, который вы хотите искать. И в том определении надо было сказать "... других безусловных экстремумов нет...". Вот что бы этой путаницы избежать и применяют понятие монотонности.

_hum_ в сообщении #1261021 писал(а):

получается, что слабо унимодальные могут иметь много пологих мест, а значит, и много локальных (нестрогих) экстремумов...[такие для указанных методов оптимизации не пойдут]

Точнее не для всех методов подойдут. В этом случае не будет гарантии нахождения глобального экстремума. Кроме того некоторые методы придётся слегка модифицировать на случай "пологих мест". Поэтому в обычном подходе пытаются найти отрезок на котором функция унимодальна (строго).