Значение поисковых методов и методов оптимизации

Мне было интересно, какие различия и отношения существуют между "методами поиска" и "методами оптимизации"?

Особенно при решении проблемы оптимизации? Я подчеркиваю контекст решения проблем оптимизации, потому что я думаю, что методы поиска не только для решения проблем оптимизации, но также и проблем неоптимизации?

Моя путаница проистекает из следующих фактов:

Существуют некоторые методы оптимизации, которые называются «поиск xxx», такие как локальный поиск , стохастический поиск … Что на самом деле означает «поиск»? Интересно, есть ли методы оптимизации, которые не являются "поиском"?
Также в этой книге « Введение в стохастический поиск и оптимизацию от Spall» я не совсем понимаю разницу между «поиском» и «оптимизацией» в его названии и в его содержании. Почему нужно различать «Поиск» и «Оптимизация», если они означают одно и то же? Или «Оптимизация» означает стохастические задачи / задачи оптимизации вместо методов оптимизации, в отличие от «поиска» означает методы решения задач / задач оптимизации?
Также отсутствие бесплатного ланча в поиске и оптимизации снова отличает поиск и оптимизацию.

Спасибо и всего наилучшего!

optimization Тим
источник

Ответы:

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

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

стохастический поиск: поиск по недетерминированному критерию выбора пробных точек.

Это не зависит от того, задан ли критерий оптимизации. В частности, в «Нет бесплатного обеда в поиске и оптимизации» поиск относится к поиску осуществимости, тогда как оптимизация относится к поиску оптимальности.

В общем смысле для задачи оптимизации поиск и оптимизация эквивалентны. Тем не менее, они имеют коннотации, которые имеют значение в использовании этого термина.

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

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

Арнольд Ноймайер
источник

Спасибо! Таким образом, для задач оптимизации: (1) В широком смысле поиск эквивалентен методам оптимизации. (2) В своем более узком смысле, поиск «обычно используя только значения функции» означает «методы поиска» {методы поиска} = {методы оптимизации, использующие только значения функции}

\cup

$\cup$ {методы поиска строки} "?" поиск строки "является единственным" методом поиска ", который использует вещи, выходящие за пределы значений функции? Если я добавлю некоторое возмущение к градиенту в методе, основанном на градиенте, станет ли метод методом" стохастического поиска "? Локальный поиск и стохастический поиск используют только значения функций?

Тим

(3) Являются ли методы поиска в его узком смысле метаэвристическими?

Тим

@Tim: Поиск строки может использовать или не использовать градиенты в своем поиске (например, поиск линии Вольфа нуждается в них). Вы не должны придавать этим словам слишком точное значение; они наводят на мысль о чем-то, а не о математических понятиях с точным значением. - Метод Ньютона использует градиенты и гессианы. - Метод является стохастическим, когда поиск включает генератор случайных чисел. - локальный поиск может использоваться в общем смысле метода, который не гарантирует сходимость к глобальному оптимуму, или подразумевает прямой поиск, основанный только на проверке локальных окрестностей текущей наилучшей точки.

Арнольд Ноймайер

Метаэвристика должна содержать принципы, более конкретные, чем просто «локальный поиск», чтобы заслужить свое имя; Я никогда не слышал, чтобы это применялось вообще. Но терминология не очень точна

Арнольд Ноймайер

Разница в терминологии между «поиском» и «оптимизацией» обусловлена тем фактом, что поиск относится к процессу поиска $x^\ast$ так что для данного $g(x)$ у нас есть $g(x^\ast)=0$ т.е. ищем корень. В оптимизации мы хотим найти $x^\ast$ так что $f(x) \rightarrow \textrm{min!}$ , По крайней мере, если $f$ является гладким, то поиск этого минимума обычно преобразуется в проблему поиска корня для $g(x)=\nabla f(x)$ , Другими словами, термин «поиск» происходит от более общей проблемы, но для задач оптимизации вещи, которые имеют дело с оптимизацией, часто сводятся к вещам, которые имеют дело с поиском.

Вольфганг Бангерт
источник

Поиск более широко применяется к системам уравнений и неравенств. В частности, в случае оптимизации ищется решение

g (x) = 0, f (x) \leq f_{b e s t}

$g(x)=0, f(x)\le f_{best}$ , Но методы прямого поиска в оптимизации не имеют доступа к

g (x)

$g(x)$ следовательно, нельзя просто применить алгоритм поиска к этому набору ограничений.

Арнольд Ноймайер