Методы оптимизации

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Сибирский государственный индустриальный университет»

Институт открытого образования

Кафедра автоматизации и информационных систем

Курсовая работа

по дисциплине «Методы оптимизации»

Выполнил:

студент группы ЗАТПу-15

Борисова Н.А.

Шифр 14321

Проверил:

д. т. н, профессор Кулаков С.М.

Новокузнецк

2018



Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Сибирский государственный индустриальный университет»

Институт информационных технологий и автоматизированных систем

Кафедра автоматизации и информационных систем

УТВЕРЖДАЮ

Заведующий кафедрой АИС

«_______» ________________2018 г.

ЗАДАНИЕ

на курсовую работу (курсовой проект)

по дисциплине «Методы оптимизации»

студента Борисовой Натальи Александровны

группа ЗАТПу-15

Тема курсовой работы (курсового проекта) «Освоение алгоритма решения типовой задачи оптимизации на учебном примере»

Сроки сдачи студентом законченной работы « » 2018 г.

Исходные условия и данные к работе (объект исследования, методы и т.д.): Метод Флетчера-Ривса

Цель работы: Методом Флетчера-Ривса найти минимум целевой функции с учетом ограничений

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

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

Вариант 5

Метод Флетчера-Ривса

Функция

Ограничения

Руководитель работы (проекта) ____________ д. т. н, профессор С.М. Кулаков

Задание к исполнению принято Борисовой Н.А. «25» января 2017 г.



Содержание

Введение

1. Формулировка математической задачи оптимизации

2. Минимизация функций. Основные положения

3. Метод сопряженных градиентов

4. Алгоритм метода Флетчера-Ривса

5. Минимизация функции методом Флетчера-Ривса

6. Программная реализация метода

Заключение

Список использованных источников



Введение

Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходиться заниматься в повседневной жизни. Термином «оптимизация» в литературе обозначает процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

Развитие численных линейных методов решения задач линейного программирования очень важно в нынешнее время, поскольку сложность решаемых задач взваливает всю работу на современные ЭВМ, работающие с единицами и нолями, и « неподозревающих» о существовании производных, первообразных, интегралов и пр. И нахождение оптимального решения сводится к представлению его в виде численных методов.

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

Цель данной работы - освоить алгоритм решения типовой задачи оптимизации на учебном примере. Для достижения поставленной цели необходимо решить следующие задачи:

сформулировать математическую задачу оптимизации;

описать минимизацию функций и ее основные положения;

привести метод сопряженных градиентов;

проанализировать и обработать теоретические и экспериментальные данные по теме метод Флетчера-Ривса;

минимизировать функции методом Флетчера-Ривса;

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

оптимизация флетчер ривс градиент



1. Формулировка математической задачи оптимизации

В общем виде математическую задачу оптимизации можно сформулировать следующим образом:[1,2]

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных f(x) = f(x1,...,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x) > min (max), x U,

где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.

Многие задачи как практического, так и теоретического характера касаются выбора «наилучшей» конфигурации или множества параметров для достижения некоторой цели. Сложилась иерархия таких задач вместе с соответствующим набором методов их решения. Объектом иерархии является общая задача нелинейного программирования (НЛП):

(1.1)

i = 1,2,… r, (1.2)

i = r + 1, r + 2,… m, (1.3)

где f, gi - произвольные функции параметра x Rn.

От задачи максимизации, производя замену перейдем к задаче минимизации. Поэтому почти всегда будем говорить о задаче минимизации.[5]

В задачах (1)-(3), x Rn, f: Rn R1 - целевая функция, а множество точек x Rn, удовлетворяющих ограничениям (1.2), (1.3), - это допустимое множество, будем обозначать его X.

В теории НЛП изучаются:

проблемы существования решения;

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

методы вычисления оптимальных решений.

Рассмотрим некоторые из примеров задач оптимизации.

1) Оценка параметров и структуры математической модели.

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

Пусть результат измерения случайной величины у зависит от x Rp, причем

,

где у - результат измерения;

(x,) - функция, вид которой известен;

Rm - неизвестные параметры функции.

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

