40109

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

Доклад

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

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

Русский

2013-10-15

90 KB

27 чел.

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)


 

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

16463. ПРАВО ВНЕШНИХ СНОШЕНИЙ 172.5 KB
  19 Лекция № 6. ПРАВО ВНЕШНИХ СНОШЕНИЙ. 1. Основные понятия дипломатического и консульского права. 2. Дипломатическое право. 3. Консульское право. 1. Дипломатическое и консульское право право внешних сношений можно определить как отрасль междунар...
16464. ПРАВО МЕЖДУНАРОДНЫХ ОРГАНИЗАЦИЙ И КОНФЕРЕНЦИЙ 67 KB
  6 Лекция № 7. ПРАВО МЕЖДУНАРОДНЫХ ОРГАНИЗАЦИЙ И КОНФЕРЕНЦИЙ. 1. Понятие классификация правовая природа и структура международных организаций. 2. Организация Объединенных Наций и другие важнейшие международные организации. 3. Подготовка и правила про
16465. ОБЕСПЕЧЕНИЕ МЕЖДУНАРОДНОЙ БЕЗОПАСНОСТИ 99 KB
  11 Лекция № 8. ОБЕСПЕЧЕНИЕ МЕЖДУНАРОДНОЙ БЕЗОПАСНОСТИ 1. Понятие и система международной безопасности. 2. Мирное урегулирование международных споров. 1. На всем протяжении человеческой истории чрезвычайную актуальность имела проблема недопущени...
16466. МЕЖДУНАРОДНОЕ ГУМАНИТАРНОЕ ПРАВО 93 KB
  Лекция № 9. МЕЖДУНАРОДНОЕ ГУМАНИТАРНОЕ ПРАВО. 1. Понятие и источники международного гуманитарного права. 2. Права человека: понятие классификация и стандарты в международном праве. 3. Система межгосударственного сотрудничества в области прав человека. 1. Нормы ме...
16467. МЕЖДУНАРОДНАЯ ОТВЕТСТВЕННОСТЬ И МЕЖДУНАРОДНОЕ УГОЛОВНОЕ ПРАВО 72 KB
  Лекция № 10. МЕЖДУНАРОДНАЯ ОТВЕТСТВЕННОСТЬ И МЕЖДУНАРОДНОЕ УГОЛОВНОЕ ПРАВО. 1. Ответственность в международном праве. 2. Понятие особенности и правовая природа международного сотрудничества в борьбе с преступностью. 3. Преступления имеющие международный уголовный...
16468. Важнейшие подотрасли международного публичного права 44 KB
  Лекция. Важнейшие подотрасли международного публичного права. 1. Международное морское право. 2. Международное воздушное право. 3. Международное космическое право. 1. Международное морское право совокупность норм международного права регулирующих отношения ме...
16469. Муниципальное право 995 KB
  Глава 1 МУНИЦИПАЛЬНОЕ ПРАВО КОМПЛЕКСНАЯ ОТРАСЛЬ ПРАВА Понятие муниципальное право новое для нашего государствоведения хотя вопросы муниципального управления муниципального хозяйства в свое время являлись предметом исследования юристов и деятелей земского...
16470. Основи конституційного ладу України 378 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО основи конституційного ЛАДУ УКРАЇНИ Київ Ін Юре 1997 ББК 67.94УКР300 1143 Погорілко В. Ф. П43Основи конституційного ладу України. К.: Ін Юре 1997. 40
16471. Права та свободи людини і громадянина в Україні 494 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО В. В. ГОЛОВЧЕНКО М. І. СІРИЙ ПРАВА ТА СВОБОДИ ЛЮДИНИ І ГРОМАДЯНИНА В УКРАЇНІ Київ Ін Юре 1997 ББК 67.94УКР300 П43 Погорілко В. Ф. Головчен...