Главная » Дизайн гостиной » Обзор градиентных методов в задачах математической оптимизации. Простейший градиентный метод. Нахождение экстремума функции без ограничения

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

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

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

Градиент скалярной функции F (X ) в некоторой точке направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения F (X ), проходящей через точку X k ). Вектор, противоположный градиенту  антиградиент  направлен в сторону наискорейшего убывания функции F (X ). В точке экстремума grad F (X )= 0.

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

где  k  параметр шага на k -й итерации вдоль антиградиента. Для методов восхождения (поиска максимума) нужно двигаться по градиенту.

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

Метод с постоянным параметром шага. В этом методе параметр шага постоянен на каждой итерации. Возникает вопрос: как практически выбрать величину параметра шага? Достаточно малый параметр шага может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой параметр шага может привести к проскакиванию точки минимума и к колебательному вычислительному процессу около этой точки. Указанные обстоятельства являются недостатками метода. Поскольку невозможно заранее угадать приемлемое значение параметра шага  k , то возникает необходимость использования градиентного метода с переменным параметром шага.

По мере приближения к оптимуму вектор градиента уменьшается по величине, стремясь к нулю, поэтому при  k = const длина шага постепенно уменьшается. Вблизи оптимума длина вектора градиента стремится к нулю. Длина вектора или норма в n -мерном евклидовом пространстве определяется по формуле

, где n  число переменных.

Варианты остановки процесса поиска оптимума:

C практической точки зрения удобней пользоваться 3-им критерием остановки (поскольку представляют интерес значения параметров проектирования), однако для определения близости точки экстремума нужно ориентироваться на 2-й критерий. Для остановки вычислительного процесса можно использовать несколько критериев.

Рассмотрим пример. Найти минимум целевой функции F (X ) = (x 1  2) 2 + (x 2  4) 2 . Точное решение задачи X*= (2,0;4,0). Выражения для частных производных

,
.

Выбираем шаг  k = 0,1. Осуществим поиск из начальной точки X 1 = . Решение представим в виде таблицы.

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

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

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

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

