Методы оптимизации 1-ого порядка

Многомерная градиентная оптимизация

Величина шага в рекуррентном соотношении: для переменной i на j +1 итерации вычисляется с использованием градиента целевой функции R(x), т.е. . При этом шаг может определяться с использованием градиента в одной (текущей) или в двух (текущей и предыдущей) точках. На­правление градиента, как известно, показывает направления наискорейшего возрас­тания функции, а его модуль — скорость это­го возрастания. Поисковые методы оптимизации содержат субъ­ективно задаваемые па­раметры, которые су­щественно влияют на эффективность поиска, вследствие чего один и тот же метод может дать совершенно различные траектории поиска. Среди этих методов выделим метод сопряжённых градиентов и метод Ньютона.

Из курса математики известно, что направление наибольшего возрастания функции характеризуется ее градиентом. Если критерий оптимизации задан уравнением: f(х1,…xn), то его градиент в некоторой точке О (из области определения функции ) определяется вектором:

(6)

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

В этом случае частные производные в точке O находят приближенными методами.

(7)

Δ. -бесконечно малое приращение (1 - 5% от значения i - ой переменной).

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

Метод градиента. Опишем принцип использования метода градиента на примере функции двух переменных f= f(Х1 , Х2 ). Этот принцип без изменения переносится на любое число переменных.

Рис.6.

Пусть в начальный момент значения X1 и Х2 соответствуют точке Мо (см. рис.6). Цикл расчета начинается с серии пробных шагов. Сначала величине X1 дается небольшое приращение > 0, причем в это время Х2 неизменно. Затем определяется полу

ченное при этом приращение Δf, величины f, которое можно считать пропорциональным значению величины частной производной. Далее производится приращение величины X2. В это время X1 - const. Получаемое при этом приращение величины f является мерой другой частной производной. После нахождения составляющих градиента делается рабочие шаги в направлении вектора градиента, если стоит задача определения максимума и в направлении противоположном, если решается задача поиска минимума.

, (8)

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

.

Таким образом определяются новые значения X1 и Х2 , соответствующие точке М1. После каждого рабочего шага оценивается приращение Δf величины f. Если Δf >0 при поиске максимума или Δf<0 при поиске минимума, то движение происходит в правильном направлении, иначе необходимо уменьшить величину шага. В качестве примера рассмотрим задачу поиска минимума функции: f(X)=X1**2+25*X2**2.

Примем величину шага h =1, Δ X1 = Δ X2 = 0.05. В качестве исходной точки поиска возьмём точкуX0 =(2,2). Поиск минимума осуществляем следующими этапами (см. таблицу1):

Таблица1.

Шаг	X1	Х2				S1k	S2k	f
			4.050	101.25	101.250	-0.040	-0.999	104.00
	1.960	1.001	3.970	51.30	51.453	-0.077	-0.997	28.89
	1.883	0.004	3.816	1.45	4.082	-0.035	-0.355	3.55
	0.948	-0.351	1.94	-16.30	16.416	-0.119	0.993	3.98
Величина Δf>0,поэтому уменьшаем шаг вдвое.
0.5	1.416	-0.174	2.882	-7.45	7.988	-.0180	0.466	2.76
0.5	1.236	0.292	2.552	15.85	16.049	-0.079	0.494	3.66
Величина Δf>0,поэтому уменьшаем шаг вдвое.
0.25	1.326	0.059	2.702	4.20	4.994	-0.135	-0.21	1.84

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

а) б)

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

а) Поиск максимума с выбором оптимального шага.

б) Сравнение с методом градиента.

Величину шага h можно определить из условия минимума f(Xk+hk*Sk):

(9)

Пример. В качестве примера рассмотрим задачу поиска минимума функции:

f(X)=X1**2+25*X2**2.

Таблица 2.

Этап	Шаг hk	X1	Х2			f
				4.050	101.25	104.00
	2.003	1.92	-0.003	3.84	-0.15	3.19
	1.85	0.07	0.07	0.14	3.5	0.13
	0.07	0.07	-0.000			0.0049

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

(или менее), если шаги предпринимаются в так называемых сопряжённых направлениях. Вектор S1 называют сопряжённым вектору S0 ,если

, (9)

где

Пример. Пусть f(X)=X12+X22-4 , X0=(4,4). Пусть

Обозначим координаты вектора S1(S11,S12). Тогда

или

Отсюда S11+√3*S12=0. Добавим условие, чтобы длина вектора была равна 1:. Отсюда находим: . Вычислим градиент функции в исходной точке - . По формуле (9) находим:

, , h=-5.86

Тогда

Метод вторых производных. Метод Ньютона.В соответствие с этим методом:

, (10)

матрица обратная матрице Гессе. Матрица Гессе

. (11)

Пример. Найти минимум функции Розенброка:

. В качестве исходной точки поиска примем X=[-0.5 0.5}T. f(X)=8.5

f(x)=2.33

4. Постановка задачи многокритериальной оптимизации

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

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

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

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

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

(1)

который принимает значения в -мерном арифметическом пространстве .

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

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

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

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

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

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

- минимум целевых функций ,

- максимум целевых функций

по поисковым переменным при наличии ограничений:

- на поисковые переменные:

, l=1,L; L-число поисковых переменных.

- на поисковые переменные в виде функциональных неравенств: , j=1,J; J - число функциональных неравенств.

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

, i=1,I. I- число функциональных равенств.

Для сравнения критериев ,имеющих разный физический смысл (и естественно разные размерности),проведем нормализацию критериев в следующем виде:

для целевых функций ,

, i=1,……..m,

для целевых функций

i=m+1,…,M.

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

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

Найти минимум целевых функций

по поисковым переменным при наличии ограничений:

- на поисковые переменные:

, l=1,L; L-число поисковых переменных.

- на поисковые переменные в виде функциональных неравенств: , j=1,J; J- число функциональных неравенств.

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

, i=1,I. I - число функциональных равенств.

(Вильфредо Парето (1848-1923) – итальянский социолог и экономист)