Исследование методов штрафных функций

     Федеральное агентство по образованию Российской Федерации

     Государственное образовательное учреждение высшего  профессионального обучения

     АМУРСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

     (ГОУВПО  «АмГУ»)

     Факультет математики и информатики

     Кафедра МАиМ

     Специальность 010501 «прикладная математика» 
 
 
 
 

     Курсовая  работа

     по  курсу: Методы оптимизации

     на  тему: Исследование методов штрафных функций 
 
 
 
 
 
 
 
 
 
 
 
 

     Благовещенск 2006

 

      Федеральное агентство по образованию Российской Федерации

     Государственное образовательное учреждение высшего  профессионального обучения

     АМУРСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

     (ГОУВПО  «АмГУ») 

     Факультет математики и информатики

     Кафедра МАиМ

     Специальность 010501 «прикладная математика» 
 

     Задание

     к курсовой работе студентов 

     

1. Тема работы: Исследование методов штрафных функций;
2. Срок сдачи студентами законченной работы: 15.12.2006 г.;
3. Дата выдачи задания: 01.09.2006 г.

 
 

     Руководитель 

     к.ф-м.н., доцент

     Задание принял к исполнению 02.09.2006 г. 

 

      Реферат 

     Курсовая  работа, 26 страниц, 4 рисунков, 2 таблиц, 5 источников.

     НЕЛИНЕЙНОЕ  ПРОГРАММИРОВАНЕ, ОПТИМИЗАЦИЯ, ШТРАФ, БАРЬЕРНАЯ ФУНКЦИЯ, АЛГОРИТМ, МЕТОД, ИТЕРАЦИЯ

     Объектом  исследования являются методы штрафных функций.

     Изучены методы и механизмы переход от задачи условной оптимизации к эквивалентной задаче или последовательности задач безусловной оптимизации.

     По  ходу исследования были решены некоторые  примеры с помощью этих методов.

 

      Содержание 

Введение

1. Общая задача нелинейного программирования

1.1 Постановка задачи

1.2 Теорема (обобщенное правило множителей Лагранжа)

1.3 Регулярный случай

1.4 Теорема (обобщенное правило множителей Лагранжа в регулярном случае)

1.5 Достаточные условия, существование, единственность

1.6 Об ограничениях-равенствах

1.7 Еще один достаточный признак условного минимума

2. Методы штрафных функций

2.1 Метод барьерных поверхностей

2.1.1 Алгоритм метода барьерных поверхностей

2.2 Метод штрафных функций

2.2.1 Алгоритм метода штрафных функций

Заключение

