Метод проекции антиградиента

Метод проекции антиградиента Курсовая работа

• Введение
• 1. Численные методы нелинейного программирования
• 1.1 Виды численных методов нелинейного программирования
• 1.2 Оценка численных методов нелинейного программирования
• 2. Метод проекции антиградиента
• 2.1 Задача
• Заключение
• Список использованной литературы

Проникновение количественных методов в экономику, технику и другие области человеческой деятельности, которое в последние десятилетия неуклонно возрастает, усиливает внимание специалистов в области прикладных наук к математическому аппарату, используемому в интересующих их областях, и привлекает все большее число математиков к разработке математической проблематики прикладного характера. В последнее время все чаще возникают задачи, сводящиеся к схеме нелинейного программирования. Вместе с тем имеющаяся на русском языке монографическая литература по нелинейному программированию (в отличие от линейного программирования) совершенно недостаточна. Нелинейное программирование в определенном смысле подобно линейному программированию, в нем отсутствует лишь требование линейности функций, хотя, конечно теория нелинейного программирования охватывает и линейный случай.

Методы оптимизации — это методы поиска лучшего результата, оптимального решения, лучшего пути. Задачей оптимизации называется задача о поиске экстремума функции или функционала на заданном множестве допустимых решений. А постановка задачи — это определенные действия для выполнения конкретной задачи. Сама по себе постановка задачи оптимизации проста и естественна: заданы множество? и функция ѓ(x), определенная на ?; требуется найти точки минимума или максимума функции ѓ на ?. Запишем задачу на минимум в виде:

ѓ(x)>min, x? (1)

При этом ѓ будем называть целевой функцией,? — допустимым множеством, любой элемент x? — допустимой точкой задачи ѓ(x)>min.

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

Существует множество методов поиска локального экстремума. В данной курсовой работе будут рассмотрены численные методы нелинейного программирования и наиболее подробно метод проекции антиградиента.

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

· ознакомиться с задачей нелинейного программирования;

· рассмотреть численные методы нелинейного программирования;

· изучить метод проекции антиградиента;

· решить тестовые задачи в MS Excel;

· сделать выводы.

1. Численные методы нелинейного программирования

Задача нелинейного программирования встречается в естественных и физических науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством. В наиболее абстрактной форме задача нелинейного программирования ставится так: что-то должно быть максимизировано (или минимизировано); однако ограничения лимитируют действия, которые мы можем принять для достижения максимума (или минимума).

Задачи оптимизации (экстремальные задачи) На минимум:

при ограничениях На максимум:

при ограничениях называются задачами нелинейного программирования (сокращенно задачами НЛП), если среди функцийѓ, g1… gm, h1…, hk имеется хотя бы одна нелинейная функция. Задачи НЛП, как и любые другие задачи оптимизации, являются математическими моделями некоторых практических задач принятия решения.

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

1) проблема существования оптимального решения;

2) проблема установления необходимых и достаточных признаков оптимальности (характерных свойств, присущих точкам минимума и максимума);

3) разработка способов вычисления оптимальных решений (методов решения задач НЛП).

Известно достаточно много численных методов решения общей задачи нелинейного программирования. Во многих из них реализованы идеи, реализованные в численных методах безусловной минимизации. Основное отличие состоит в том, что при решении этой задачи необходимо учитывать ограничения, задающие допустимое множество Х Є R?, на котором нужно найти точку x* Є X минимума целевой функции ѓ(x). Далее представлены наиболее часто применяемые на практике численные методы решения такой задачи.

1.1 Виды численных методов нелинейного программирования

Метод условного градиента или метод линейной аппроксимации (линеаризации) целевой функции. Применение данного метода оправдано лишь в том случае, когда задача вида ѓ(x)>min, x Є X, т. е. задача минимизации линейной функции на X, решается достаточно просто. Но если множество X имеет сложную структуру, то задача трудна.

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

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

Проективные методы образуют целое семейство. Иногда их называют методами допустимых направлений или градиентными методами с большой длиной шага. Сущность этих методов заключается в следующем: линейные и линеаризированные ограничения образуют линейное многообразие (определяемое пересечением ограничений), на которое можно спроектировать выбранное направление поиска S в пространстве решений. То, что в методах подразумевается под проекцией, ассоциируется с понятием проекции вектора, описывающего локальное приращение функции при перемещении в заданном направлении.

1.2 Оценка численных методов нелинейного программирования

нелинейный программирование антиградиент проекция