по .

Здесь N - количество наблюдений.

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

2) Распределение ресурсов в условиях неполной информации.

Пусть имеется m ресурсов в количествах, задаваемых компонентами bj, 1 j m, вектора b Rm. Обозначим А=[a1,…,an] матрицу размера m Ч n. Столбец aj - матрицы A характеризует затраты ресурсов на единицу интенсивности j-го способа производства. Обозначим x Rn вектор, компоненты которого xj, 1 j n, j-го способа производства, а с Rn вектор, компоненты которого сj, j = 1,…,n, доход от единицы продукции j-го способа производства. Обозначим z = (c,x) - общий доход. В принятых обозначениях задача распределения ресурсов между способами производства с целью максимизации дохода имеет вид:

(c,x) , Ax b, x 0.

Для некоторых практических задач такая детерминированная модель не адекватна реальности, так как Cj, j = 1,2,…,n случайные величины. Предположим, что с - случайный вектор с математическим ожиданием и ковариационной матрицей V. Тогда значение целевой функции z будет случайной величиной с математическим ожиданием и дисперсией (x,Vx).

Для максимизации ожидаемого значения z следует решить задачу

(c,x) Ax b, x 0.

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

(x,Vx) min, Ax b, x 0.

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

В следующей постановке требуется достигнуть лишь заданного уровня дохода при минимуме дисперсии.

(х, Vx) min, Аx b, (, х) , х 0.

Другой подход может состоять в минимизации вероятности недостижения заданного уровня дохода. =P. Пусть с = d + yf, где d, f - детерминированные векторы, а y - случайная составляющая. Тогда

Максимизация сводится к решению задачи:



Ax b, х 0.

В том случае, когда с - случайный вектор в зависимости от степени неприятия риска k, производится максимизация ожидаемого значения полезности

, Ax b, х 0.

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

2. Минимизация функций. Основные положения

Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.

f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0], и касательной к поверхности уровня функции f(x), проходящей через точку х[0]. В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С0, С1, ... , получим серию поверхностей, характеризующих ее топологию (рис. 1).

Рисунок 1 - Градиент

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f?(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентными методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.[3,4]

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х[1], лежащую в направлении антиградиента ? наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f?(х[k]) в точке х[k], получаем итерационный процесс вида

х[k+1] = x[k]-akf?(x[k]), аk > 0; k=0, 1, 2, ...

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



xi[k+1]=хi[k] - ak?f(x[k])/? xi

i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || ? ?, либо выполнение условия малости градиента

|| f?(x[k+l]) || ? ? ,

Здесь ? и ? - заданные малые величины.

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага аk.

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

f(х[k+1]) = f(x[k] - akf'(x[k])) < f(x[k]).

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

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

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

Все описываемые градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

Где - текущее приближение к решению ; - параметр, характеризующий длину шага; - направление поиска управляемых переменных x. Способ определения и на каждой итерации связано с особенностями применяемого метода. Рассмотрим простейшие градиентные методы.

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

Второй - метод наискорейшего градиентного спуска, где величина шага определяется для каждого значения k из условия:

, .

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

Более подробно рассмотрим метод Флетчера-Ривса. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера-Ривса и его модификации особенно полезным при решении задач большой размерности.

3. Метод сопряженных градиентов

Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.[5,6] Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н ? симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений.[1] Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р[0], р[1], ..., р[k-1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f'(x[k])+bk-1p[k-l], k >= 1;

p[0] = -f'(x[0]).

Величины bk-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:

(p[k], Hp[k-1])= 0.

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

итерационный процесс минимизации имеет вид

x[k+l] =x[k] +akp[k],

где р[k] - направление спуска на k-м шаге; аk - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k] + аkр[k]) = f(x[k] + ар [k]).

Для квадратичной функции

.



4. Алгоритм метода Флетчера-Ривса

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.[6,7]

1. В точке х[0] вычисляется p[0] = -f'(x[0]).

2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х[k+1].

3. Вычисляются величины f(x[k+1]) и f'(x[k+1]).

4. Если f'(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x[k+l] = x[k] +akp[k],

p[k] = -f'(x[k])+bk-1p[k-l], k >= 1;

p[0] = -f'(x[0]);

f(х[k] + akp[k]) = f(x[k] + ap[k];

.

Здесь I ? множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис.2). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Поскольку х[1] является точкой минимума функции в направлении р[0], то f'(х[1]) ортогонален вектору р[0]. Затем отыскивается вектор р [1], H-сопряженный к р [0]. Далее отыскивается минимум функции вдоль направления р[1] и т. д.

Рисунок 2 - Траектория спуска в методе сопряженных градиентов

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

Схема алгоритма метода Флетчера - Ривса представлена на рис. 3.

Рисунок 3 - Блок-схема алгоритма метода Флетчера-Ривса

5. Минимизация функции методом Флетчера-Ривса

Задача 5. Методом Флетчера-Ривса найти минимум целевой функции с учетом ограничений: .

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

Варианты:

Минимизируйте функцию .

Дано: . (1)

при ограничениях: .

Решение задачи:

Задаем начальную точку x0=(2,2).

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

.

Итерация №0.

.

Проверим критерий остановки:

x0 = (2;2)T,

|Ѓ¤f(X0)| < е,

.

Вычислим значение функции в начальной точке f(X0)=40.

Сделаем шаг вдоль направления антиградиента.

f(X1) = 3·(-16.0·t0+2.0)2+2· (-16.0·t0+2.0) · (-24.0·t0+2.0)+5· (-24.0·t0+2.0)2 > >min.

Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f'(x1)=0): 8832.0*t1-832.0 = 0.

Получим шаг: t0 = 0.0942.

Выполнение этого шага приведет в точку:

Итерация №1.

Проверим критерий остановки:

x1 = (0.49275;-0.26087)T,

|Ѓ¤f(X0)| < е,

.

Вычислим значение функции в новой точке f(X1) = 0.812.

X2 = X1 - t1d1,

d1 = Ѓ¤f(X1) + b0Ѓ¤f(X0),

Сделаем шаг вдоль направления антиградиента.

f(X2)=3·(-2.5995·t1+0.49275)2+2·(-2.5995·t1+0.49275)·(1.3762·t1-0.26087)+5·(1.3762·t1-0.26087)2 > min.

Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f'(x2)=0):

45.172*t2-8.5629 = 0.

Получим шаг: t0 = 0,1896.

Выполнение этого шага приведет в точку:

Итерация №2.

.

Проверим критерий остановки:

x2 = (6.8105e-8;-3.6056e-8)T.

|Ѓ¤f(X2)| < е,

.

Вычислим значение функции в новой точке f(X2) = 0.

Анализ решения. Найдем матрицу Гессе функции

с учетом ограничений: .

Найдем частные производные второго порядка.

4. Вычислим значение этих частных производных второго порядка в стационарных точках M(0;1).

Вычисляем значения для точки M1(0;1):

Строим матрицу Гессе:

D1 = a11 > 0, D2 = 56 > 0

В точке M1(0;1) матрица Гессе положительно определена и функция является выпуклой. Точка x1=(0;1) является точкой минимума.

6. Программная реализация метода

На рисунке 4 изображена блок-схема алгоритма поиска минимума целевой функции методом Флетчера-Ривса.



Рисунок 4 - Блок-схема алгоритма поиска минимума

На рисунке 5 представлена консольная версия компьютерной программы, написанной в среде программирования Microsoft Visual Studio 2010. Эта программа находит минимум целевой функции методом Флетчера-Ривса.

Рисунок 5 ? консольная версия компьютерной программы, написанной в среде программирования Microsoft Visual Studio 2010

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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConGrad

{

public delegate double MyFxDelegate(int nNumVars, ref double[] fX, ref double[] fParam);

class Program

{

static void Main(string[] args)

{

int nNumVars = 2;

double[] fX = new double[] { 2, 2 };

double[] fParam = new double[] { 2, 2 };

int nIter = 0;

int nMaxIter = 100;

double fEpsFx = 0.0000001;

int i;

double fBestF;

string sErrorMsg = "";

CConjugateGradient1 oOpt;

MyFxDelegate MyFx = new MyFxDelegate(Fx3);

oOpt = new CConjugateGradient1();

for (i = 0; i < nNumVars; i++)

{

Console.WriteLine("X({0}) = {1}", i + 1, fX[i]);

}

Console.WriteLine("******** FINAL RESULTS *************");

fBestF = oOpt.CalcOptim(nNumVars, ref fX, ref fParam, fEpsFx, nMaxIter, ref nIter, ref sErrorMsg, MyFx);

Console.WriteLine("Optimum at");

for (i = 0; i < nNumVars; i++)

{

Console.WriteLine("X({0}) = {1}", i + 1, fX[i]);

}

Console.WriteLine("Function value = {0}", fBestF);

Console.WriteLine();

Console.Write("Press Enter to end the program ...");

Console.ReadLine();

}

static public double Fx3(int N, ref double[] X, ref double[] fParam)

{

return 3 * X[0] * X[0] + 2 * X[0] * X[1] + 5 * X[1] * X[1];

}

public class CConjugateGradient1

{

MyFxDelegate m_MyFx;

public double MyFxEx(int nNumVars, ref double[] fX, ref double[] fParam, ref double[] fDeltaX, double fLambda)

{

int i;

double[] fXX = new double[nNumVars];

for (i = 0; i < nNumVars; i++)

{

fXX[i] = fX[i] + fLambda * fDeltaX[i];

}

return m_MyFx(nNumVars, ref fXX, ref fParam);

}

private void GetGradients(int nNumVars, ref double[] fX, ref double[] fParam, ref double[] fDeriv, ref double fDerivNorm)

{

int i;

double fXX, H, Fp, Fm;

fDerivNorm = 0;

for (i = 0; i < nNumVars; i++)

{

fXX = fX[i];

H = 0.01 * (1 + Math.Abs(fXX));

fX[i] = fXX + H;

Fp = m_MyFx(nNumVars, ref fX, ref fParam);

fX[i] = fXX - H;

Fm = m_MyFx(nNumVars, ref fX, ref fParam);

fX[i] = fXX;

fDeriv[i] = (Fp - Fm) / 2 / H;

fDerivNorm += Math.Pow(fDeriv[i], 2);

}

fDerivNorm = Math.Sqrt(fDerivNorm);

}

public bool LinSearch_DirectSearch(int nNumVars, ref double[] fX, ref double[] fParam, ref double fLambda, ref double[] fDeltaX, double InitStep, double MinStep)

{

double F1, F2;

F1 = MyFxEx(nNumVars, ref fX, ref fParam, ref fDeltaX, fLambda);

do

{

F2 = MyFxEx(nNumVars, ref fX, ref fParam, ref fDeltaX, fLambda + InitStep);

if (F2 < F1)

{

F1 = F2;

fLambda += InitStep;

}

else

{

F2 = MyFxEx(nNumVars, ref fX, ref fParam, ref fDeltaX, fLambda - InitStep);

if (F2 < F1)

{

F1 = F2;

fLambda -= InitStep;

}

else

{

// reduce search step size

InitStep /= 10;

}

}

} while (!(InitStep < MinStep));

return true;

}

public double CalcOptim(int nNumVars, ref double[] fX, ref double[] fParam, double fEpsFx, int nMaxIter, ref int nIter, ref string sErrorMsg, MyFxDelegate MyFx)

{

int i;

double[] fDeriv = new double[nNumVars];

double[] fDerivOld = new double[nNumVars];

double F, fDFNormOld, fLambda, fLastF, fDFNorm = 0;

m_MyFx = MyFx;

// calculate and function value at initial point

fLastF = MyFx(nNumVars, ref fX, ref fParam);

GetGradients(nNumVars, ref fX, ref fParam, ref fDeriv, ref fDFNorm);

fLambda = 0.1;

if (LinSearch_DirectSearch(nNumVars, ref fX, ref fParam, ref fLambda, ref fDeriv, 0.1, 0.000001))

{

for (i = 0; i < nNumVars; i++)

{

fX[i] += fLambda * fDeriv[i];

}

}

else

{

sErrorMsg = "Failed linear search";

return fLastF;

}

nIter = 1;

do

{

nIter++;

if (nIter > nMaxIter)

{

sErrorMsg = "Reached maximum iterations limit";

break;

}

fDFNormOld = fDFNorm;

for (i = 0; i < nNumVars; i++)

{

fDerivOld[i] = fDeriv[i]; // save old gradient

}

GetGradients(nNumVars, ref fX, ref fParam, ref fDeriv, ref fDFNorm);

for (i = 0; i < nNumVars; i++)

{

fDeriv[i] = Math.Pow((fDFNorm / fDFNormOld), 2) * fDerivOld[i] - fDeriv[i];

}

if (fDFNorm <= fEpsFx)

{

sErrorMsg = "Gradient norm meets convergence criteria";

break;

}

fLambda = 0;

if (LinSearch_DirectSearch(nNumVars, ref fX, ref fParam, ref fLambda, ref fDeriv, 0.1, 0.000001))

{

for (i = 0; i < nNumVars; i++)

{

fX[i] += fLambda * fDeriv[i];

}

F = MyFx(nNumVars, ref fX, ref fParam);

if (Math.Abs(F - fLastF) < fEpsFx)

{

sErrorMsg = "Successive function values meet convergence criteria";

break;

}

else

{

fLastF = F;

}

}

else

{

sErrorMsg = "Failed linear search";

break;

}

} while (true);

return fLastF;

}

}

}

}

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



Заключение

В данной работе были выполнены все поставленные задачи: освоен алгоритм решения задачи оптимизации на примере решения задачи нахождения минимума целевой функции методом Флетчера-Ривса с выполнением заданных ограничений.

В методе сопряжённых градиентов Флетчера-Ривса используется информация только о линейной части приращения в точке, как и в методах градиентного спуска. При этом метод сопряжённых градиентов позволяет решать квадратичные задачи за конечное число шагов. На многих других задачах метод сопряжённого градиента также превосходит метод градиентного спуска. Сходимость метода градиентов существенно зависит от того, насколько точно решается задача одномерной оптимизации. Возможные зацикливания метода устраняются с помощью обновлений. Тем не менее, если метод попадёт в локальный минимум функции, скорее всего, ему не удастся из него выбраться.

Если минимизируемая функция квадратичная и выпуклая, то алгоритм сопряженных градиентов приводит к оптимальному решению не более чем за n выполненных линейных поисков. Практические исследования показали, что этот метод сходится быстрее метода наискорейшего спуска, причем его эффективность возрастает на завершающих этапах поиска минимума функции. Кроме этого, следует отметить, что данный метод может быть использован при минимизации функций с разрывными производными. Поиск “не зависает на изломе”, а идет вдоль линии, соединяющей точки изломов линий уровня, которая, как правило, проходит через точку минимума.



Список использованных источников

1. Аббасов М. Э. Методы оптимизации: Учеб. пособие / М.Э. Аббасов - СПб.: Издательство “ВВМ”, 2014. - 64 с.

2. Аттетков А.В. Введение в методы оптимизации : учебное пособие для вузов / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. - М. : Финансы и статистика , 2008. - 269 с.

3. Гончаров В.А. Методы оптимизации/ В.А. Гончаров. - М.: Высшее образование, 2009. - 191с.

4. Пантелеев А.В. Методы оптимизации. Практический курс: учебное пособие/ А.В. Пантелеев, Т.А. Летова. - М: Логос, 2011. - 424 с.

5. Струченков В.И. Методы оптимизации в прикладных задачах. -М.: Солон-Прес, 2009. - 320 с.

6. Федунец Н.И. Методы оптимизации : учебное пособие для вузов / Н.И. Федунец, Ю.Г. Черников. - М. : МГГУ, 2009. - 375 с.

7. Ширяев В.И. Исследование операций и численные методы оптимизации : учебное пособие для вузов / В.И. Ширяев. - 3-е изд., стер. - М. : КомКнига, 2015. - 216 с.

Размещено на Allbest.ru

...