40109

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

Доклад

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

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

Русский

2013-10-15

90 KB

22 чел.

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)


 

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

31924. Обчислення параметрів парної лінійної регресії матричним способом 177 KB
  Знайти оцінки коефіцієнтів моделі матричним способом. Матриця Х складається з 2х стовпців: 1й складається з 1 так як у моделі присутній вільний член а другий із вибіркових значень фактора Х. Остаточно матриця А буде мати вигляд: Тобто і наша модель має вигляд: Знайдемо інші параметри лінійної моделі для цього спочатку заповнимо таблицю 1: а для того щоб знайти стандартну похибку моделі обчислимо теоретичні значення фактора Y та знайдемо залишки моделі е. Знайдемо стандартну похибку моделі Е за формулою: .
31925. Архітектура комп’ютерів 286.5 KB
  Проаналізувати текст програми lb1. text SEGMENT ORG 100h begin: MOV x20 MOV bx30 DD xbx MOV cxx DD ch16 RET text ENDS END begin Початок сегменту коду програми під назвою text†Встановлення лічильника адреси на зміщення 100H шістнадцятирічне число 100 відносно початку сегменту кода Занесення до регістру АX числа 20 Занесення до регістру BX числа 30 Додавання двох чисел що містяться в регістрах АX та BX Занесення до регістру CX числа з регістру X Збільшення числа що міститься у старших 8 бітах регістра СX на 16 Команда...
31927. Общая психология, ответы на билеты 211.5 KB
  Крупные научные школы придерживались различных методологических принципов. Для поведенческой психологии (бихевиоризма) существенным было положение об объективности, наблюдаемости психических явлений. В психоанализе выдвигалась идея динамики, метаморфоз психической энергии в разные периоды жизни ребенка и взрослого. Концепции отечественных психологов строятся на принципах единства сознания и деятельности, принципе детерминизма
31928. Бытовая радиотелевизионная аппаратура 150 KB
  Структурная электрическая схема телевизора чернобелого изображения. Телевизоры чернобелого изображения ранних лет выпуска схема питания. Переносные ч б телевизоры схема питания. Переносные телевизоры ч б изображения схема разверток.
31932. Проектний тепловий розрахунок рекуперативного теплообмінника 585 KB
  Мета розрахунку Основною метою розрахунку теплообмінників є визначення поверхні теплообміну F а також основних розмірів апарата. Отже для визначення теплової поверхні необхідно розрахувати коефіцієнт теплопередачі k а також середній температурний напір 3. Визначення теплового навантаження апарата та масової витрати гарячого теплоносія 4. Визначення кількості трубок в теплообмінному апараті 5.