Материал: Алгоритмы пособие

2.6.Алгоритмы методов одномерной оптимизации

2.6.1.Метод дихотомии

Схема алгоритм метода дихотомии, представленная на рис. 2.6-1, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.

Рис.2.6-1. Алгоритм метода дихотомии

В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b][3].На отрезке [a0;b0], где a0=a, аb0 = b, выбираются две точки симметричные относительно середины отрезка:

унимодальности функции можно провести сокращение отрезка неопределенности по следующему правилу:

Еслиf( 1) f( 1), то x* [a0; 1] ; Если f( 1) >f( 1), то x* [ 1;b0].

36

Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.

2.6.2. Метод золотого сечения

Схема алгоритма метода золотого сечения, представленная на рис. 2.6-2, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.

Рис.2.6-2. Алгоритм метода золотого сечения

В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b] [3].В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения:

,

где k1=0.382, а k2=0.618.

37

Сравнение значений функции в точках х1 и х2 позволяет, в силу унимодальности функции f(x), отбросить ту часть отрезка, где заведомо нет точки минимума. Известно, что и точка х1и точка х2дваждыосуществляет золотое сечение на отрезке[a;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.

2.6.3. Метод средней точки

Схема алгоритма метода средней точки, представленная на рис. 2.6-3, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.

Рис. 2.6-3. Алгоритм метода средней точки Алгоритм метода средней точки [2] основан на сокращении длины

текущего отрезка неопределенности [a;b], путем отбрасывания той половины отрезка, которая не содержит точки минимума. В основу метода положено основное свойство унимодальности функции, то есть, для того чтобы на отрезке [a;b] существовал минимум, необходимо, чтобы первая производная на нем была неубывающей. Выбрав середину текущего отрезка c=(ai+bi)/2),

функции, точка минимума не может лежать левее точки с, переопределяется

правее точки с и переопределяется правая граница отрезка (bi+1=c). В случае

Сокращение отрезка проводятся до тех пор, пока не выполнится неравенство n=|bn-an|≤ε.

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

2.7.Алгоритмы методов многомерной оптимизации

Итерационные методы, применяемые для решения задач минимизации функции нескольких переменных, относятся к классу методов спуска[3]. В них каждая итерация(k) приводит к уменьшению значения целевой функции:

Q(xk+1,yk+1)<Q(xk,yk), для всех k 0.

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

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

Схема алгоритма метода градиентного спуска, представленная на рис. 2.7-1, требует дополнения следующих процедур-функций:

Q(x,y) – целевая функции;

g1(x,y) – частная производная по х;

g2(x,y)– частная производная по y.

39