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)


 

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

11536. Синтез структуры счетчика и исследование функций счетчика с заданными параметрами 70 KB
  Отчет о лабораторной работе по курсу Схемотехника ЦИФРОВЫЕ СЧЁТЧИКИ Цель работы: синтез структуры счетчика и исследование функций счетчика с заданными параметрами. Задание: синтезировать и построить цифровой счётчик со следующими характеристиками: ...
11537. Программирование разветвляющихся алгоритмов 111 KB
  Тема 2. Программирование разветвляющихся алгоритмов Цель лабораторной работы: научиться пользоваться простейшими компонентами организации переключений TСheckBox TRadioGroup. Написать и отладить программу разветвляющегося алгоритма. 2.1. Операторы if и case языка Паскаль Для...
11538. Программирование циклических алгоритмов. Операторы организации циклов repeat, whyle, for языка Pascal 68.73 KB
  Программирование циклических алгоритмов Цель лабораторной работы: изучить простейшие средства отладки программ в среде DELPHI. Составить и отладить программу циклического алгоритма. Операторы организации циклов repeat whyle for языка Pascal Под циклом понимается...
11539. Устройства СВЧ и антенны 879.5 KB
  Устройства СВЧ и антенны Методические указания к лабораторным работам по дисциплине Устройства СВЧ и антенны для студентов факультета Радиотехника электроника и физика направления 552500 и 654200 – Радиотехника всех форм обучения Лабораторная работа №1 ...
11540. Разработка оконных приложений, использующих автономные модули 91.98 KB
  Лабораторная работа №8 Разработка оконных приложений использующих автономные модули Условие Задача 3.4. Составьте подпрограмму исходными данными которой являются числовые массивы C и или D из n элементов. Основной её результат – также массив получающий некотор
11541. Анализ требований (UML) 60.25 KB
  Лабораторная № 1. Анализ требований UML Анализ требований – процесс изучения потребностей и целей пользователей классификация и преобразование их к требованиям к системе аппаратуре и программному обеспечению разрешение конфликтов между требованиями определение г
11542. Концептуальная модель ПО (UML) 29.21 KB
  Лабораторная № 2. Концептуальная модель ПО UML Построение модели предметной области начинается с выявления абстракций существующих в реальном мире то есть тех основных концептуальных объектов которые встречаются в системе. Концептуальная модель – это представлени...
11543. Концептуальная и физическая модели базы данных (IDEF1x) 73.85 KB
  Лабораторная № 3. Концептуальная и физическая модели базы данных IDEF1x Концептуальная модель базы данных Логическая модель Концептуальная модель базы данных рис. 2 описывает объекты предметной области их атрибуты и связи между ними в том объеме в котором они подл
11544. Ограничения на данные (DEFAULT и CHECK) и ссылочную целостность 18.35 KB
  Лабораторная № 5. Ограничения на данные DEFAULT и CHECK и ссылочную целостность Добавление отношения Конт. м. таблицы содержащей FK Отношения Добавить Спецификация таблиц и столбцов ИЛИ Проект таблицы кнопка Отношения Добавить... Слева все про РК имя таблицы поле...