Поэтапная оптимизация

Градуированная оптимизация — это метод глобальной оптимизации , который пытается решить сложную задачу оптимизации, изначально решая значительно упрощенную задачу и постепенно преобразуя ее (при оптимизации) до тех пор, пока она не станет эквивалентна сложной задаче оптимизации. ^{[1] [2] [3]}

В этом разделе не указаны источники . Пожалуйста, помогите улучшить этот раздел , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены . ( Октябрь 2011 ) ( Узнайте, как и когда удалять это сообщение )

Постепенная оптимизация — это усовершенствование метода восхождения на холм , которое позволяет восходящему на холм избегать остановок в локальных оптимумах. ^[4] Она разбивает сложную задачу оптимизации на последовательность задач оптимизации, так что первая задача в последовательности является выпуклой (или почти выпуклой), решение каждой задачи дает хорошую отправную точку для следующей задачи в последовательности, а последняя задача в последовательности — это сложная задача оптимизации, которую она в конечном итоге стремится решить. Часто ступенчатая оптимизация дает лучшие результаты, чем простое восхождение на холм. Кроме того, при наличии определенных условий можно показать, что она находит оптимальное решение для последней задачи в последовательности. Эти условия таковы:

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

Можно показать индуктивно, что если эти условия выполнены, то Hill Climbinger придет к глобальному оптимуму для сложной проблемы. К сожалению, может быть сложно найти последовательность задач оптимизации, которая удовлетворяет этим условиям. Часто градуированная оптимизация дает хорошие результаты, даже когда нельзя доказать, что последовательность задач строго удовлетворяет всем этим условиям.

Градуированная оптимизация обычно используется в обработке изображений для поиска объектов на более крупном изображении. Эту проблему можно сделать более выпуклой, размывая изображения. Таким образом, объекты можно найти, сначала выполнив поиск на самом размытом изображении, затем начав с этой точки и выполнив поиск на менее размытом изображении, и продолжая таким образом, пока объект не будет точно обнаружен на исходном четком изображении. Правильный выбор оператора размытия зависит от геометрического преобразования, связывающего объект на одном изображении с другим. ^[5]

Градуированная оптимизация может использоваться в многообразном обучении. Например, алгоритм Manifold Sculpting использует градуированную оптимизацию для поиска многообразного встраивания для нелинейного снижения размерности . ^[6] Он постепенно масштабирует дисперсию из дополнительных измерений в наборе данных, оптимизируя оставшиеся измерения. Он также использовался для расчета условий для фракционирования с опухолями, ^[7] для отслеживания объектов в компьютерном зрении, ^[8] и других целей.

Подробный обзор метода и его применения можно найти в ^{[3] .}

Имитация отжига тесно связана с градуированной оптимизацией. Вместо сглаживания функции, по которой она оптимизируется, имитация отжига случайным образом возмущает текущее решение на убывающую величину, что может иметь аналогичный эффект. ^{[ необходима цитата ]} Поскольку имитация отжига опирается на случайную выборку для поиска улучшений, ее вычислительная сложность экспоненциальна по числу оптимизируемых измерений. ^{[ необходима цитата ]} Напротив, градуированная оптимизация сглаживает оптимизируемую функцию, поэтому методы локальной оптимизации, которые эффективны в многомерном пространстве (такие как методы на основе градиента, Hill Climbing и т. д.), по-прежнему могут использоваться.

• Числовое продолжение