метод штрафных функций для решения задач выпуклого программирования. Реферат.

Реферат

Рассмотрен метод штрафных функций для решения задач выпуклого

программирования.

Рассматриваются основные теоретические положения метода штрафных функций.

Применение метода штрафов описывается на примере семи основных наиболее

часто применяемых штрафных функций. Приведены некоторые оценки сходимости

этих функций, а также вычислительные аспекты данного метода.

Написана программа, позволяющая эффективно решать задачи выпуклого

программирования методом штрафных функций с помощью ЭВМ.

Ключевые слова: оптимизационная задача, выпуклое программирование,

штрафная функция, глобальный минимум, релаксационный метод.

Объем пояснительной записки 24 страницы.

Использовано 7 источников литературы.

Содержание

Введение 5

1. Постановка задачи выпуклого программирования 7

2. Теоретические положения метода штрафных функций 8

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

2.2 Характеристические свойства штрафных функций 8

2.3 Поиск локальных экстремумов 11

2.4 Сходимость метода штрафов 13

3. Реализация метода штрафов на ЭВМ 17

Заключение 19

Список литературы 20

Приложение 1. Текст программы 21

Приложение 2. Результаты работы программы 24

Введение

Интенсивное развитие методов математического программирования связано с

тем, что оптимизационные задачи играют большую роль в самых различных

областях человеческой деятельности. Сейчас основное внимание уделяется

развитию методов выпуклого программирования. Построен целый ряд

алгоритмов, проведены исследования их сходимости. Однако эти алгоритмы

применяются довольно редко, и нет достаточной информации, позволяющей

судить об их сравнительной эффективности. При использовании методов

выпуклого программирования решение исходной задачи обычно определяется как

предел минимизирующей последовательности решений более простых (

вспомогательных ) экстремальных задач. Полагая в основу тип

вспомогательных задач, большинство методов выпуклого программирования

можно разделить на две группы.

* К первой группе относятся методы, при реализации которых на каждом

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

функции при линейных ограничениях. Это различные варианты метода

возможных направлений (метод отсечения, проекций градиента ).

* Ко второй группе относятся методы, с помощью которых искомое решение

определяется как предел последовательности безусловных минимумов

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

штрафных функций, центров, множителей Лагранжа.

Первые оценки сходимости метода штрафных функций были получены Л. Битнером

и И.И. Бреминым, установившими оценки сходимости логарифмического и

квадратичного штрафов для решения задач выпуклого программирования. Б.Т.

Поляком получены оценки быстроты сходимости метода штрафов в окрестности

локального экстремума для выпуклых задач с ограничениями в форме

равенства.

1. Постановка задачи выпуклого программирования.

Задачей выпуклого программирования будем называть задачу:

0x01 graphic

(1.1)

Если f(x) - выпуклая функция, а G - выпуклое множество, обычно G задается

в виде:

0x01 graphic

(1.2)

где 0x01 graphic

- заданные выпуклые функции.

Теорема 1.1.0x01 graphic

Пусть f(x) - выпуклая функция, заданная на выпуклом замкнутом множестве D,

тогда любой локальный минимум f(x) на множестве D является глобальным.

Следствие. Если f(x) - строго выпуклая функция, то ее глобальный минимум

на выпуклом замкнутом множестве D достигается в единственной точке.

Легко видеть, что в задаче выпуклого программирования не существует

локальных минимумов со значением функции f большим, чем 0x01 graphic

,0x01 graphic

а множество точек

0x01 graphic

является выпуклым и замкнутым.

2. Теоретические положения метода штрафных функций.

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

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

приближенно к задаче минимизации некоторой функции, представляющей собой

сумму данной целевой функции невязок в ограничениях задачи.

Пусть дана задача выпуклого программирования (1.1) - (1.2). Вводится

вспомогательная функция 0x01 graphic

, следующего вида

0x01 graphic

где 0x01 graphic

- некоторый векторный параметр.

Функцию 0x01 graphic

называют штрафной функцией, если она обладает следующими свойствами:

0x01 graphic

т.е. при больших 0x01 graphic

функция 0x01 graphic

в области допустимых решений D близка f(x), а вне области D принимает

значения порядка +0x01 graphic

2.2. Характеристические свойства штрафных функций.

Хотя значительная часть приведенных ниже теоретических результатов о

характеристике штрафных функций и сходимости метода не зависит от того,

как задано множество G, способ задания множества G весьма важен как для

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

свойств, связанных с соотношениями двойственности. Обычно, когда речь идет

о численных методах выпуклого программирования, предполагается, что

0x01 graphic

где 0x01 graphic

- выпуклая вектор - функция,

0x01 graphic

Будем рассматривать функции 0x01 graphic

вида

0x01 graphic

В этом случае удобно проводить исследование свойств систем функций 0x01

graphic

на языке порождающих их функций одной переменной 0x01 graphic

Мы ограничимся рассмотрением нескольких порождающих функций, наиболее

часто употребляемых на практике:

0x01 graphic

(2.2.1)

0x01 graphic

(2.2.2)

0x01 graphic

(2.2.3)

0x01 graphic

(2.2.4)

0x01 graphic

(2.2.5)

0x01 graphic

(2.2.6)

0x01 graphic

(2.2.7)

Предполагается во всех случаях, что 0x01 graphic

Для краткости условимся обозначать номерами с (1) по (7) функции штрафа

Vk,, порожденные соответственно функциями (2.2.1) - (2.2.7).

Отметим, что при использовании второй из этих функций для минимизации

можно применять градиентные методы. Однако скорость сходимости этих

методов при больших значениях 0x01 graphic

медленная. При использовании функций (7) и (6) требуется определять

предварительную точку 0x01 graphic

, что несущественно, если используются функции (1) - (3) и (5).

Кроме того, необходимо, чтобы используемый метод минимизации

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

информацией о функциях 0x01 graphic

в int G. Иначе говоря, требуется некоторая модификация методов безусловной

минимизации.

Такие проблемы не возникают при использовании штрафных функций (1) - (3) и

(5). С другой стороны, как показывают теоретические исследования и анализ

экспериментов, функции (6) и (7) оказываются предпочтительнее, чем (2), с

точки зрения быстроты сходимости процесса. Использование функций (1) - (3)

существенно ограничивает возможности эффективного решения вспомогательных

задач, так как эти функции не обладают гладкостью, достаточной для

применения процедур безусловной минимизации высокого порядка.

В предположении, что 0x01 graphic

- возрастающая последовательность и вспомогательные задачи решаются точно,

применение штрафных функций (1), (2), (4) и (5) гарантирует монотонность

последовательностей 0x01 graphic

и 0x01 graphic

, где 0x01 graphic

, если Vk имеет вид (1), (2) или 0x01 graphic

, для функций (6) и (7). Это учитывается при изменении параметра 0x01

graphic

. Порождающие функции (2) и (3) являются аналитическими, и их применение

не ограничивает гладкости 0x01 graphic

на всем Rn . Штрафная функция (3) обладает относительно малым порядком

роста вне допустимой области, что избавляет о необходимости заботиться о

хорошем начальном приближении 0x01 graphic

Конечно, отмеченные выше особенности различных функций штрафа не дают

достаточных оснований предпочесть одну функцию другой, а, скорее,

позволяют построить гипотеза о предпочтении, для проверки которых

потребуются более тщательные исследования (априорные оценки, рекомендации

по выбору параметров 0x01 graphic

и т.д.) и прежде всего большой численный эксперимент.

2.3. Поиск локальных экстремумов.

Как уже отмечалось, решение невыпуклых экстремальных задач встречает

серьезные трудности, связанные с отсутствием удовлетворительных методов

безусловной минимизации невыпуклых функций. При реализации метода штрафных

функций на каждом шаге ограничиваемся отысканием некоторых локальных

экстремумов вспомогательных функций. При этом выбор локальных минимумов во

вспомогательных задачах должен быть организован так, чтобы любая их

предельная точка являлась локальным минимумом в исходной задаче (нетрудно

привести пример, показывающий, что этим свойством обладает не каждая

последовательность локальных минимумов, даже если ее предельные точки

принадлежат G).

Обозначим через А* множество таких локальных минимумов функции f на G, что

0x01 graphic

для 0x01 graphic

Теорема 2.1. Пусть А* - непустой компакт, 0x01 graphic

; S - компакт такой, что 0x01 graphic

и 0x01 graphic

для 0x01 graphic

; точки 0x01 graphic

выбираются из условий 0x01 graphic

0x01 graphic

где 0x01 graphic

Тогда начиная с некоторого номера, 0x01 graphic

и 0x01 graphic

и любая предельная точка последовательности 0x01 graphic