На вопрос о том, какой из методов нелинейного программирования наилучший можно сказать при оценивании «качества» того или иного алгоритма. Критерии оценивания:

1) время необходимое для реализации серии вычислительных процедур (число операций и время их выполнения);

2) степень сложности задачи (размерность, число ограничений в виде равенств, число ограничений в виде неравенств);

3) точность решения по отношению к оптимальному значению х* или по отношению к ѓ(х*), h (x*), g (x*) и ѓ(х*);

4) простота практического использования алгоритма (время, необходимое для ввода исходных данных и записи функций в память ЭВМ);

5) простота машинной программы, реализующей рассматриваемый алгоритм;

6) алгоритм должен позволять решать задачи, которые представляют практический интерес (нельзя полагать, что какой-либо из алгоритмов окажется эффективным при решении любой задачи).

2. Метод проекции антиградиента

Антиградиент дает только направление минимизации, но не длину шага. Направление проекции антиградиента является локально наилучшим направлением движения к условному минимуму целевой функции. При поиске условного максимума используют проекцию градиента. Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению. Он указывает сторону наибольшего убывания функции в данной точке. Все проективные методы предполагают реализацию на каждом k-ом этапе указанной ниже последовательности шагов:

1) алгоритм начинает работу в допустимой точке х;

2) определяется допустимое направление s;

3) в допустимом направлении выбирается шаг длиной, минимизирующий ѓ(х), но в то же время сохраняющий вектор х=х+s допустимым.

Целевая функция метода проекции антиградиента имеет вид. И задача оптимизации задана следующим образом. Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задается антпградиентом :

(2)

Где выбирается

· постоянной, в этом случае метод может расходиться;

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

· наискорейшим спуском.

Алгоритм:

1) вычислить .

2) если, то вычислить по формуле и закончить вычисления. В противном случае — продолжить вычисления, переходя к пункту 3.

3) определить максимальную длину шага:

4) решить задачу одномерного поиска:

5) положить .

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

1.

2.

Здеcь — значение, полученное послего шага оптимизации. — наперед заданное положительное число Данный алгоритм можно легко распространить на неравенства, используя либо дополнительные переменные, либо активные ограничения.

Рисунок 1

Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, «уменьшенному в раз» .

Линейные ограничения типа равенства. Пусть в задаче оптимизации допустимое множество? определено ограничениями типа равенства, то есть имеет вид

?={x Є R?: (ai;x) = bi, i=} (3)

а целевая функция ѓ(х) дифференцируема в R?. Предположим, что известна точка х?. Рассмотрим функцию (у)=ѓ(х+P*y), yR? где матрица P определена соотношением

P= А (АА) А (4)

Для этой функции в силу правила дифференцирования сложной функции и симметричной матрицы Р справедливо равенство

grad (y)=P* grad ѓ(x) (5)

Прежде всего убедимся, что х*?. Используя представление х*=х+Р*у* (6)

и условие х?, заключаем, что (а, х*)=(а, х)+(а, Р*у*)=(а, х)=b, i=. Поскольку вектор Р*у* ортогонален каждому вектору линейного подпространства ?, в том числе и векторам а. Следовательно, х* ?.

Так как у* является стационарной точкой функции (у), то grad (y*)=0, и поэтому, учитывая grad (y)=P* grad ѓ(x) и P= А (АА) А при х=х* и у=у*, находим Р* grad ѓ(x*)= grad ѓ(x*) — А (АА) grad ѓ(x*)= grad ѓ(x*)+ А= grad ѓ(x*)+а=0, (7)

где = -(АА)А grad ѓ(x*), а — координаты вектора R?. Представив ограничения (3) в виде ѓ(х)=(а, х)-b=0, i=, и учитывая равенства gradѓ(x*)=а, заключаем, что точка х* является стационарной точкой функции Лагранжа

L (x,)=ѓ(x)+((a, x)-b) (8)

то есть удовлетворяет необходимому условию минимума целевой функции ѓ(х) на множестве ?.

Стационарные точки целевой функции ѓ(х) на допустимом множестве можно определять, решая задачу безусловной минимизации функции (у). В общем случае функция (у) может иметь несколько стационарных точек, причем каждой ее стационарной точке у* будет соответствовать стационарная точка (6) функции Лагранжа (8). Через минимизацию функции (у) можно найти все стационарные точки целевой функции. Однако, если целевая функция является выпуклой функцией на выпуклом множестве ?, то для решения задачи минимизации такой функции достаточно найти хотя бы одну стационарную точку целевой функции в ?, поскольку в любой стационарной точке выпуклая функция достигает наименьшего значения. Строго выпуклая функция может иметь лишь одну стационарную точку, так как она может достигать наименьшего значения на выпуклом множестве только в одной точке.