Список используемых источников 

 

      ВВЕДЕНИЕ 

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

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

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

 

      1. Общая задача нелинейного программирования 

     1.1 Постановка задачи 

     Общей задачей нелинейной условной оптимизации мы будем называть условную задачу минимизации  

     f0(x) ® min, x Î W,(1.1) 

     где W выделяется как ограничениями типа равенств  

     fi(x) = 0, i = 1, ..., k,(1.2) 

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

     gj(x) £ 0, j = 1, ..., l(1.3) 

     Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (1.1)–(1.3) можно записывать в виде  

     f0(x) ® min, f(x) = Q, g(x) £ Q.(1.4) 

     (напомним, что неравенство g(x) £ Q означает покоординатные неравенства).

     Нам также потребуется следующее  обозначение: a+ = (a + |a|)/2; таким образом, a+ = a, если a ³ 0 и a+ = 0, если a £ 0. Для векторов a Î Rm операция "+" определяется покоординатно: a+ = ((a1)+, ..., (am)+). Кроме того, через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j Î {1, ..., l}: gj(x) = 0} — это номера ограничений, которые в данной точке существенны. Например, на рисунке 1 J(x1) = {2}, а J(x2) = Æ.  

     1.2 Теорема (обобщенное  правило множителей  Лагранжа) 

     Пусть f0, f, g Î C1, а x* — локальное решение задачи (1.4). Тогда найдутся такие l*0 Î R, l* Î Rk, m* Î Rl, не равные одновременно нулю, такие, что m*j ³ 0 при j Î J(x*) и  

      (1.5) 

     Доказательство. Возьмем r > 0 таким, чтобы x* = argminxÎWr f(x), где Wr = W Ç B(x*, r). Для любого n Î N определим функцию f n: Rm ® R равенством  

     f n(x) = f0(x) + n(||f(x)||2 + ||g+(x)||2) + ||x - x*||2. 

     Задача 1. Докажите, что f n Î C1, в частности, покажите, что (||g+(x)||2)¢ = 2g+(x)g¢(x).

     Поскольку f n непрерывно дифференцируемы и поэтому непрерывны, функции f n на шаре B(x*, r) достигают минимума; обозначим его через xn. В частности,  

     f n(xn) £ f n(x*),(1.6) 

     т. е.

     f0(xn) + n(||f(xn)||2 + ||g+(xn)||2) + ||xn - x*||2 £ f n(x*). 

     Отсюда, поскольку, как легко видеть, f n(x*) = f0(x*),  

       

     ыражение  в квадратных скобках ограничено, так как xn Î B(x*, r). Поэтому ||f(xn)||2 + ||g+(xn)||2 ® 0 при n ® ¥ и, следовательно, f(xn) ® Q и g+(xn) ® Q при n ® ¥.

     Пусть теперь {xni} — произвольная сходящаяся, скажем к y, подпоследовательность. Тогда, как легко видеть, во-первых, y Î W и, во-вторых, f ni(xni) ® f0(y) + ||y - x*||2 при n ® ¥. Поэтому, подставляя в (1.6) ni вместо n и переходя к пределу в получившемся неравенстве при i ® ¥, получим  

     f0(y) + ||y - x*||2 £ f0(x*). 

     С другой стороны, так как x* = argmin f(x), f0(x*) £ f0(y). Отсюда ||y - x*||2 £ 0, т. е. y = x*. Таким образом, любая сходящаяся подпоследовательность последовательности {xn} сходится к x*. Последнее, учитывая компактность последовательности, гарантирует ее сходимость к тому же пределу.

     Далее, в силу доказанного можно считать, что при всех n точка xn лежит внутри шара B(x*, r). Поэтому в силу теоремы Ферма (f n)¢(xn) = Q, т. е.  

      (1.7)

 

      Положим теперь  

       

     ln0 = sn, lni= 2nfi(xn)sn, mnj= 2n[gj(xn)]+sn. Поскольку ln0,lnj,mnjÎ [-1, 1] (n Î N; i = 1, ..., k; j = 1, ..., l), можно считать, не ограничивая общности, что найдутся такие l*0,l*iи m*j, что

       ln0® l*0, lni® l*i, mnj® m*j при n ® ¥.

     Умножив (1.7) на sn и переходя в получившемся равенстве к пределу при n ® ¥, получаем  

      (1.8) 

     Остается  заметить, что, во-первых, так как |ln0|2+ åki=1|lni |2+ålj=1|mnj|2=1, не все из l*0,l*i,m*jравны нулю, во-вторых, поскольку mnj= 2n[gj(xn)]+sn ³ 0, неотрицательны и m*jи, наконец, в-третьих, если j Ï J(x*) (т. е. gj(x*) < 0), то gj(xn) < 0 при больших n; поэтому [gj(x*)]+ = 0, что влечет равенство m*j= 0 и, следовательно, равенство 

       

     Таким образом (1.8) — это (1.5).  

     1.3 Регулярный случай 

     Так же, как и в случае ограничений-равенств в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если l*0¹ 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (1.5) на l*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: Rm×Rk×Rk ® R (в регулярном случае) равенством 

     L(x, l, m) = f0(x) + (l, f(x)) + (m, g(x)). 

     Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ¢1(x),..., f ¢k(x)линейно независимы и для некоторого ненулевого вектора h Î Rm  

     (f ¢i(x),h) = 0 при i = 1, ..., k 

     и  

     (g¢j(x),h) < 0 при j Î J(x). 

     Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ¢i(x)),и, во-вторых, он образует с градиентами g¢j(x)активных ограничений (указывающими, очевидно, вовне множества W) тупой угол (рисунок 2). 

     1.4 Теорема (обобщенное  правило множителей  Лагранжа в регулярном случае).  

     Пусть f0, f, g Î C1, а x* — регулярное локальное решение задачи (1.4). Тогда найдутся l* Î Rk, m* Î Rl не равные одновременно нулю, такие, что m*j ³ 0 при j Î J(x*) и

 

      L¢x(x*,l*, m*) = 0,(1.9)

     (m*, g(x*)) = 0.(1.10) 

     Доказательство. Пусть l0**, l** и m** — величины, существование которых утверждается в теореме 1.2. Покажем, что l0** ¹ 0. В предположении противного умножим (1.5) скалярно на вектор h, фигурирующий в определении регулярности x*: