Математическое программирование

Математическое программирование – раздел прикладной математики, изучающий методы поиска экстремума функций. Алгоритмы математического программирования используются при решении оптимизационных задач, в частности, при синтезе объектов, выполняемых оптимизационными методами.

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

По типу области определения целевой функции математическое программирование подразделяется на дискретное, непрерывное и дискретно-непрерывное математическое программирование. Алгоритмы непрерывного математического программирования используются при параметрическом синтезе, дискретного – для синтеза структур, дискретно-непрерывного – при структурно-параметрическом синтезе.

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

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

Наиболее популярными локальными алгоритмами нулевого порядка (поисковыми алгоритмами) являются Роземброка (вращающихся координат), деформируемого многогранника, Хука-Дживса.

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

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

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

Литература

1. Химмельблау Д. Прикладное нелинейное программирование. Пер. с англ. Мир, М., 1975.
2. Батищев Д.И. Методы оптимального проектирования. М. Радио и связь 1984г.
3. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Сов. Радио, 1975.
4. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
5. Сушков Ю.А. Об одном способе организации случайного поиска. Автоматика и вычислительная техника, 1974, № 6, 41-48.
6. Фиакко А., Мак-Кормик Г. Нелинейное прогаммирование. Методы последовательной безусловной минимизации. Пер. с англ. М.: Мир, 1972.
7. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

Связанные понятия

• Оптимизация
• Структурно-параметрический синтез
• Параметрический синтез
• Алгоритм случайного поиска