Градиентный метод решения задач выпуклого программирования

ВВЕДЕНИЕ
     
          Интенсивное развитие методов математического программирования связано с тем, что оптимизационные задачи играют большую роль в самых различных областях человеческой деятельности. Сейчас основное внимание уделяется развитию методов выпуклого программирования. Построен целый ряд алгоритмов, проведены исследования их сходимости. Однако эти алгоритмы применяются довольно редко, и нет достаточной информации, позволяющей судить об их сравнительной эффективности. При использовании методов выпуклого программирования решение исходной задачи обычно определяется как предел минимизирующей последовательности решений более простых (вспомогательных) экстремальных задач. 
     Полагая в основу тип вспомогательных задач, большинство методов выпуклого программирования можно разделить на две группы.
     - К первой группе относятся методы, при реализации которых на каждом шаге приходится решать задачу минимизации линейной или выпуклой функции при линейных ограничениях. Это различные варианты метода возможных направлений (метод отсечения, проекций градиента).
     - Ко второй группе относятся методы, с помощью которых искомое решение определяется как предел последовательности безусловных минимумов специальным образом сконструированных вспомогательных функций: метод штрафных функций, центров, множителей Лагранжа.
     В дипломной  работе рассматривается градиентный метод решения задач выпуклого программирования.


Глава 1. Задача нелинейного программирования 

1.1 Основные понятия задачи нелинейного программирования

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


     h_1 (X ? ),h_2 (X ? ),h_3 (X ? ),…,h_m (X ? ),      i=(1,m) ?   (1.1)

задают ограничения в виде равенств 

?g_(m+1) (X ? ),g_(m+2) (X ? ),g_(m+3) (X ? ),…, g?_p (X ? ),   j=(m+1,p) ?                                    (1.2)

     
задают ограничения в виде неравенств, где
     X ?=[x_1,x_2,x_3,…,x_n ],X ??E^n- вектор параметров проектируемого объекта, процесса или системы оптимальные значения которых должны быть найдены. 
     Тогда задача нелинейного программирования может быть сформулирована следующим образом:
     найти вектор X ?=[x_1,x_2,x_3,…,x_n ],X ??E^n,доставляющий минимум (максимум) целевой функции F(X ? ) при m линейных и (или) нелинейных ограничений в виде равенств 
     
                                    h_i (X ? )=0,          i=(1,m) ?  (1.3)

и (p-m) линейных и (или) нелинейных ограничений в виде неравенств 

                                  g_j (X ? )>0,      j=(m+1,p) ?                                                     (1.4)
     
В течение последних двух десятилетий из нелинейного программирования выделились самостоятельные разделы:
     -выпуклое программирование, 
     -квадратичное программирование, 
     -целочисленное программирование, 
     -стохастическое программирование, 
     -динамическое программирование и др.
     Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены.
     Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратичная, а ограничения – линейны.
     В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения.
     
     В задачах стохастического программирования в целевой функции или в функциях ограничений содержатся случайные величины, которые подчиняются законам теории вероятностей.
     В задачах динамического программирования ограничения содержат как параметр время и при этом описываются дифференциальными уравнениями. Процесс нахождения решений в задачах динамического программирования является многоэтапные.

1.2 Классификация методов нелинейного программирования

     Для решения задачи нелинейного программирования было предложено много методов, которые можно классифицировать по различным признакам.
     По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:
     - однокритериальные, 
     - многокритериальные.
     По длине вектора X ? методы делятся на:
     - однопараметрические или одномерные (n=1), 
     - многопараметрические или многомерные (n>1).
     По наличию ограничений методы нелинейного программирования делятся на:
     - без ограничений (безусловная оптимизация), 
     - с ограничениями (условная оптимизация).
     По типу информации, используемой в алгоритме поиска экстремума методы делятся на:
     - методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения; 
     - градиентные методы первого порядка, в которых при поиске экстремума функции используются значения ее первых производных; 

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

