Лекция: Другие методы условной оптимизации
Если все ограничения задачи заданы в виде неравенств, то для поиска условного минимума могут применяться модификации некоторых методов безусловной оптимизации. Так в методах случайного поиска модификация заключается в изменении условия успешности шага или направления. Шаг считается успешным. если он приводит в точку, в которой улучшается значение целевой функции и выполняются все ограничения. С этой целью добавляется проверка каждой точки на принадлежность допустимому множеству. В остальном алгоритмы остаются без изменений.
Аналогичное дополнение алгоритма Хука-Дживса делает его пригодным для поиска условного минимума. Генетические алгоритмы также могут использоваться для условной оптимизации. Для этого в них вводится детерминированный оператор жизнеспособности: если особь не удовлетворяет условиям «жизни», она погибает. Такой оператор должен применяться к каждой особи.
В данной главе не затронуты вопросы, возникающие при минимизации многоэкстремальных функций. Задача поиска глобального минимума многократно сложнее локальной оптимизации. Напомним, что при минимизации унимодальных функций в одних методах направление спуска выбирается по локальной модели целевой функции, например, линейной (градиентные методы) или квадратичной (метод Ньютона), в других – без использования модели, например, симплексный и случайные методы. В случае многоэкстремальной функции методы поиска строятся также на основе либо модели глобального поведения функции, либо эвристических представлений.
Несмотря на интенсивные исследования проблемы глобальной оптимизации сегодня нет эффективных методов, построенных на идее глобального поведения функции. Практическое применение находят в основном подходы, испоьзующие локальный спуск из многих начальных точек с последующим выбором лучшего из найденных решений. Многократный спуск иногда называют мультистартом. Ему присущи такие недостатки как возможность неоднократного спуска в одну и ту же точку и отсутствие гарантии попадания в область притяжения глобального минимума. Эффективность мультистарта повышают за счет обеспечения выхода из «мелких» минимумов, исключения повторных спусков в найденные минимумы и т.п. С этой целью процессу спуска придают инерцию, которая позволяет проскакивать «неглубокие» минимумы (метод тяжелого шарика), изменяют целевую функцию для придания ей «туннельного эффекта», обеспечивающего переход из найденного в более глубокий минимум, используют редукцию задачи и другие идеи.