Главная: Рефераты

Рефераты. Анализ режимов работы электрических сетей ОАО "ММК им. Ильича" и разработка адаптивной системы управления режимами электропотребления






Поэтому вопрос о выборе рациональной длины шага в градиентных методах является своего рода оптимизационной задачей. Один из способов определения оптимальной длины шага  иллюстрируется на рис. 1.3 и носит название метода скорейшего спуска [1,7].


Рисунок 1.3 - Иллюстрация метода скорейшего спуска (а) и параболическая аппроксимация целевой функции для выбора оптимального шага (б)


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


 (1.17)


где λi - значение λ, минимизирующее функцию.


. (1.18)


Значение λi может быть найдено с помощью одного из методов одномерного поиска (например, методом квадратичной интерполяции).

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

Для поиска минимума функции


 (1.19)


в направлении di из точки xi используется метод квадратичной интерполяции.

В точке , и мы выбираем длину шага λ такой, чтобы шаг "перекрыл " минимум функции φ(λ). Производная


. (1.20)


Данный оператор for(i=0;i<n;i++) g2+=g[i]*d[i]; - вычисляет выражение


. (1.21)


Оператор if (ff[2]>=ff[0] || g2>=0) проверяет условие "перекрытия" минимума, которое выполняется при выполнении либо одного, либо другого условия. Если минимум не попал в отрезок (0,λ), то λ удваивается, и это повторяется столько раз, сколько необходимо для выполнения условия "перекрытия".

Удостоверившись, что отрезок (0,λ) содержит минимум, в качестве третьей точки возьмем точку λ/ 2. Минимальную точку сглаживающего квадратичного полинома находим в соответствии с соотношением


 (1.22)


что отражено следующими операторами

l[3]=h*(ff[1]-.75*ff[0]-.25*ff[2]);

l[3]/=2*ff[1]-ff[0]-ff[2];

Оператор for(i=0;i<n;i++)

{ x[i]=y[i]+l[0]*d[i]; y[i]=x[i]; }

производит присваивание xi+1=xi, и если |g(xi+1)| достаточно мало, то процесс заканчивается. В процессе поиска предполагается сходимость к экстремуму, поэтому для эффективности процедуры разумно уменьшить длину шага. При этом деление шага пополам выбрано произвольно.

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


1.5.3 Метод проектирования градиента

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

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

Для упрощения алгоритма допустим, что имеется одно ограничение в виде линейного неравенства


 (1.23)

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

Начало вычислительной процедуры такое же, как и в предыдущих методах:

в области  принимается исходное (нулевое) приближение х10, х20;

вычисляется значение целевой функции в этой точке Z0;

в соответствии с выражением (1.15) в этой точке вычисляется градиент целевой функции grad Z;

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


Рисунок 1.4 - Иллюстрация метода проектирования градиента


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

Необходимо проверить, принадлежит ли точка с координатами х11, х21 области  допустимых значений переменных. Для этого проверяется неравенство (1.23), в которое подставляются координаты х11, х21:


 (1.23)


Если это неравенство выполняется, вычислительный процесс продолжается.

Из точки с координатами х11, х21 выполняется следующий шаг. В результате этого шага имеем второе приближение - точку с координатами х12, х22. значение целевой функции в этой точке Z2.

Пусть для этой точки неравенство  не выполняется. Следовательно, точка с координатами х12, х22 вышла из области  и необходимо выполнить возврат в эту область.

Возврат в область  выполняется следующим образом. Из точки с координатами х12, х22 опускается перпендикуляр на прямую  т.е. конец вектора (х11, х21; х12, х22) проектируется на эту прямую. В результате получается новое приближение - точка с координатами х13, х23, которая принадлежит области . В этой точке вычисляется значение целевой функции Z3.

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


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


Рассмотрим задачу поиска локального минимума критерия оптимальности W в области, ограниченной системой неравенств (3.16)-(3.17). Введение обобщенного критерия оптимальности по методу штрафных функций [3,5] производится с помощью непрерывной функции


. (1.24)


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


T=W+RQ(x),


где R - некоторое положительное число, называемое коэффициентом штрафа.

Рассматривается некоторая неограниченная, монотонно возрастающая последовательность {Rk}, k=1,2,... положительных чисел. Для первого элемента этой последовательности с помощью метода покоординатного спуска отыскивается локальный минимум функции T. Пусть этот минимум достигается при значениях (b*,R1).