Нелинейные ограничения. Если среди ограничений в задаче оптимизации есть нелинейные, то поиск минимума целевой функции ѓ(х) на допустимом множестве усложняется. Пусть для определенности ?={хR?: g (x)?0, i=}, где g (x) — дифференцируемые функции на k-ой итерации известна точка х?, для которой активными являются ограничения с индексами i={iN: g (x)=0}. Составим матрицу, строками которой являются матрицы-строки (grad g (x)), i, предполагая, что они линейно независимы. Тогда проекционная матрица =I- () спроектирует антиградиент w= -grad ѓ(x) целевой функции в точке x на направление, ортогональное градиентам всех функций g (x), i, задающих в этой точке активные ограничения. Но в общем случае может оказаться, что это направление будет направлением спуска, поскольку оно может лишь касаться в точке x? границы? множества ?.

2.1 Задача

В данном случае целевая функция является квадратичной и ее можно записать в виде где

Единственное ограничение задачи имеет вид, где. В качестве начальной возьмем точку, а в условии прекращения поиска положим .

Вычислим антиградиент

И градиент левой части ограничения

.

Рассмотрим подробнее первую (k=1) итерацию при решении этой задачи методом проекции антиградиента.

1) поскольку, то антиградиент и градиент в начальной точке ортогональны. Следовательно, нет необходимости вычислять проекционную матрицу, которая в данном случае является единичной .

2) при помощи исчерпывающего спуска из точки в направлении вектора р находим значение

И точку. Ясно, что продвижение точки в направлении вектора выводит за пределы допустимого множества, то есть, так как. Точка лежит на касательной кривой, заданной уравнением, в точке .

3) проектируем точку на допустимое множество Х, то есть найдем точку кривой В, наименее удаленную от точки. Так как функция дифференцируемая, то точка будет основанием кратчайшего перпендикуляра, опущенного из на кривую В. Эту точку можно найти методом последовательных приближений. где. В качестве нулевого приближения при s=1 можно принять, а условием прекращения последовательных приближений можно считать выполнение неравенства где — заданный параметр точности. При выполнении этого неравенства полагаем и. Выбирая получаем, при этом .

4) проверяем условие прекращения итераций:. Так как требуемая точность еще не достигнута, поиск точки минимума целевой функции на множестве Х следует продолжить. Для этого переходим к пункту 1, заменив точку на найденную на первой итерации точку .

Таблица 1. Результаты расчетов на четырех итерациях.

Таким образом, результат четвертой итерации с заданной точностью совпал с точным решением задачи .

Заключение

Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.

В данной курсовой работе была описана задача нелинейного программирования и рассмотрены некоторые численные методы. Наиболее подробно был изучен метод проекции антиградиента. Его алгоритм был реализован при решении задачи. Также тестовые задачи были решены в среде MS Excel. Подводя итоги, можно сказать, что направление проекции антиградиента является локально наилучшим направлением движения к условному минимуму целевой функции. При поиске условного максимума используют проекцию градиента.

1. Аттетков, А. В. Методы оптимизации/ А. В. Аттетков, С. В. Галкин, В. С. Зарубин. — М., МГТУ им. Н. Э. Баумана, 2010, 371 с.

2. Банди, Б Методы оптимизации. Вводный курс/ Б. Банди. — М., Радио и связь, 1988, 51 с.

3. Зангвил, У. И. Нелинейное программирование/ У. И. Зангвил; под общ. ред. В. М. Гальперина; - М., Советское радио, 2008, 11 с.

4. Интрилигатор, М. Математические методы оптимизации и экономическая теория/ М. Интрилигатор. — М., Айрис пресс, 2012, 57 с.

5. Сухарев, А. В. Курс методов оптимизации/ А. Г. Сухарев, А. В. Тимохов, В. В. Федоров. — М., ФИЗМАТЛИТ, 2009, 256 с.

6. Харчистов, Б. Ф Методы оптимизации/ Б. Ф. Харчистов. — Таганрог, ТРТУ, 56 с.

7. Химмельблау, Д. Прикладное нелинейное программирование/ Д. Химмельблау; под общ. ред. Быховского М. Л. — М., Мир, 2006, 72 с.

8. Википедия [Электронный ресурс]/ Градиентный метод; 2009. URL: http://ru.wikipedia.org/wiki, свободный