Условная оптимизация. Метод приведенного градиента.

 

Методику решение задач выпуклого программирования с линейными ограничениями методом приведенного градиента впервые предложил Вульф в 1963 году. Данный метод получил название метод Франка–Вульфа или метод приведенного градиента. В дальнейшем данный метод распространили на решение задач нелинейного программирования с заданными нелинейными ограничениями.

Метод приведенного градиента (в англ. литературе «reduced gradient method») ˗ это итерационный численный метод решения оптимизационных задач, который позволяет определить «условный» экстремум целевой функции (минимальное или максимальное значение)

при наличии заданных ограничений на ее переменные в виде равенств (т.е. определена область допустимых значений) 

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

Метод приведенного градиента основан на сокращении размерности задачи с помощью представления всех переменных через множество зависимых (Y) и независимых (X) переменных. Количество зависимых (Y) переменных должно соответствовать размерности системы ограничений (1…m). В результате задача поиска экстремума функции переписывается следующим образом:

Целевая функция:

Система уравнений с ограничениями:

 

В соответствии с рассматриваемым методом вектор столбец независимых (X) переменных определяется на каждом шаге итерационного расчета используя следующее выражение:

В зависимости от условия поиска (поиск максимального или минимального значения целевой функции) используется либо знак «+», либо знак «-».

Направление движение определяется градиентом функции через производные целевой функции по независимым (X) переменным. Следует отметить, что зависимые (Y) переменные целевой функции является неявной функцией от независимых (X) переменных в системе уравнений, которые определяют ограничения задачи. Запишем производную целевой функции  по независимым (X) переменным с учетом неявной зависимости:

где производные в скобках определяются с учетом явной зависимости целевой функции от зависимых (Y) и независимых (X) переменных.

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

где производные в скобках определяются с учетом явной зависимости системы уравнений с ограничениями от зависимых (Y) и независимых (X) переменных.

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

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

График линий равного уровня функции f(x) с пояснением метода приведенного градиента (simenergy.ru)

Рис.1. График линий равного уровня функции f(x) с пояснением метода приведенного градиента

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

В последнем выражении знак «+» используется если по условиям задачи необходимо найти максимум целевой функции, а знак «-» используется если по условиям задачи необходимо найти минимум целевой функции.

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

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

- траектория поиска остается в малой окрестности текущей точки поиска:

- приращение целевой функции не меняется:

- градиент целевой функции в точке локального минимума обращается в нуль:

 

Методика расчета

1 шаг: Разделяем вектор столбец неизвестных на вектор-столбец  зависимых (Y) и независимых (X) переменных. В результате задача поиска экстремума функции переписывается следующим образом:

Целевая функция:

Система уравнений с ограничениями:

 

2 шаг: Определение аналитических соотношений (в символьном виде) для вычисления приведенного градиента функции:

› Определение производной целевой функции по независимым переменным  с учетом явной зависимости функции от независимых (X) и зависимых (Y) переменных

› Определение производной системы уравнений, записанной для ограничений, по независимым переменным с учетом явной зависимости функции от независимых (X) и зависимых (Y) переменных

3 шаг: Задаем начальное приближение для вектор-столбца независимых (X) переменных

Далее выполняется итерационный процесс.

4 шаг: Определяем вектор-столбец зависимых (Y) переменных на текущем шаге расчета используя систему уравнений с ограничениями.

5 шаг: Определяем значение приведенный градиент для текущего шага расчета.

6 шаг: определяем шаг расчета из условия поиска экстремума для следующей функции  (решения задачи одномерной оптимизации).

7 шаг: определяем вектор-столбец независимых (X) переменных на следующем шаге расчета:

8 шаг: проверяем критерии останова итерационного процесса:

- траектория поиска остается в малой окрестности текущей точки поиска;

- приращение целевой функции не меняется;

- градиент целевой функции в точке локального минимума обращается в нуль.

В противном случае возвращаемся к «шагу 4» и продолжаем итерационный расчет.

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

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