Вектор (b*,R1) используется как начальное приближение для решения задачи поиска минимума функции T где R2>R1 и т.д. Таким образом, решается последовательность задач минимизации функций T(b*,Rk), k=1,2 ..., причем результат предыдущей оптимизации используется в качестве начального приближения для поиска последующей.


Рисунок 1.5 - Блок-схема метода штрафных функций


1.7 Методы полиномиальной аппроксимации


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

Рассмотрим следующие вопросы:

квадратичная аппроксимация <#"1.files/image051.gif">


1.7.1.1Метод Пауэлла

Если известны значения функции f(x) в трех разных точках α, β, γ равные соответственно fα, fβ, fγ, то функция f(x) может быть аппроксимирована квадратичной функцией


ö(x)=Ax2+Bx+C, (1.26)


где А, В и С определяются из уравнений


Aá2+Bá+C=fá,

Aâ2+Bâ+C=fâ,

Aã2+Bã+C=fã. (1.27)


После преобразований этих уравнений получаем


A=[(ã-â)fá+(á-ã)fâ+(â-á)fã] / D,

B=[(â2-ã2)fá+(ã2-á2)fâ+(á2-â2)fã] / D,

C=[âã(ã-â)fá+ãá(á-ã)fâ+áâ(â-ã)fã] / D, (1.28)


где D=(á-â)(â-ã)(ã-á)

Ясно, что φ(x) будет иметь минимум в точке


x=-B/2A,


если А>0. Следовательно, можно аппроксимировать точку минимума функции f(x) значением


 (1.29)


Этот метод может непосредственно применяться к функциям одной переменной. Он может быть очень полезен для выполнения линейного поиска в процедурах, описанных в теме №3. В этих процедурах требуется найти минимум функции f(x) в точках прямой x0+λd, где x0- заданная точка, а d определяет заданное направление. Значение функции f(x0+λd) на этой прямой является значениями функции одной переменной λ:


φλ = f(x0+λd). (1.30)


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

Шаг 1. x2 = x1 + D x.

Шаг 2. Вычислить W(x1) и W(x2).

Шаг 3.

если W(x1) > W(x2), то x3 = x1 + 2 D x;

если W(x1)< W(x2), то x3 = x1 - D x;

W(x1) > W(x2),

Шаг 4. Вычислить W(x3) и найти

Wmin = min{ W(x1),W(x2), W(x3)},

Xmin = xi, соответствующая Wmin.

Шаг 5. По x1, x2, x3 вычислить x*, используя формулу для оценивания с помощью квадратической аппроксимации.

Шаг 6. Проверка окончания

если | Wmin - W(x*)| < W, то закончить поиск. В противном случае к шагу 7;

если | Xmin - x*| < x, то закончить поиск. В противном случае к шагу 7.

Шаг 7. Выбрать Xmin или x* и две точки по обе стороны от нее. Обозначить в естественном порядке и перейти к шагу 4.

Заметим, что если точка Е задана слишком малой, то á, â, ã, а также fá, fâ, fã будут очень близко друг к другу и значение d (1.29) может стать вообще недостижимыми. Чтобы преодолеть эту трудность, перепишем (1.29) для второй и последней интерполяции:


 (1.31)


1.7.2 Кубическая интерполяция

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

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

Рассмотрим задачу минимизации функции f(x) на прямой x0 + hd , то есть минимизацию функции


 (1.32)


Предположим, что известные следующие значения:


 (1.33)


Эту информацию можно использовать для построения кубического полинома a+bh+ch2+dh3, который будет аппроксимировать функцию φ(h) Если p=0 , то уравнения, которые определяют a, b, c, d имеют вид :


 (1.34)


Следовательно, если r является точкой минимума кубического полинома,


 (1.35)


где


Одно из значений этого выражения является минимумом. Друга производная равна 2c +6dh.

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



другая производная будет


 (1.36)


 (1.37)


Выбор точки q зависит от нас. Если Gp >0 , то надо выбрать значение q положительным, то есть сделать шаг в направлении уменьшения функции φ(h) , в другом случае значения q надо выбирать отрицательным. Значение должно быть таким, чтобы интервал (0, ) включал в себя минимум. Это будет верным, если φq > φ p или Gp >0.

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

Давидон, Флетчер и Пауэлл предложили выбирать q следующим путем:


 (1.38)


где φm - оценка самого малого значения истинного минимума φ(h),

h- константа, значение которой обычно берут 2 или 1.


1.7.3 Квадратичные функции

Квадратичная функция [7,8]


 (1.39)


где a - константа;

b - постоянный вектор;

