40109

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

Доклад

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

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

Русский

2013-10-15

90 KB

24 чел.

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)


 

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

20016. Технология обработки информации в электронных таблицах (ЭТ). Структура электронной таблицы. Типы данных: числа, формулы, текст 38 KB
  Типы данных: числа формулы текст. Графическое представление данных. Электронные таблицы Электронная таблица это программа обработки числовых данных хранящая и обрабатывающая данные в прямоугольных таблицах. Можно вводить и изменять данные одновременно на нескольких рабочих листах а также выполнять вычисления на основе данных из нескольких листов.
20017. Интернет. Информационные ресурсы и сервисы компьютерных сетей: Всемирная паутина, файловые архивы, интерактивное общение. Назначение и возможности электронной почты. Поиск информации в Интернете 72 KB
  Адресация в Интернет Для того чтобы связаться с некоторым компьютером в сети Интернет Вам надо знать его уникальный Интернет адрес. Существуют два равноценных формата адресов которые различаются лишь по своей форме: IP адрес и DNS адрес. IP адрес IP адрес состоит из четырех блоков цифр разделенных точками. Благодаря такой организации можно получить свыше четырех миллиардов возможных адресов.
20018. Виды информационных моделей (на примерах). Реализация информационных моделей на компьютере. Пример применения электронной таблицы в качестве инструмента математического моделирования 55.5 KB
  Понятие модели. Пример применения электронной таблицы в качестве инструмента математического моделирования. Моделирование Человечество в своей деятельности научной образовательной постоянно созадет и использует модели окружающего мира. Строгие правила построения моделей сформулировать невозможно однако человечество накопило богатый опыт моделирования различных объектов и процессов.
20019. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение, передача и обработка информации 48 KB
  Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки.
20020. Измерение информации: содержательный и алфавитный подходы. Единицы измерения информации 39 KB
  Измерение информации: содержательный и алфавитный подходы. Единицы измерения информации. Определить понятие количество информации довольно сложно. один из основоположников кибирнетиеи американский математик Клож Шенон развил вероятностный подход к измерению количества информации а работы по созданию ЭВМ привели к объемному подходу .
20021. Дискретное представление информации: двоичные числа; двоичное кодирование текста в памяти компьютера. Информационный объем текста 40.5 KB
  Дискретное представление информации: двоичные числа; двоичное кодирование текста в памяти компьютера. Кодирование информации Представление информации происходит в различных формах в процессе восприятия окружающей среды живыми организмами и человеком в процессах обмена информацией между человеком и человеком человеком и компьютером компьютером и компьютером и так далее. Преобразование информации из одной формы представления...
20022. Дискретное представление информации: кодирование цветного изображения в компьютере (растровый подход). Представление и обработка звука и видеоизображения. Понятие мультимедиа 40.5 KB
  Дискретное представление информации: кодирование цветного изображения в компьютере растровый подход. Кодирование информации в компьютере Вся информация которую обрабатывает компьютер должна быть представлена двоичным кодом с помощью двух цифр 0 и 1. Это явилось причиной того что в компьютере обязательно должно быть организовано два важных процесса: кодирование которое обеспечивается устройствами ввода при...
20023. Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации 25.5 KB
  Процесс передачи информации источник и приемник информации канал передачи информации. Скорость передачи информации. Передача хранение и обработка информации представляют собой информационные процессы протекающие в социальных биологических и технических системах. Передача это процесс распространения информации в пространстве.
20024. Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя (на примере учебного исполнителя). Свойства алгоритма. Способы записи алгоритмов; блок-схемы 53.5 KB
  Понятие алгоритма. Исполнитель алгоритма. Свойства алгоритма. Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.