Пример. min F (x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Тогда  F (X )= [ 4x 1 ; 12x 2 2 ]. Пусть точка X k = , следовательно  F (X )= [ 8; 12], F (X k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Необходимо найти , доставляющее минимум данной функции.

Алгоритм метода наискорейшего спуска (для поиска минимума)

Начальный шаг . Пусть   константа остановки. Выбрать начальную точку X 1 , положить k = 1 и перейти к основному шагу.

Основной шаг . Если || gradF (X )||< , то закончить поиск, в противном случае определить  F (X k ) и найти  k  оптимальное решение задачи минимизации F (X k   k S k ) при  k  0. Положить X k +1 = X k   k S k , присвоить k =

k + 1 и повторить основной шаг.

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

Метод дихотомии (бисекции) Начальный шаг. Выбирают константу различимости  и конечную длину интервала неопределенности l . Величина  должна быть по возможности меньшей, однако позволяющей различать значения функции F ( ) и F ( ) . Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить k =

Основной этап состоит из конечного числа однотипных итераций.

k-я итерация.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются. Решение x * = (a k + b k )/2. В противном случае

,
.

Шаг 2. Если F ( k ) < F ( k ), положить a k +1 = a k ; b k +1 =  k . В противном случае a k +1 =  k и b k +1 = b k . Присвоить k = k + 1 и перейти к шагу 1.

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

 = 0,618034 от конца интервала.

Алгоритм метода золотого сечения

Начальный шаг. Выбрать допустимую конечную длину интервала неопределенности l > 0. Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить  1 = a 1 +(1   )(b 1  a 1 ) и  1 = a 1 +  (b 1  a 1 ) , где  = 0,618 . Вычислить F ( 1 ) и F ( 1 ) , положить k = 1 и перейти к основному этапу.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются x * = (a k + b k )/ 2. В противном случае если F ( k ) > F ( k ) , то перейти к шагу 2; если F ( k )  F ( k ) , перейти к шагу 3.

Шаг 2. Положить a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Вычислить F ( k +1 ), перейти к шагу 4.

Шаг 3. Положить a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Вычислить F ( k +1 ).

Шаг 4. Присвоить k = k + 1, перейти к шагу 1.

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

Метод сопряженных градиентов (Флетчера-Ривса). В этом методе выбор направления движения на k + 1 шаге учитывает изменение направления на k шаге. Вектор направления спуска является линейной комбинацией направления антиградиента и предыдущего направления поиска. В этом случае при минимизации овражных функций (с узкими длинными впадинами) поиск идет не перпендикулярно оврагу, а вдоль него, что позволяет быстрее прийти к минимуму. Координаты точки при поиске экстремума методом сопряженных градиентов рассчитываются по выражению X k +1 = X k   V k +1 , где V k +1 – вектор, рассчитываемый по следующему выражению:

На первой итерации обычно полагается V = 0 и выполняется поиск по антиградиенту, как в методе наискорейшего спуска. Затем направление движения отклоняется от направления антиградиента тем больше, чем значительнее менялась длина вектора градиента на последней итерации. После n шагов для коррекции работы алгоритма делают обычный шаг по антиградиенту.

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

Шаг 1. Ввести начальную точку Х 0 , точность  , размерность n .

Шаг 2. Положить k = 1.

Шаг 3. Положить вектор V k = 0.

Шаг 4. Вычислить grad F (X k ).

Шаг 5. Вычислить вектор V k +1.

Шаг 6. Выполнить одномерный поиск по вектору V k +1.

Шаг 7. Если k < n , положить k = k + 1 и перейти к шагу 4, иначе к шагу 8.

Шаг 8. Если длина вектора V меньше , окончить поиск, иначе  перейти к шагу 2.

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

Недостатки градиентных методов

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

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

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

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

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в факторном пространстве изображены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремальное значение функции отклика у ext .

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

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и определить истинное направление градиента.

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

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

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная модель оказалась адекватной, то может быть определено направление градиента:

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

где m – положительное число, определяющее величину шага в направлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав величину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осуществляем опыт в точке с координатами . Если значение функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиента, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, выходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

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

фициент , значит, область экстремума функции отклика (область оптимума) еще не достигнута. Определяется новое направление градиента и начинается движение к области оптимума.

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

В общем виде последовательность действий, необходимых для решения задачи оптимизации методом градиента, может быть представлена в виде блок-схемы (рис. 4.4).

1) исходные уровни факторов (х j 0) следует выбирать возможно ближе к точке оптимума, если есть какая-то априорная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значение интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факторов в нормированном виде

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

В основе метода лежит следующая итерационная модификация формулы

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), где

a - заданный положительный коэффициент;

Ñ f(x k) - градиент целевой функции первого порядка.

Недостатки:

необходимость выбора подходящего значения ;

медленная сходимость к точке минимума ввиду малости f(x k) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации Ñ f(x k) вдоль направления Ñ f(x k) с помощью одного из методов одномерной оптимизации x k+1 = x k - a k Ñ f(x k).

Данный метод иногда называют методом Коши.

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

Метод сопряженных направлений

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), x E n , где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением f(x *)=0. Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), x E n , где f(x) является целевой функцией n независимых переменных. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

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

Метод Ньютона

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), где

a k - параметр, выбираемый таким образом, чтобы f(x k+1) min.

2. Нахождение экстремума функции без ограничения

Дана некоторая функция f(х) на открытом интервале (а, в) изменения аргумента х. Предполагаем, что exst внутри этого интервала существует (нужно сказать, что в общем случае математически заранее это утверждать не могут; однако в технических приложениях очень часто наличие exst внутри некоторого интервала изменения интервала изменения аргумента может быть предсказано из физических соображений).

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x * max(min), если эту точку можно окружить таким интервалом (x * -ε, x * +ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x * -ε, x * +ε), выполняется неравенство:

f(x) ≤ f(x *) → для max

f(x) ≥ f(x *) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

