Геометрическое программирование: оптимизация позиномов и проектирование инженерных систем

Математическим атомом геометрического программирования является моном — функция, представляющая собой произведение строго положительной константы на переменные, возведенные в любые действительные степени (как положительные, так и отрицательные). Сумма нескольких таких мономов образует позином (posynomial). Классическая задача ГП заключается в минимизации целевой функции, являющейся позиномом, при наличии ограничений-неравенств, где левая часть также является позиномом, а правая строго равна единице. Условие строгой положительности всех переменных является критическим, так как оно отражает физическую реальность (длина, масса, напряжение или сечение кабеля не могут быть нулевыми или отрицательными).

В своей исходной формулировке задача геометрического программирования является невыпуклой, что делает ее труднорешаемой для стандартных алгоритмов. Однако математики обнаружили гениальный трюк: если выполнить замену переменных, перейдя к их логарифмам (y_i = ln(x_i)), и прологарифмировать сами функции, невыпуклые позиномы магическим образом превращаются в выпуклые функции (логарифмические суммы экспонент). Полученная преобразованная задача обладает идеальными свойствами: любая локальная точка минимума неоспоримо является глобальным оптимумом, а для ее поиска можно применить всю вычислительную мощь современных алгоритмов внутренней точки (Interior-Point Methods), сходящихся за полиномиальное время.

Огромную теоретическую ценность представляет двойственная задача геометрического программирования. В отличие от прямой задачи, которая является нелинейной, двойственная задача максимизирует специальную функцию при наличии исключительно линейных ограничений (условий ортогональности и нормальности). Количество независимых переменных в двойственной задаче совпадает с общим числом мономов, а количество линейных ограничений равно числу исходных переменных плюс один. Разность между числом мономов и числом ограничений называется степенью трудности (Degree of Difficulty). Если степень трудности равна нулю, система линейных уравнений имеет единственное решение, и глобальный оптимум вычисляется чисто алгебраически, вообще без применения итерационных поисковых алгоритмов!

Сегодня геометрическое программирование переживает бурное возрождение благодаря взрывному росту электронной промышленности. При проектировании сверхбольших интегральных схем (VLSI) инженерам необходимо минимизировать задержку распространения сигнала и энергопотребление транзисторов при жестких ограничениях на площадь кристалла. Физические уравнения, описывающие затворы транзисторов и емкости проводов, идеально укладываются в формат позиномов (Digital Circuit Sizing). Современные решатели, такие как CVX или MOSEK, за доли секунды оптимизируют параметры миллионов логических вентилей на микрочипе, доказывая, что теория, созданная полвека назад, стала главным математическим двигателем закона Мура.