Алгоритм Нелдера-Мида.

[Astrona]

Применяется для поиска локального минимума функций, зависящих от нескольких аргументов (в многомерных задачах). Насколько мне известно, этот метод реализован как библиотечный в программе Mathlab. Кратко его суть: строится начальный симплекс - множество из n+1 допустимых точек аргументов, где n-размерность задачи. Назову этот симплекс гиперпирамидой (треугольник, если на плоскости). Далее точки сортируются в порядке ухудшения значения функции. Наихудшаю точку пробуем заменить на другую, полученную как ее отражение по прямой из нее через центр масс оставшихся лучших точек (грубо говоря, по направлению туда, где ф-ция потенциально улучшается). Если отражение (и его пару под-вариантов на той же прямой) не дают улучшения ф-ции, то весь симплекс пропорционально сжимается к лучшей из точек. Все повторяется до тех пор, пока либо симплекс не вырождается (начинают совпадать точки или стягивается в маленькую область), а разброс значений ф-ции становится несущественным.

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

Если кто сталкивался с методом и проблемами, отзовитесь. Мне будет интересно обсудить подробнее.
Вот ссылочка на вики, где можно получить представление о теме:
http://en.wikipedia.org/wiki/Nelder-Mead_method

Как преодолеть вырождение симплекса? В моем случае оптимизируемая ф-ция аналитически не задана, получается в результате измерений. Имеет 6 аргументов по 5 или 8 бит каждый.

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

[TOTAL]

Astrona писал(а):

Как преодолеть вырождение симплекса?

Правильный тр-к всегда таким останется. Откуда вырождение?

[Zai]

Astrona писал(а):

У меня проблема стоит особо остро, потому что разрядность аргументов заданна (ограничена)

Что означает это Ваше утверждение?
Если Вы проводите поиск экстремумов, то по какой причине все Ваши переменные и операции с ними не удвоенной точности?

[Astrona]

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


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

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

Добавлено спустя 2 минуты 20 секунд:

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

[TOTAL]

Astrona писал(а):

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

При чем здесь целые? Если значения функции известны только в конечном числе точек, то перебором найдите с наилучшим значением.

[Astrona]

Нелдера-Мида примеяю как раз потому, что среди других ему требуется меньше всего раз вычислять ф-цию. Колв-о точек всего как минимум 2^(5*6), что неприемлемо много. Я уже писал, что аналитически не задана, а каждое измерение дорого по времени.

[TOTAL]

Astrona писал(а):

Нелдера-Мида примеяю как раз потому, что среди других ему требуется меньше всего раз вычислять ф-цию. Колв-о точек всего как минимум 2^(5*6), что неприемлемо много. Я уже писал, что аналитически не задана, а каждое измерение дорого по времени.

Точки кем-то заданы или в каких угодно точках можете вычислять? Впрочем, я бросаю это гадание.

[Zai]

Astrona писал(а):

Я уже писал, что аналитически не задана, а каждое измерение дорого по времени.

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

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

[Astrona]

Может не так оперативно, как хотелось бы - обсуждал эту проблему на месте..
Так вот, пространство с 6-ю дискретными аргументами, каждый 5-8 бит, т.е. прямой перебор неприемлем совершенно!
Измерять значение ф-ции можно в любых допустимых значениях аргументов. Измерили, изменили аргументы, измерили.. подумали, снова изменили аргументы и снова измерили и т.д.
Сама ф-ция можно считать непрерывная и сколь угодной точности, но не аргументы.

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

Именно на аналитической ф-ции Розенбрука проверяю. Она вполне хороший кандидат для остановки алгоритма до окончания оптимизации по причине низкой разрядности аргументов. Хотя разрядности хватает, чтобы "вручную" выбрать точку получше!!!

[Astrona]

Решил оставить оригинальный алгоритм, а с вырождением "бороться" инициализацией симплекса заново.