40109

Методы штрафных функций и методы центров в выпуклом программировании

Доклад

Менеджмент, консалтинг и предпринимательство

Методы штрафных функций и методы центров в выпуклом программировании Метод штрафных функций Постановка задачи Даны непрерывно дифференцируемые целевая функция fx = fx1 xn и функции ограничений gjx = 0 j = 1 m; gjx 0 j = m1 p определяющие множество допустимых решений D. Требуется найти локальный минимум целевой функции на множестве D т. Стратегия поиска Идея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска безусловного минимума вспомогательной функции: Fx Ck =...

Русский

2013-10-15

90 KB

20 чел.

24. Методы штрафных функций и методы центров в выпуклом программировании

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

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

Даны непрерывно дифференцируемые целевая функция f(x) = f(x1,…, xn) и функции ограничений gj(x) = 0, j = 1,…, m; gj(x) £ 0, j = m+1,…, p, определяющие множество допустимых решений D.

Требуется найти локальный минимум целевой функции на множестве D, т.е. такую точку x*ÎD, что

f(x*) = min f(x)

          xÎD

где D = { x | gj(x) = 0, j = 1,…, m; m < n

                     gj(x) £ 0, j = m+1,…, p }.

Стратегия поиска

Идея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска безусловного минимума вспомогательной функции:

F(x, Ck) = f(x) + Vk(x, Ck) ® min

                                                   xÎRn

где Vk(x, Ck) - штрафная функция, Ck - параметр штрафа, задаваемый на каждой k-ой итерации. Это связано с возможностью применения эффективных и надежных методов поиска безусловного экстремума.

Штрафные функции конструируется, исходя из условий:

    Vk(x, Ck) = 0, при выполнении ограничений (xÎD) и

    Vk(x, Ck) > 0, при невыполнении ограничений (xÏD)

или

    lim Vk(x, Ck) = 0, если xÎD

    k®¥

    lim Vk(x, Ck) = ¥, если xÏD

    k®¥

Чем больше Ck, тем больше штраф за невыполнение ограничений.

Начальная точка поиска задается обычно вне множества допустимых решений D. На каждой k-ой итерации ищется точка x*(Ck) минимума вспомогательной функции F(x, Ck) при заданном параметре Ck с помощью одного из методов безусловной минимизации. Полученная точка x*(Ck) используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании последовательность точек x*(Ck) стремится к точке условного минимума x*.

Алгоритм

Шаг 1. Задать начальную точку x0; начальное значение параметра штрафа C0>0; число r>1 для увеличения параметра; малое число e > 0 для остановки алгоритма. Положить k = 0.

Шаг 2. Составить вспомогательную функцию

F(x, Ck) = f(x) + Vk(x, Ck) = f(x) + Ck*V(x)

Шаг 3. Найти точку x*(Ck) безусловного минимума функции F(x, Ck) по x с помощью какого-либо метода:

F(x(Ck), Ck) = min F(x, Ck)

                           xÎRn

При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять xk. Вычислить Vk(x(Ck), Ck).

Шаг 4. Проверить условие окончания:

а) Vk(x(Ck), Ck) £ e, процесс поиска закончить:

      x* = x*(Ck),      f(x*) = f(x*(Ck));

б) Vk(x(Ck), Ck) > e, положить:

      Ck+1 = r*Ck,     xk+1 = x*(Ck),      k = k+1

и перейти к шагу 2.

Сходимость

Утверждение. Пусть x* – локально единственное решение задачи поиска условного минимума, а функции f(x) и gj(x) непрерывно дифференцируемы в окрестности точки x*. Тогда для достаточно больших Ck найдется точка x*(Ck) локального минимума функции F(x, Ck) в окрестности x* и x*(Ck) ® x* при Ck ® ¥.

Замечания

1. Так как сходимость метода обеспечивается при Ck ® ¥, то возникает вопрос о том, нельзя ли получить решение исходной задачи в результате однократного поиска безусловного минимума вспомогательной функции с параметром Ck, равным большому числу, например 1020. Однако такая замена последовательного решения вспомогательных задач не представляется возможной, так как с ростом Ck  функция F(x, Ck) приобретает ярко выраженную овражную структуру. Поэтому скорость сходимости любого метода безусловной минимизации к решению x*(Ck) резко падает, так что процесс его определения заканчивается, как правило, значительно раньше, чем будет достигнута заданная точность, и, следовательно, полученный результат не дает возможности судить об искомом решении x*.