принадлежит А*.

Доказательство. Существование точек 0x01 graphic

легко получить, применяя следующее утверждение:

Утверждение. Пусть 0x01 graphic

- непрерывная функция, 0x01 graphic

- компакт и существует такая точка x0x01 graphic

,что 0x01 graphic

0x01 graphic

. Тогда найдется точка 0x01 graphic

, для которой 0x01 graphic

. Любая предельная точка последовательности 0x01 graphic

принадлежит А*0x01 graphic

, причем А*0x01 graphic

совпадает с множеством 0x01 graphic

. Так как 0x01 graphic

, для больших k имеем 0x01 graphic

. Ч.т.д.

Отметим, что существование компакта S с указанными свойствами вытекает из

следующего утверждения.

Лемма 2.1. Пусть f - непрерывная функция, G - замкнутое множество, А* -

непустой компакт. Тогда существует компакт S такой, что 0x01 graphic

и 0x01 graphic

для 0x01 graphic

Доказательство. Рассмотрим последовательность компактов 0x01 graphic

. Легко проверить, что 0x01 graphic

. Если утверждение леммы неверно, то при каждом k найдется точка 0x01

graphic

такая, что 0x01 graphic

. Не умаляя общности, можно считать, что 0x01 graphic

. Точка 0x01 graphic

при этом должна принадлежать А*0x01 graphic

. Если 0x01 graphic

при всех k, то 0x01 graphic

не может быть локальным минимумом, вопреки определению А*. Если же 0x01

graphic

при некотором k, то из соотношения

0x01 graphic

следует, что 0x01 graphic

, причем 0x01 graphic

содержится в 0x01 graphic

вместе с некоторой окрестностью 0x01 graphic

, так что 0x01 graphic

. Тем самым 0x01 graphic

- локальный минимум функции f на G и 0x01 graphic

, что противоречит выбору последовательности 0x01 graphic

. Ч.т.д.

Мы рассмотрели случаи, когда ограничения в задаче в виде неравенств. Когда

среди ограничений задачи имеются равенства, применяют штрафную функцию,

порождаемую 0x01 graphic

. Отметим, что учет ограничения 0x01 graphic

с помощью этой функции то же самое, что и учет эквивалентной пары

ограничений 0x01 graphic

, - 0x01 graphic

с помощью функции (3).

2.4. Сходимость метода штрафов.

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

том смысле, что для отыскания каждой точки последовательности 0x01 graphic

, как правило, приходится применять какой - либо бесконечношаговый метод

безусловной минимизации.

Скорость сходимости метода штрафов естественно оценивать числом больших

штрафов, каждый из которых состоит в отыскании очередной точки 0x01

graphic

. Такая оценка, с одной стороны, не зависит от выбора алгоритма решения

вспомогательной задачи. С другой стороны, с ее помощью нетрудно получить

оценку числа малых шагов, если, конечно, известна скорость сходимости

выбранного алгоритма безусловной минимизации.

Следует отметить, что метод штрафов не вполне отвечает обычным

представлениям об итерационных процессах: множество 0x01 graphic

точек 0x01 graphic

, которые могут быть получены на k-ом шаге, не зависит от выбора 0x01

graphic

. Тем самым оценка величин 0x01 graphic

и 0x01 graphic

, где 0x01 graphic

, не должна зависеть ни от начальной точки 0x01 graphic

, ни от результата предыдущих итераций.

Получим некоторые априорные оценки быстроты сходимости метода штрафов при

решении задач выпуклого программирования.

Определим систему функций 0x01 graphic

, следующим образом:

а) 0x01 graphic

- выпуклая функция, 0x01 graphic

;

b) 0x01 graphic

для всех 0x01 graphic

;

c) известна функция 0x01 graphic

такая, что 0x01 graphic

, причем 0x01 graphic

;

d) 0x01 graphic

;

e) известна функция 0x01 graphic

такая, что при любом 0x01 graphic

для 0x01 graphic

справедливо неравенство 0x01 graphic

, причем 0x01 graphic

Рассмотрим теперь систему функций 0x01 graphic

, 0x01 graphic

, задаваемых соотношением

0x01 graphic

(2.4.1)

где 0x01 graphic

удовлетворяют условиям a) - e) (будем при этом говорить, что система 0x01

graphic

обладает 0x01 graphic

- свойством). Нетрудно проверить, что система функций (2.4.1)

