Решение невыпуклой оптимизации с использованием глобального алгоритма оптимизации с использованием MATLAB

Question

У меня есть простая проблема с неограниченной невыпуклой оптимизацией. Поскольку проблемы такого типа имеют несколько локальных минимумов, я ищу алгоритм глобальной оптимизации, который дает уникальный/глобальный минимум. В Интернете я столкнулся с глобальными алгоритмами оптимизации, такими как генетические алгоритмы, имитированный отжиг и т. Д., Но для решения простой однонаправленной непонятной проблемы невыпуклой оптимизации я считаю, что использование этих алгоритмов высокого уровня не кажется хорошей идеей. Может ли кто-нибудь порекомендовать мне простой глобальный алгоритм для решения такой простой одной переменной без ограничений, не выпуклой задачи оптимизации? Я бы высоко оценил идеи по этому поводу.

Answer 1

Поскольку это одномерная проблема, все проще. Простую процедуру крутого спуска можно использовать следующим образом. Предположим, что интервал поиска - a<x<b.

Запустите SD с минимальной функции, скажем f (x). Вы восстанавливаете первый минимальный Xm1. Вы должны использовать прекрасный шаг, не слишком большой. Сдвиньте эту точку, добавив положительную небольшую константу Xm1 + ε. Затем максимизируйте f или минимизируйте -f, начиная с этой точки. Вы получаете максимум f, вы искажаете его по ε и начинаете с него минимизацию и так далее.

Answer 2

«Так как проблемы такого типа имеют несколько локальных минимумов». Это не правда, реальная ситуация выглядит следующим образом:

• Может быть, у вас есть один локальный минимум

• Может быть, у вас есть бесконечное множество местных miminums

• Может быть, у вас есть конечное число локальных минимумов

• Может быть минимум не достигается

• Может быть пробл эм неограничена снизу

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

---

1. В самом деле М^п ~ M для любого конечного п и любого бесконечного множества M. Поэтому тот факт, что вы проблема имеет одно измерение нет ничего. Это все еще сложно, поскольку проблема с 1000000 параметрами, взятыми из множества M с теоретической точки зрения.

2. Если интересно, как приблизительно решить проблему с известной точностью эпсилон в области - затем разделить Вас домен на 1/espsilon областей, значение выборки (вычисляться функции) в средней точке, и выбрать минимальный метод

3. , который я ниже будет точный метод и другие методы: оценка частиц, sequent.convex.programming, альтернативное направление, частичный рой, метод Simple Neidler-Mead, сглаживание градиента/субградиента mutlistart или любой алгоритм спуска, такой как метод Ньютона или координата descend, они все не имеет gurantess для невыпуклых проблем, и некоторые из них даже не могут быть применены, если функция невыпукла.

---

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

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

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

Но и вы должны иметь нижнюю границу по какому-то принципу:

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

• использовать функцию Лагранжа Dual

• использование Lipshitc постоянная на функция и т. д.

И это изощренный шаг.

Если эти два значения близки - мы сделали в другом случае частичный или уточняющий раздел.

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

---

Ссылки:

Для более большого объяснения, пожалуйста, посмотрите на: EE364B, лекция 18, проф. Стивен Бойд, Стэнфордский университет. Он доступен на youtube и в ITunes University. Если вы новичок в этой области, я рекомендую вам посмотреть курсы EE263, EE364A, EE364B Стивена П. Бойда. Вам понравится