поиск минимума функционала

[d.dragon.n76]

Требуется найти глобальный минимум функционала $T=T(x_1,\dots,x_n)$, $n$ --- натуральное число. Мне удалось обнаружить численные алгоритмы поиска локального минимума для унимодальных функций. Аналитически доказать унимодальность функционала $T$ не удается, т.к. $T$ вычисляется из сложной системы уравнений.

Кроме перебора как можно найти глобальный мимнимум? Возможно ли как численно доказать что функционал $T$ унимодален на конкретном отрезке?

[Ham]

Если разбить конкретный отрезок на части, то для этих частей можно численно применить интервальные вычисления для поиска минимума(максимума) от полной производной от Т'(...)=0 (на дифференциируемых областях). Этот метод определяет Только те области где не будет минимума(максимума) основной функции. (когда 0 на попадает в вычисленный интервал)

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

[2..3]+[1..7]=[3..10] [5..6]/[-1..0,2]=(-\infty..+\infty) (-\infty..2]+[0..+\infty)=(-\infty..+\infty) (-\infty..+\infty)^2=[0..+\infty)

по желанию:
Если функция Т от многих переменных то можно привести её в обратную польскую нотацию и(или) сделать карринг для удобства.

[Yuri Gendelman]

d.dragon.n76 писал(а):

Кроме перебора как можно найти глобальный мимнимум? Возможно ли как численно доказать что функционал $T$ унимодален на конкретном отрезке?

Практически все методы поиска экстремума - локальные, основанные на вычислении градиента, точном или приближенном, или типа метода прямого поиска (построение и перемещение симплекса из N+1 точек). Для поиска глобального экстремума мультимодальных функций предлагался метод случайного поиска (Расстригин).
Универсального алгоритма доказательства унимодальности скорее всего не существует.

[d.dragon.n76]

Yuri Gendelman писал(а):

d.dragon.n76 писал(а):

Кроме перебора как можно найти глобальный мимнимум? Возможно ли как численно доказать что функционал $T$ унимодален на конкретном отрезке?

Практически все методы поиска экстремума - локальные, основанные на вычислении градиента, точном или приближенном, или типа метода прямого поиска (построение и перемещение симплекса из N+1 точек). Для поиска глобального экстремума мультимодальных функций предлагался метод случайного поиска (Расстригин).
Универсального алгоритма доказательства унимодальности скорее всего не существует.

1. порекомендуйте книжку (желательно чтобы в электронном виде была доступна)

2. имеет ли место выигрыш по времени при использовании метода случайного поиска по сравнению с методом перебора?

[Yuri Gendelman]

d.dragon.n76 писал(а):

1. порекомендуйте книжку (желательно чтобы в электронном виде была доступна)
2. имеет ли место выигрыш по времени при использовании метода случайного поиска по сравнению с методом перебора?

1. По методам оптимизации я часто пользовался вот этой книгой: Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. Она была в библиотеке Колхоза: http://lib.homelinux.org/

2. Если бы не было выигрыша по времени, то не было бы и смысла их применять. Но при этом вероятность того, что экстремум найден, меньше 100%. Это - цена выигрыша.

[mserg]

Видел в интернет-магазине книжку с современным содержанием за 350 евро. Название точно не помню, что-то вроде "Global Optimization". В открытой виде видел только слайды, но для "непосвященных" это будет выглядеть как китайская грамота.

Предложенные участниками форума методы - из каменного века, эффективность у них соответствующая. Можно попытаться использовать библиотеку BIAS/PROFIL, которая "объединяет" описанные выше методы. В ней же есть примеры. Вам нужно только дать функцию в аналитическом виде, система сама найдет глобальный оптимум (если сможет). В любом случае, система даст наилучшее решение и оценку до оптимума.
Довольно неплохая книга по этой теме:
http://edurss.ru/cgi-bin/db.pl?lang=Ru& ... list=Found
Повторюсь еще раз - все это "из бабушкиных фолиантов". Наука на месте не стоит.

[Yuri Gendelman]

Вот это утверждение:
Finding the global maximum or minimum of a function is much more challenging and has been practically impossible for many problems so far.
пока что, к сожалению, не отменено.

Реализованный в PROFIL/BIAS вариант метода ветвей и границ имеет экспоненциальную сходимость. Недетерминистские методы (прямой Монте-Карло, эволюционное программирование и пр.) работают не быстрее. Все вышеперечисленные решают далеко не все задачи из стандартных тестовых наборов.

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

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

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

Информация: На сайте http://gigapedia.com/ есть много книг по global optimization. Возможно, там есть и та самая за 350 евро.

[mserg]

Еще пару слов для "непосвященных".
Современные пакеты оптимизации включают в себя множество алгоритмов, которые экспоненциально уменьшают пространство поиска, тратя на это полиномиальное количество ресурсов (процессорного времени и памяти). Хотя задачи остаются трудно-решаемыми, вероятность получить оптимум или лучший результат экспоненциально выше, чем если использовать тривиальные алгоритмы (например, случай поиск). Во время поиска оптимума система интеллектуально подбирает "наиболее подходящие" полиномиальные алгоритмы и/или комбинирует их. Кроме локального поиска часто АВТОМАТИЧЕСКИ используются аналитические преобразования, декомпозиция формул, дифференцирование, "переформулирование" исходной задачи, добавление отсекающих плоскостей и динамическое линейное программирование, аппроксимация функций ломанными и т.д. и т.п. Читать и программировать можно до пенсии...

[Yuri Gendelman]

mserg,
Мне очень понравились современные пакеты оптимизации, о которых Вы рассказали. Не могли бы Вы привести пример такого пакета, который бы экспоненциально уменьшал пространство поиска, тратя на это полиномиальное количество ресурсов.

[mserg]

Не буду рекламировать конкурентов, т.к. через несколько месяцев выходит наш пакет глобальной оптимизации. Приведу пример на библиотеке BIAS/PROFIL.

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

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

[Yuri Gendelman]

Цитата:

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

То есть "экспоненциальное уменьшение пространства поиска" - это просто рекламный слоган. К теории сложности алгоритмов это отношения не имеет.

[mserg]

Утверждение верно в среднем. Для конкретной задачи может быть еще хуже: будет полный перебор и еще балласт в виде полиномиальных алгоритмов. Даже симплекс-метод может впасть в перебор, но обычно он полиномиальный. Впрочем, если хочется не понять, о чем тут писалось, то я бессилен...

[Yuri Gendelman]

mserg писал(а):

Даже симплекс-метод может впасть в перебор, но обычно он полиномиальный.

Да, согласен.
Но я предпочитаю пользоваться терминами из теории сложности алгоритмов.

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

Для линейного программирования полиномиальный метод впервые опубликовал Хачиян.