Функция/(л), определенная на выпуклом множестве М про странства Е^^, называется выпуклой на М, если для любых точек л'^ и х^, принадлежащих М, и для любого числа Я, О < Л < 1, спра ведливо неравенство /((1 - X) л-о + Хх^) < (1 - Х)/(х^) + ХЛх^У (1) Множество М с Е^^ называют выпуклым, если оно вместе с двумя любыми своими точками целиком содержит и соединяю щий их отрезок. Следовательно, всякое выпуклое множество со стоит из одного «куска» и не имеет «дырок» и «вмятин». 103 в теории выпуклого программирования в качестве основной обычно рассматривается задача отыскания вектора х = (Лр х^_, ... , х^, который удовлетворяет условиям х.>0, 7=1,2, ...,Az, (2) g.(A')<0,/=l,2,...,m (3) и доставляет глобальный минимум функцииУ(х). При этом заданные функции/, g,, g^, ... , g^^^, определенные на ^-мерных векторах х с неотрицательными компонентами, пред полагаются выпуклыми. Векторы, удовлетворяющие условиям (2) и (3), называют до пустимыми, а искомые векторы - оптимальными. В задачах выпуклого программирования для оптимальности допустимого вектора достаточно, чтобы он был наилучшим сре ди близких к нему допустимых векторов. Это означает, что выде ленный класс задач нелинейного программирования не содержит многоэкстремальных задач. Для задач выпуклого программирования разработан ряд эф фективных численных методов. В некоторых из них исходная за дача заменяется задачей поиска седловой точки функции Лагран- жа. Такие методы, как правило, связаны с классическими идеями наискорейшего спуска. В других методах непосредственно исполь зуется то обстоятельство, что в этих задачах достаточно найти допустимый вектор, наилучший среди близких к нему допусти мых векторов. Многообразие подобных методов определяется различными приемами построения последовательностей допус тимых векторов, монотонно минимизирующих целевую функцию. В этих случаях на каждом шаге при выборе направления движе ния решается вспомогательная задача, более простая, чем исход ная; в ряде методов - задача линейного программирования (см.). В некоторых из таких методов движение происходит в допустимой области {методы возмолсных направлений), в других допускается выход из этой области с последующим возвращением на границу {методы проекций градиента). Может применяться для решения задач выпуклого програм мирования и метод штрафов. При этом отыскание оптимально- 104 го вектора в исходной задаче сводится к последовательному ре шению вспомогательных задач на безусловный экстремум. Ми нимизируемые функции в этих задачах получают добавлением к функции fix) штрафов за нарушение ограничений (2) и (3). Из общих методов решения задач выпуклого программиро вания одним из важных является класс методов отсечения, в ко тором допустимое множество в окрестности решения аппрок симируется последовательностью вложенных многогранников. Благодаря этому вспомогательные задачи на каждом шаге могут решаться методами линейного программирования (см.). Для моделирования экономических систем часто используют задачи минимизации выпуклой функции при линейных ограни чениях. С целью решения таких задач разработан ряд методов, опирающихся на методы линейного программирования. В част ности, для минимизации выпуклой квадратичной функции имеют ся конечные алгоритмы. Другой важный класс, применяемый для моделирования эко номических задач, составляют сепарабельные задачи выпуклого про- граммирования. В этих задачах функции/и g^ представлены в виде сумм выпуклых функций одной переменной. После подходящей кусочно-линейной аппроксимации каждой из функций эти зада чи могут быть приближенно решены методами линейного про граммирования.
Ви переглядаєте статтю (реферат): «ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