2. Точки x*(Ck) в алгоритме - это точки локального минимума функции F(x, Ck). Однако функция F(x, Ck) может быть неограниченной снизу и процедуры методов безусловной минимизации могут расходиться. Это обстоятельство необходимо учитывать при программной реализации.

3. Обычно выбирается C0  = 0,01; 0,1; 1, а rÎ[4, 10]. Иногда начинают с C0  = 0, т.е. с задачи поиска безусловного минимума.

4. При решении задач процедура расчетов завершается при некотором конечном значении параметра штрафа Ck. При этом приближенное решение, как правило, не лежит в множестве допустимых решений, т.е. ограничения задачи не выполняются. Это является одним из недостатков метода. С ростом параметра штрафа генерируемые алгоритмом точки приближаются к решению исходной задачи извне множества допустимых решений. Поэтому обсуждаемый метод иногда называют методом внешних штрафов.

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

Штрафные функции

Как уже говорилось, штрафные функции конструируется, исходя из условий:

    lim Vk(x, Ck) = 0, если xÎD

    k®¥

    lim Vk(x, Ck) = ¥, если xÏD

    k®¥

Как правило, для ограничений типа равенств используется квадратичный штраф:

 Vk(x, Ck) = Ck*(S[gj(x)]2),     j = 1,…, m

Для ограничений типа неравенств можно использовать:

1. Vk(x, Ck) = Ck*S(max{gj(x), 0})q,   j = m+1,…, p, параметр q ³ 1

при q = 1, штрафная функция недифференцируема и для ее минимизации нельзя применять методы наискорейшего спуска, метод сопряженных градиентов, метод Ньютона.

2. Vk(x, Ck) = Ck*max gj(x)+

                                             где gj(x)+ = max{gj(x), 0},      j = m+1,…, p

Метод внутренних штрафных (барьерных) функций

{xk}:  xk = argmin Hk(x, k)

                      xÎRn

H(x, Ck) = f(x) + k*B(x)

lim Bk(xk) = + ,

 k®¥

{k}0 при k®¥

2. Метод центров

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

Даны целевая функция f(x) = f(x1,…, xn) и функции ограничений gj(x) £ 0, j Î H , определяющие множество допустимых решений D.

Требуется найти локальный минимум целевой функции на множестве D, т.е. такую точку x*ÎD, что

f(x*) = min f(x)

          xÎD

где D = { x | gj(x) £ 0, j Î H }.

Вводится вспомогательная функция F(x) = max gj(x), по всем j Î H.

Алгоритм метода центров

0 шаг. Задать начальную точку x0ΠD. k = 0.

1 шаг. xk+1 = argmin Фk(x)

                      x Î Rn

Фk(x) = max {f(x) – f(xk),  F(x)}

2 шаг. k = k + 1. переход к шагу 1.

Последовательность {xk} слабо сходится к ответу, т.е. сходимость по функционалу:

lim f(xk) = min f(x)

Геометрическая интерпретация.

Недостаток метода: функция Фk(x) на каждом шаге в общем случае не дифференцируема, т.е. для ее минимизации надо использовать спец. методы.

Для ускорения сходимости применяют следующую вспомогательную функцию:

В такой модификации нет необходимости точно минимизировать вспомогательную функцию. Достаточно нна шаге 1 выбирать точку xk+1:  Фk(xk+1) < 0

 быстрее


F(
x)

f(x)

f(x) – f(x0)

f(x) – f(x1)

0

x1

x2

x*

x*

F(x)

f(x)

f(x) – f(x0)

f(x) – 0

x0

x1

x2

x'1

F(x,1)

x2

x1

f1(x)

f2(x)

V(x)

F(x,5)

F(x,20)

x3

x*

f(x)


 

А также другие работы, которые могут Вас заинтересовать

15051. Қазақ газетінде көтерілген мәселелер 48.5 KB
  Қазақ газетіндегі көтерілген оқу –тәрбие мәселелері. Қазақ – қоғамдық –саяси және әдеби газет 1913 жылы 2 ақпаннан бастап Орынборда аптасына бір рет 1915 жылы аптасына екі рет шығып тұрған. Тиражы –3000 кейбір мағлұматтарда 8000ға жеткен. Бірінші редакто