удовлетворяет следующему утверждению.

Утверждение. Пусть в задаче выпуклого программирования (1.1) - (1.2)

множество G телесно, 0x01 graphic

не пусто и ограничено, функции 0x01 graphic

выпуклы и удовлетворяют условию

0x01 graphic

Тогда, начиная с некоторого k, существуют точки 0x01 graphic

, удовлетворяющие неравенству 0x01 graphic

для всех 0x01 graphic

; последовательность 0x01 graphic

ограничена, любая ее предельная точка 0x01 graphic

принадлежит G и

0x01 graphic

Теорема 2.2. Пусть f сильно выпукла с константой 0x01 graphic

и для решения задачи выпуклого программирования применяется метод штрафов

с градиентным критерием остановки, 0x01 graphic

Тогда если функции штрафа обладают 0x01 graphic

- свойством, то существуют такие 0x01 graphic

, что

0x01 graphic

при 0x01 graphic

(2.4.2)

0x01 graphic

(2.4.3)

при 0x01 graphic

, где 0x01 graphic

и 0x01 graphic

- число элементов в множествах 0x01 graphic

и 0x01 graphic

соответственно, 0x01 graphic

Отметим, что неравенства (2.4.2), (2.4.3) не содержат 0x01 graphic

, однако от выбора последовательности 0x01 graphic

зависят величины 0x01 graphic

Среди рассмотренных нами систем функций штрафа 0x01 graphic

- свойством обладает лишь система (5) при 0x01 graphic

Аналогично могут быть установлены оценки быстроты сходимости метода при

некоторых других функциях штрафа. Так, если 0x01 graphic

, при использовании функции (6) в тех же условиях имеем неравенство

0x01 graphic

а если взять 0x01 graphic

, то в случае функции (4) получим

0x01 graphic

Эти оценки улучшаемы по порядку в данном классе задач.

Если известны удовлетворительные приближения для оптимальных множителей

Лагранжа, то оценки быстроты сходимости метода штрафов можно получить с

помощью решения достаточно простых вспомогательных экстремальных задач.

3. Реализация метода штрафов на ЭВМ.

Для решения задач выпуклого программирования на ЭВМ удобно использовать

метод обобщенного градиента, согласно которому точка 0x01 graphic

получается как предел последовательности точек

0x01 graphic

где 0x01 graphic

- числовой параметр, 0x01 graphic

- значение в точке 0x01 graphic

обобщенного градиента функции 0x01 graphic

, определяемого следующим образом:

0x01 graphic

Таким образом, если 0x01 graphic

, то 0x01 graphic

, т.е., получаем обычный метод градиента для функции 0x01 graphic

. Если 0x01 graphic

, то обобщенный градиент представляет собой линейную комбинацию градиентов

целевой функции 0x01 graphic

и функций, соответствующих тем ограничениям, которые не выполняются в

точке x.

Для примера реализуем на ЭВМ решение задачи Розена - Сузуки методом

штрафных функций.

Задача Розена - Сузуки:

0x01 graphic

при следующих ограничениях:

0x01 graphic

Оптимальным решением этой задачи является

0x01 graphic

Будем решать эту задачу методом штрафных функций, а полученную задачу

минимизации методом обобщенного градиента.

В качестве параметров, выберем 0x01 graphic

и 0x01 graphic

Программа написана на языке С++.

Заключение.

В данной работе были рассмотрены основные теоретические положения метода

штрафных функций, получены некоторые оценки сходимости для наиболее

употребляемых штрафных функций, а также их характеристические свойства.

Результатом работы является программа на языке С++, решающая методом

штрафных функций задачи выпуклого программирования, и, в частности, задачу

Розена - Сузуки.

Список литературы.

1. Васильев Ф. П. Численные методы решения экстремальных задач - М.;

Наука, 1980

2. Гроссман К. Г., Каплан А. А. Нелинейное программирование на основе

безусловной минимизации - Новосибирск: Наука, 1981

3. Кудрявцев Е. М. Исследование операций в задачах, алгоритмах,

программах - М.: Радио и связь, 1984

4. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации -

М.: Наука, 1978

5. Романовский И. В. Алгоритмы решения экстремальных задач - М.: Наука,

1982

6. Шун Терри Е. Решение инженерных задач на ЭВМ - М.: Мир, 1977.

Приложение 1.

Текст программы.

#include

