Глава II. Выпуклое программирование

§ 1. Нелинейное и выпуклое программирование

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

Наиболее общая задача нелинейного программирования может быть сформулирована следующим образом:

требуется определить значения n переменных x₁, x₂, ..., x_n, которые удовлетворяют m уравнениям или неравенствам вида

(2.1)

и обращают в максимум (или минимум) функцию цели

Предположим, что f и g_i - нелинейные заданные функции, b_i - известные константы. Обычно считается, что все или по крайней мере некоторые переменные должны быть неотрицательными.

В частном случае линейного программирования предполагается, что функции f и g_i являются линейными, т. е.

Всякая другая задача математического программирования, отличная от этой, считается нелинейной задачей.

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

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

где на функции f_j (x_j) должны в свою очередь быть наложены некоторые ограничения. Это так называемая сепарабельная функция. В другом случае целевая функция может быть записана как сумма линейной и квадратичной функций:

Нелинейные задачи такого типа называются задачами квадратичного программирования. Для того чтобы найти оптимальное решение, на величины d_ij необходимо наложить некоторые дополнительные ограничения.

Задачи с нелинейными ограничениями более трудны, чем с линейными. Чтобы в этих задачах получить оптимальное решение, к функциям g_i и f должны быть предъявлены весьма жесткие требования. В частности, оптимальное решение нелинейной задачи может быть получено в том случае, если ограничения g_i, заданные нелинейными неравенствами, определяют выпуклое множество в пространстве Переменных (см. гл. 1, § 3) и функция цели является нелинейной гладкой выпуклой или вогнутой функцией. В дальнейшем будет дано строгое определение выпуклой и вогнутой функций. Здесь же только необходимо указать, что свойство выпуклости функций f обеспечивает существование лишь одного минимума, а свойство вогнутости f - лишь одного максимума f внутри области, задаваемой ограничениями. На этом и строятся алгоритмы определения оптимального значения функции цели. При отсутствии выпуклости или вогнутости решение задачи математического программирования наталкивается на наличие локальных минимумов или максимумов, к отысканию которых в общем случае применимы классические методы.

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