G - положительно определенная симметричная матрица - имеет минимум в точке x* , где x* определяется следующим путем:


 (1.40)


откуда



Любую функцию можно аппроксимировать в окрестности точки x0 функцией


 (1.41)

где G(x0) - матрица Гессе, вычисленная в точке x0.

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


 (1.42)


откуда



или


 (1.43)


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


 (1.44)


или


 (1.45)


где λи - длина шага, определяется одномерным поиском в направлении G-1(xи)g(xи).


1.8 Метод Нелдера-Мида


Метод Нелдера-Мида (поиск по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта [7,8]. Множество (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n+1) вершинах симплекса и перемещении в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если n<=6.

В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.

Шаг 1. Найдем значения функции в вершинах симплекса:


f1=f( x1), f2=f(x2) ... fn+1=f(xn+1) (1.46)


Шаг 2. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg , наименьшее значение функции fl и соответствующие им точки xh, xg и xl.

Шаг 3. Найдем центр тяжести всех точек, за исключением точки xh. Пусть центром тяжести будет


 (1.47)


и вычислим f(x0)=f0.

Шаг 4. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки x0, получим точку xr и найдем f(xr) = fr.

Операция отражения иллюстрируется рис. 1.6.


Рисунок 1.6 - Операция отражения


Если α>0 - коэффициент отражения, то положение точки xr определяется следующим образом:


xr-x0=α (x0-xh), т.е.


xr=(1+α)x0 -αxh. (1.48)


Замечание.


α= |xr-x0| / |x0 -xh|.


Шаг 5. Сравним значения функций fr и fl.

Если fr<fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe=f(xe). Рисунок 1.7. иллюстрирует операцию растяжения симплекса. Коэффициент растяжения γ1 можно найти из следующих соотношений: xe-x0=γ (xr-x0), т.е.


xe=γxr+ (1-γ)x0. (1.49)


Рисунок 1.7 - Операция растяжения


Замечание


γ=|xe-x0| / |xr-x0|


Если fe<fl, то заменяем точку xh на точку xe и проверяем (n+1)-ую точку симплекса на сходимость к минимуму (см. шаг 8). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг 2.

Если fe=fl , то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг 5, 1) проверить сходимость и, если она достигнута, вернуться на шаг 2.

Если fr>fl, но fr <=fgто xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг 2, т.е. выполняем пункт 1,б, описанный выше.

Если fr>fl и fr>fgто перейдем на шаг 6.

Шаг 6. Сравним значения функций fr и fh.

Если fr>f h, то переходим непосредственно к шагу сжатия 6,2.

Если fr<fh, то заменяем точку xh на точку xr и значение функции fh на значение функции fr. Запоминаем значение fr>f g из шага 5,2, приведенного выше. Затем переходим на шаг 6,2.

В этом случае fr>f h, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Пытаемся исправить это, найдя точку xc (а затем fс) с помощью шага сжатия, показанного на рис. 1.8.

Если fr>f h, то сразу переходим к шагу сжатия и находим точку xc из соотношения


xc-x0=β(xh-x0), (1.50)


где β(0<b<1)- коэффициент сжатия. Тогда


xc=βxh+(1-β)x0. (1.51)


Если fr<f h, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения


xc-x0=β(xr-x0), т.е.


xc=βxr+(1-β)x0. (1.52)


Шаг 7. Сравниваем значения функций fc и fh.

Если fc<f h, то заменяем точку xh на точку xc, и если сходимость не достигнута ,то возвращаемся на шаг 2.

Если fc>f h, то очевидно, что все наши попытки найти значение меньшее fh закончились неудачей, поэтому мы переходим на шаг 8.

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


Рисунок 1.8 - Шаг сжатия для fr>fh


Рисунок 1.9 - Шаг сжатия для fr<fh


Таким образом, точка xi заменяется на точку


,


т.е. заменяем точку xi точкой .

Затем вычисляем fi для i=1,2,...,(n+1), проверяем сходимость и, если она достигнута, возвращаемся на шаг 2.

Шаг 9. Проверка сходимости основана на том, чтобы стандартное отклонение (n+1) -го значения функции было меньше некоторого заданного малого значения. В этом случае вычисляется


, (1.53)


где .

Если σ<ε, то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции xl. Исходя из этого, такой критерий сходимости является разумным, хотя Бокс, Дэвис и Свенн предлагают то, что они считают более "безопасной" проверкой.

Коэффициенты αβγ в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать α=1, β=0.5 и γ=2. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.

Страницы: 1, 2, 3, 4, 5, 6



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.