15052. Қазақ әдебиеті - жалпы шолу, энциклопедиялық мақала 62.94 KB
  Қазақ әдебиеті ҚАЗАҚ ӘДЕБИЕТI қазақ халқының ғасырлар қойнауынан ұрпақтан ұрпаққа жеткен рухани мәдени мұрасы сөз өнерiнiң асыл қазынасы. Қазақтың сөз өнерiнiң тегi әрiден түркi тiлдес тайпалардың өз алдына халық болып қалыптаспай тұрған кезiнен басталады. Халық фо
15053. Қазақ әдебиеті - тұлғаның рухани дамуының бастауы 62.5 KB
  ҚАЗАҚ ӘДЕБИЕТІТҰЛҒАНЫҢ РУХАНИ ДАМУЫНЫҢ БАСТАУЫ Ш. А.Өсерова А.Б.Бөгенбаева Жамбыл атындағы №5 орта мектеп Тараз қ. Әр халықтың тәлімтәрбиелік мұрасы ұлттық мәдениетінің маңызды белгісі болып табылады. Осы арқылы ол ұлттың ұлттық тәрбиесінің ере...
15055. Қазақ әдебиетіндегі айтыс өнерінің өзіндік өрнегі 63 KB
  ӘӨЖ ҚАЗАҚ ӘДЕБИЕТІНДЕГІ АЙТЫС ӨНЕРІНІҢ ӨЗІНДІК ӨРНЕГІ Г.А.Жұмабекова Тараз мемлекеттік педагогикалық институты Тараз қ. Қазақ әдебиетінің қайталанбас хас ерекшеліктері аз емес.Осы орайда ауыз әдебиеті үлгілерінің кемел жазба әдебиетке ойысу ұласу үрдісін...
15056. Қазақ әдебиетіндегі терме жанрының қалыптасуы мен дамуы 77.5 KB
  ҚАЗАҚ ӘДЕБИЕТІНДЕГІ ТЕРМЕ ЖАНРЫНЫҢ ҚАЛЫПТАСУЫ МЕН ДАМУЫ М.Т. Мұқашева №8 Төле би атындағы гимназия Тараз қ. Қазақы сөз арнау дәстүрі түрлі жанрлық тақырыптық сипатымен өзге түрік халықтарына қарағанда өте бай. Ең бастысы байырғы рухан
15057. Қазақ әдебиетінің ежелгі дәуірі, көне Түркі ескерткіштері 83 KB
  Қазақ әдебиетінің ежелгі дәуірі: көне Түркі ескерткіштері Ежелгі дәуір әдебиет VIIXIV ғғ. деп аталатын жеті ғасырды қамтыған әдебиетіміздің ұзақ тарихына қатысты ескерткіштер шығармалар аз емес. Олардың алғашқылары деп түркі рутайпаларына ортақ Орхон ескерткішт...
15058. Қазақ әдебитеті пәні бойынша ҰБТ-ге дайындаудың тиімді жолдары 116.5 KB
  ҚАЗАҚ ТІЛІ МЕН ӘДЕБИЕТ ПӘНІ БОЙЫНША ОҚУШЫЛАРДЫ БІРІҢҒАЙ ҰЛТТЫҚ ТЕСТІЛЕУГЕ ДАЙЫНДАУДЫҢ ТИІМДІ ЖОЛДАРЫ Манабаева Гүлбайрам Рахымқызы қазақ тілі мен әдебиеті пәнінің мұғалімі №35 жалпы орта білім беру мектебі Қазақ әдебиетінде өзіндік айтулы із қалдырған белгі
15059. Қазақ мақал-мәтелдерінің гендерлік сипаты 44 KB
  УДК 4Ф Б 76 ҚАЗАҚ МАҚАЛМӘТЕЛДЕРІНІҢ ГЕНДЕРЛІК СИПАТЫ М.Б. Боранбай Қ. Жұбанов атындағы Ақтөбе мемлекеттік университеті Ақтөбе қ. Қазақ халқы рухани дүниеге қазынаға бай халық. Оның қай түрін алсақ та тәлімтәрбиесі мол ұрпақтанұрпаққа қалдырған өcие