1.3 Выпуклое программирование

     Выпуклое программирование [convexprogramming] — раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений. 
     Общая задача выпуклого программирования состоит в отыскании такого вектора  x (т. е. такой точки выпуклого допустимого множества), который доставляет минимум выпуклой функции f(x) или максимум вогнутой функции y(x). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторов предпочитают термин “вогнутое программирование”. 
     Выпуклость (вогнутость) важна тем, что гарантирует нахождение оптимального решения задачи, так как соответственно локальные и глобальный экстремумы здесь обязательно совпадают. Критериями оптимальности в первом случае могут быть, напр., издержки при различных сочетаниях факторов производства, во втором случае — величина прибыли при этих сочетаниях. 
     Как видим, есть сходство между задачами выпуклого (вогнутого) и линейного программирования (последнее можно рассматривать как частный случай первого). Но нелинейность зависимостей делает задачу намного сложнее.
     
Под задачей выпуклого программирования понимают задачу вида

 f(x ? )?min
                                              
                                                   g_i (x ? )?0,   i=(1,m) ? (1.5)


где  f(x ? ) и g_i (x ? )- выпуклые функции. Для этих задач характерно то, что любой локальный минимум оказывается глобальным, и все сводится к нахождению этого единственного минимума.
     Для решения задач этого типа разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях ѕ метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.



















Глава 2. Градиентные методы решения задач выпуклого программирования


2.1 Градиентные методы решения задач
     
Методы, в основе которых лежит свойство градиента функции в точке (вектора частных производных, вычисленного в точке) как указателя направления наибольшего роста функции в окрестности точки называются градиентными. 
     Используя градиентный метод, можно найти решение любой задачи нелинейного программирования. Применение этого метода в общем случае позволяет найти точку локального экстремума. Поэтому более целесообразно использовать его для нахождения решения задач выпуклого программирования. Процесс нахождения решения задачи с помощью градиентного метода состоит в том, что начиная с некоторой точки X^((k))осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не будет найдено приемлемое решение исходной задачи. 
     Градиентные методы могут быть подразделены на две группы.
     - К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка – Вульфа. 
     - Ко второй – методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу – Гурвица.
     При нахождении решения задачи градиентными методами итерационный процесс продолжается до тех пор, пока градиент функции    f(x_1,x_2,…,x_n) в очередной точке X^((k+1)) не станет равным нулю или же пока не выполнится неравенство |f? (X^((k+1) ) )-f(X^((k) ) |0 (точность полученного решения).
Определение 1. Будем  говорить, что в точке (x^((1) ),…,x^((n)) ) функция f_0 имеет минимум, если можно указать такое число ?>0, что при всех (x_1,…,x_n ), удовлетворяющих условию 
?                                                  ?_(s=1)^n?(x_s-x_s^((0) ) ) ?^2?_1>0?
при 
?_(s=1)^n?x_s^2 ?+?,
то и любая интегральная кривая 
?                               x?_s=x_s (t),    s=1,…, n,                                       (5)
системы
?dx?_s/dt=-??f?_0/??x?_s ,     s=1,…, n,                                          (6)
обладает свойством x_s (t)?x_s^((0)) при t?+?.
         Следствие 2. Если f_0 достигает в некоторой точке (x_1^((0)),…,x_n^((0)) ) минимума, то эта точка для системы (6) является устойчивой по Ляпунову. Если же в достаточно малой ее окрестности градиент функции f_0 не обращается в нуль нигде за исключением самой точки, то (x_1^((0)),…,x_n^((0)) ) будет асимптотически устойчивой. И, наконец, если grad f_0 обращается в нуль в единственной точке и выполнены условия следствия 1, то оптимальная точка функции f_0  будет асимптотически устойчивой в целом.
Обратимся теперь к рассмотрению проблемы минимизации функций многих переменных при наличии ограничений. Рассмотрим ограничение вида ?                       f?_j (x_1,…,x_n )=0,   j=1,…,l.                                                     (7)
         Определение 3. Точку (x_1^((0)),…,x_n^((0)) ) назовем точкой минимума функции f_0  (x_1,…,x_n ) при условии (7), если существует ?>0 такое, что при всех (x_1,…,x_n ), удовлетворяющих (7) и условию 
?_(s=1)^n?(x_s-x_s^((0) ) )^2  f(x^((k) ) ).  Существуют разные способы выбора ?_k. Вообще говоря, наилучшим является выбор такого ?_k, при котором обеспечивается максимальный рост функции f(x). Такое  ?_k находится  из  условия
      (?fx?^((k))+?_k f'(x^((k) ) ))=max?(??0)??(?fx?^((k))+?_k f'(x^((k) ) )).               ?      (2.25)
         Градиентный метод поиска экстремума (2.24) с выбором шага по способу (2.25)  называется метод скорейшего подъема (или спуска для задачи на минимум). Такой метод требует наименьшего числа итераций, но зато на каждом шаге приходится решать дополнительную задачу поиска экстремума
(2.25) (правда, в одномерном случае). На практике часто довольствуются на-
хождением любого ?_k , обеспечивающего рост функции. Для этого берут
произвольное  ?_k и проверяют условие роста, если оно не выполняется, то
дробят ?_k до тех пор, пока это условие не будет выполнено (такое достаточно малое ?_k  при f'(x^((k) ) )?0 существует всегда).
         Процесс (2.24), очевидно, останавливается, когда выполнено условие
(2.23). При этом, если функция f(x) вогнута, то найденная стационарная точка будет решением задачи максимизации. В противном случае необходимо провести дополнительное исследование функции f(x) в окрестности найденной точки. Однако, даже если она будет точкой максимума, в невыпуклом случае трудно определить локальный это максимум или глобальный. Поэтому градиентные методы обеспечивают нахождение глобального экстремума только для вогнутых (выпуклых) функций, а в общем случае дают лишь локальные экстремумы (при этом можно попытаться найти глобальный экстремум, применяя итеративный процесс многократно с разными начальными точками).
         Если рассматривается задача максимизации f(x)  при ограничениях, т.е.
когда Х не совпадает с R^((n)), то непосредственное применение процесса (2.24)
может привести к нарушению ограничений, даже если начальная точка x^((0))?X. Однако эту трудность можно преодолеть, например, если получаемую по формуле (2.24) очередную точку проектировать на множество Х. Если обозначить операцию проектирования точки x на множестве Х через P_x (x), то соответствующий итеративный процесс имеет вид
?                   x?^((k+1))=(?P_x x?^((k))+?_k f'(x^((k) ) )).                                              (2.26)                 
         Полученный метод носит название метода проекции градиента. Шаг ?_k
в методе (2.26) может выбираться различными способами (например, как в
методе скорейшего подъема). Стационарная точка этого процесса является
решением задачи max?(x?X)??f(x)? в случае вогнутой функции f(x), а в общем случае требуется дополнительное исследование.
         Недостатком метода проекции градиента является необходимость про-
ведения операции проектирования, которая в общем случае эквивалентна не-
которой задаче поиска экстремума. Однако, когда Х является шаром, парал-
лелепипедом, гиперплоскостью, полупространством или ортантом, задача
проектирования решается просто и в явном виде.
        Еще одной разновидностью градиентных методов является метод условного градиента, который также предназначен для решения экстремальных задач с ограничениями. Суть его состоит в решении вспомогательной задачи максимизации на множестве Х линейной функции ,представляющей собой главную часть приращения функции f(x) в точке x^((k) ).
Эта вспомогательная задача может быть непростой, но если Х задается линейными ограничениями, то она представляет собой задачу линейного программирования, которая решается за конечное число шагов стандартными
методами (например, симплекс-методом). Если решение вспомогательной
задачи x ?^((k)) найдено, то следующее приближение для исходной задачи строится по формуле
                    ? x?^((k+1))=x^((k))+?_k (x ?^((k) )-x^((k) ) )                                              (2.27)        
        Если множество Х выпуклое, то ? x?^((k+1))?X.Шаг ?_k выбирается из условия максимального роста функции f(x)  или любым другим способом, обеспечивающим рост f(x). На практике обычно решают вспомогательную задачу не точно, а приближенно. В процессе (2.27) направление движения не совпадает с градиентом функции f(x)  в точке x^((k)), но определяется им, так как его компоненты берутся в качестве коэффициентов линейной целевой функции вспомогательной задачи.
    
     
     
     
     
     

Глава 3. Решение задач выпуклого программирования в среде  MathCad

В среду MathCad введены две функции Minimize и Maximize,позволяющие решать задачи оптимизации с использованием метода «сопряженных» градиентов.

3.1 Нахождение минимума тестовых функций 

         На рисунках 3. 1-3.7 для решения задач оптимизации используется встроенная  функция Minimize.
            Щелчок правой кнопкой  мыши по имени «решающих» функций            (Minimize или Maximize) вызывает дополнительное меню метода численного решения задачи (метод сопряженных градиентов) и их деталей (Options).
            Две последние позиции меню: Disable Evaluation ? отключение оператора и Optimize ? поиск решения через аналитические преобразования (через поиск аналитического решения). Функции Minimize и Maximize могут использоваться как самостоятельно, так и в составе блока Given……..Minimize(F,x_1,…,x_n).
Синтаксис функции:  Minimize(F,x1,…,xn),
где 
            F- критерий оптимизации, оформленный как функция пользователя;
            x1,…,xn – поисковые переменные.
            Функция Maximize записывается аналогично.
           Блок Given……..Maximize(F,x_1,…,x_n),обычно используют, если решается задача нелинейного программирования с ограничениями на поисковые переменные.



          Предлагается способ экономической оценки параметров несущих железобетонных и других композиционных конструкций.
          Рассмотрим однокритериальную многопараметрическую выпуклую целевую функцию стоимости железобетонной конструкции 
                             F(x)=F(x_1,…,x_n ).                                                                        (1)
          Здесь x_(1,)…,x_n- параметры несущих железобетонных конструкций.
          Функция F(x) задана на выпуклом компакте K?R^n со значениями в пространстве вещественных чисел R^1, т.е.
                                F(x)  :K?R .
          Задача состоит в нахождении минимума функции F(x), где x?K.
            Имеется достаточно много подходов к решению указанной задачи. Существуют сложные поисковые и оценочные методы [6]. Поисковые универсальнее, но значительно труднее оценочных. Последние позволяют использовать определенные закономерности, характеризующие оптимальные решения. В работах [5;6] рассматривается оценочный метод проверки оптимальных параметров для строительных конструкций.
           Из выпуклой целевой функции выделяются слагаемые, которые с увеличением значения x_k возрастают. Обозначим их как  F^+ (x_k )  .Слагаемые функции, которые с повышением значения x_k убывают, обозначим F^- ?(x?_k) , а не меняющие значение с изменением x_k  ?  F_0k.
          Оптимальному значению F?(x?_k) свойственно равенство групп F^+ (x_k) и F^- ?(x?_k) или достаточно малое их отклонение от равенства на допустимую величину c_k, обычно принимаемую равной 0,01x_k [5].
F^+ ?(x?_k+c_k)-F^+ (x_k ); F^- (x_k+c_k )-F^- ?(x?_k).                 (2)
         Оптимальность решения оценивается коэффициентом экономичности Э, который находится по формуле [5]
                    Э=|(F^+ ?(x?_k))?(F^- (x_k))|.                                                (3)
         Оптимальному значению соответствует значение Э=1. Предполагаемая методичка оценки оптимальности решений включает не только вычисление коэффициента экономичности Э, но и учет степени влияния групп F^+ ?(x?_k) и F^- (x_k ) на целевую функцию F(x). Степень влияния определяется отношением интенсивности изменения величины соответствующих групп в исследуемой точке к интенсивности на всем интервале значений параметра x_k: 
m^+=[?(F?^+ x_k+??x?_k)-F^+ (x_k )]/??x?_k   /(F^+ ?(x?_k))/x_k ;    
                                                                                                          (4)
m^-=[?(F?^- x_k+??x?_k)-F^- (x_k )]/??x?_k   /(F^- ?(x?_k))/x_k ;    
где m^+,m^-- коэффициенты F^+ (x_k )  и F^- (x_k )  ; ?x_k? приращение параметра x_k.
          С учетом коэффициентов интенсивности m^+ и m^- формула (3) запишется как 
                              Э=|W^+?W^- |                                                                     (5)                 
                    W^+=m^+ F^+ (x_k ),    W^-=m^- F^- ?(x?_k),
где W^+,W^-- обобщенные группы.
          Величина x_k^опт находится по формуле
                                    x_k^опт=x_k/?(Э_k ),k=1,…,n.                                         (6)        
          При Э=1 решение оптимальное, при Э<1 оптимум достигается увеличением x_k, при Э>1- уменьшением x_k.
         Эта методика проста в применении. Недостаток ее состоит в том, что для более .......................