double fmin(double x1,double x2,double x3,double x4)

{

double y;

y=x1*x1+x2*x2+2*x3*x3+x4*x4-5*x1-5*x2-21*x3+7*x4;

return y;

}

double straf1(double x1,double x2,double x3,double x4)

{

double s;

if ((x1*x1+x2*x2+x3*x3+x4*x4+x1-x2+x3-x4) <8.0)

s=0.0; else s=1.0;

return s;

}

double straf2(double x1,double x2,double x3,double x4)

{

double y;

if ((x1*x1+2*x2*x2+x3*x3+2*x4*x4-x1+x4) <10.0) y=0.0;

else y=1.0;

return y;

}

double straf3(double x1,double x2,double x3,double x4)

{

double y;

if ((2*x1*x1+x2*x2+x3*x3+2*x1-x2) <5.0) y=0.0;

else y=1.0;

return y;

}

main()

{

int i,j,n;

float f[4];float f2[4];float g[4][4];float g2[4][4];float b[4];

double x1=-0.01,x2=0.99,x3=1.99,x4=-0.99;double alpha[3];

double y1=0.0,y2=0.0,y3=0.0,y4=0.0,delta,h=0.00001;

double eps=0.00001;

clrscr();

f2[0]=f2[1]=f2[3]=1.0;

f2[2]=2.0;

f[0]=f[1]=-5.0;

f[2]=-21.0;

f[3]=7.0;

g2[0][0]=g2[0][1]=g2[0][2]=g2[0][3]=1.0;

g[0][0]=g[0][2]=1.0;

g[0][1]=g[0][3]=-1.0;

g2[1][0]=g2[1][2]=1.0

;g2[1][1]=g2[1][3]=2.0;

g[1][0]=-1.0;

g[1][3]=1.0;

g[1][1]=g[1][2]=0.0;

g2[2][0]=2;

g2[2][1]=g2[2][2]=1.0;

g2[2][3]=0.0;

g[2][0]=2.0;

g[2][1]=-1.0;

g[2][2]=g[2][3]=0.0;

alpha[0]=2.0;

alpha[1]=2.0;

alpha[2]=2.0;

{

x1-=h*y1;

x2-=h*y2;

x3-=h*y3;

x4-=h*y4;

y1=(2*x1*f2[0]+f[0])+alpha[0]*straf1(x1,x2,x3,x4)*(2*x1*g2[0][0]+g[0][0])+

alpha[1]*straf2(x1,x2,x3,x4)*(2*x1*g2[1][0]+g[1][0])+alpha[2]*

straf3(x1,x2,x3,x4)*(2*x1*g2[2][0]+g[2][0]);

y2=(2*x2*f2[1]+f[1])+alpha[0]*straf1(x1,x2,x3,x4)*(2*x2*g2[0][1]+g[0][1])+

alpha[1]*straf2(x1,x2,x3,x4)*(2*x2*g2[1][1]+g[1][1])+alpha[2]*

straf3(x1,x2,x3,x4)*(2*x2*g2[2][1]+g[2][1]);

y3=(2*x3*f2[2]+f[2])+alpha[0]*straf1(x1,x2,x3,x4)*(2*x3*g2[0][2]+g[0][2])+

alpha[1]*straf2(x1,x2,x3,x4)*(2*x3*g2[1][2]+g[1][2])+alpha[2]*

straf3(x1,x2,x3,x4)*(2*x3*g2[2][2]+g[2][2]);

y4=(2*x4*f2[3]+f[3])+alpha[0]*straf1(x1,x2,x3,x4)*(2*x4*g2[0][3]+g[0][3])+

alpha[1]*straf2(x1,x2,x3,x4)*(2*x4*g2[1][3]+g[1][3])+alpha[2]*

straf3(x1,x2,x3,x4)*(2*x1*g2[2][3]+g[2][3]);

delta=fmin(x1-h*y1,x2-h*y2,x3-h*y3,x4-h*y4)-fmin(x1,x2,x3,x4);

alpha[0]*=2.0;

alpha[2]*=2.0;

printf(\"\\nfmin=%f x1=%f x2=%f x3=%f x4=%f\",fmin(x1,x2,x3,x4),x1,x2,x3,x4);

}

while(fmin(x1-h*y1,x2-h*y2,x3-h*y3,x4-h*y4)< 0.0);

getch();

}

Приложение 2.

Результаты работы программы.

0x01 graphic