Если ограничится для функций f(x), достаточно распространенным, но все же более узким классом гладких функций (под гладкими функциями мы будем понимать такие функции, которые непрерывны вместе со своими производными на интервале изменения аргумента), то можно воспользоваться теоремой Ферма, которая дает необходимые условия существования exst.

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная , то существования необходимоexst .

Примечание. Двухсторонняя производная характеризуется свойством иными словами, речь идет о том, что в точке "с" производная в пределе одна и та же при подходе к точке "с" слева и справа, т.е.f(x) – гладкая функция.

* В случае имеет местоmin, а при →max. Наконец, если при х=х 0 , то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи I необходимые условия exst (т.е. теорема Ферма) используется очень часто.

Если уравнение exst имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными наexst (но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Х п имеет место , однако, как известно, это не экстремум.

Заметим ещё, что:

из необходимых условий нельзя сказать, какой вид экстремума найден max или min: для определения этого нужны дополнительные исследования;

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

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exst или 2-ой производной.

1. Понятие градиентных методов. Необходимым условием существования экстремума непрерывной дифференцируемой функции являются условия вида

где – аргументы функции. Более компактно это условие можно записать в форме

(2.4.1)

где – обозначение градиента функции в заданной точке.

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

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

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

Через n и n– 1 обозначены номера шагов, а через и – векторы, соответствующие значениям аргументов целевой функции на n -м и (п– 1)-м шагах. После r-го шага можно получить

т. е. после r - шагов - целевая функция уже не будет увеличиваться (уменьшаться) при любом дальнейшем изменении ее аргументов;. Последнее означает достижение точки с координатами для которой можно написать, что

	(2.4.2)
	(2.4.3)

где – экстремальное значение целевой функции.

Для решения (2.4.1) в общем случае может быть применена следующая процедура. Запишем значение координат целевой функции в виде

где – некоторый коэффициент (скаляр), не равный нулю.

В точке экстремума так как

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

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

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

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

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


	(2.4.5)

где – малое изменение координаты

Если предположить, что точка определения градиента находится посередине

отрезка то

Выбор (2.4.5) или (2.4.6) зависит от крутизны функции на участке - Ах;; если крутизна не велика, предпочтение следует отдать (2.4.5), так как вычислений здесь меньше; в противном случае более точные результаты дает вычисление по (2.4.4). Повышение точности определения градиента возможно также за счет усреднения случайных отклонений.

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

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

Пусть поиск начинается из точки причем в окрестностях этой точки функция разложима в сходящийся ряд Тейлора. Тогда

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

Рис.2.4.2 Схема вычисления шага по методу Ньютона – Рафсона.

Подставив (2.4.7) в (2.4.8), получим:

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

Подставим новое значение в целевую функцию. Если то в точке процедура определения повторяется, в результате чего находится значение:

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

где – допустимая погрешность определения целевой функции.

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

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

В (1) и (2) соответственно

Следовательно определение на каждом шаге заключается в нахождении из уравнений (1) или (2) для каждой точки траектории движения вдоль градиента, начиная с исходной.

Лекция 6.

Градиентные методы решения задач нелинейного программирования.

Вопросы: 1. Общая характеристика методов.

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

3. Метод наискорейшего спуска.

4. Метод Франка-Фулфа.

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

1. Общая характеристика методов.

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

Градиентные методы можно разделить на два класса (группы). К первой группе относятся методы, в которых все исследуемые точки принадлежат допустимой области. К таким методам относятся: метод градиента, наискорейшего спуска, Франка-Вулфа и др. Ко второй группе относятся методы, в которых исследуемые точки могут и не принадлежать допустимой области. Общим из таких методов является метод штрафных функций. Все методы штрафных функций отличаются друг от друга способом определения «штрафа».

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

При определении решения градиентными методами итерационный процесс продолжается до тех пор, пока:

Либо grad F(x*) = 0, (точное решение);

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

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

Представим человека, стоящего на склоне оврага, которому необходимо спуститься вниз (на дно). Наиболее естественным, кажется, направление в сторону наибольшей крутизны спуска, т.е. направление (-grad F(x)). Получаемая при этом стратегия, называемая градиентным методом , представляет собой последовательность шагов, каждый из которых содержит две операции:

а) определение направления наибольшей крутизны спуска (подъема);

б) перемещение в выбранном направлении на некоторый шаг.

Правильный выбор шага имеет существенное значение. Чем шаг меньше, тем точнее результат, но больше вычислений. Различные модификации градиентного метода и состоят в использовании различных способов определения шага. Если на каком-либо шаге значение F(x) не уменьшилось, это означает, что точку минимума «проскочили», в этом случае необходимо вернуться к предыдущей точке и уменьшить шаг, например, вдвое.

Схема решения.

принадлежащей допустимой области

3. Выбор шага h.

x (k+1) = x (k)

«-» - если min.

5. Определение F(x (k +1)) и:

Если
, решение найдено;

Замечание. Если grad F(x (k)) = 0, то решение будет точным.

Пример. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
min,

x 1 +x 2 2,x 1 0, x 2 0,= 0,1.

3. Метод наискорейшего спуска.

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

Схема решения.

1. Определение х 0 = (х 1 ,x 2 ,…,x n),

принадлежащей допустимой области,

и F(x 0), k = 0.

2. Определение grad F(x 0) или –gradF(x 0).

3. Выбор шага h.

4. Определение следующей точки по формуле

x (k+1) = x (k) h grad F(x (k)), «+» - если max,

«-» - если min.

5. Определение F(x (k +1)) и:

Если
, решение найдено;

Если нет:

а) при поиске min: - если F(x (k +1))

Если F(x (k +1)) >F(x (k)) – переход к п. 2;

б) при поиске max: - еслиF(x (k +1)) >F(x (k)) – переход к п. 4;

Если F(x (k +1))

Замечания: 1. Если grad F(x (k)) = 0, то решение будет точным.

2. Преимуществом метода наискорейшего спуска является его простота и

сокращение расчетов, так как grad F(x) вычисляется не во всех точках, что

важно для задач большой размерности.

3. Недостатком является то, что шаги должны быть малыми, чтобы не

пропустить точку оптимума.

Пример. F(x) = 3x 1 – 0,2x 1 2 + x 2 - 0,2x 2 2
max,

x 1 + x 2 7, x 1 0,

x 1 + 2x 2 10, x 2 0.

4. Метод Франка-Вулфа.

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

Схема решения.

1. Определение х 0 = (х 1 ,x 2 ,…,x n), принадлежащей допустимой области, и F(x 0), k = 0.

2. Определение grad F(x (k)).

3. Строят функцию

(min – «-»;max– «+»).

4. Определение max(min)f(x) при исходных ограничениях. Пусть это будет точка z (k) .

5. Определение шага вычислений x (k +1) =x (k) + (k) (z (k) –x (k)), где (k) – шаг, коэффициент, 0 1. (k) выбирается так, чтобы значение функции F(x) было max (min) в точке х (k +1) . Для этого решают уравнение
и выбирают наименьший (наибольший) из корней, но 0 1.

6. Определение F(x (k +1)) и проверяют необходимость дальнейших вычислений:

Если
или grad F(x (k +1)) = 0, то решение найдено;

Если нет, то переход к п. 2.

Пример. F(x) = 4x 1 + 10x 2 –x 1 2 –x 2 2
max,

x 1 +x 2 4, x 1 0,

x 2 2, x 2 0.

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

Пусть необходимо найти F(x 1 ,x 2 ,…,x n)
max(min),

g i (x 1 , x 2 ,…,x n) b i , i =
, x j 0, j =.

Функции F и g i – выпуклые или вогнутые.

Идея метода штрафных функций заключается в поиске оптимального значения новой целевой функции Q(x) = F(x) + H(x), которая является суммой исходной целевой функции и некоторой функции H(x), определяемой системой ограничений и называемой штрафной функцией. Штрафные функции строят таким образом, чтобы обеспечить либо быстрое возвращение в допустимую область, либо невозможность выходы из нее. Метод штрафных функций сводит задачу на условный экстремум к решению последовательности задач на безусловный экстремум, что проще. Существует множество способов построения штрафной функции. Наиболее часто она имеет вид:

H(x) =
,