Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

оптимизация

.doc
Скачиваний:
38
Добавлен:
01.06.2015
Размер:
304.13 Кб
Скачать

Лекция 1

МЕТОДЫ ОПТИМИЗАЦИИ

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

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

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

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

Метод дихотомии несколько схож с методом бисекции, однако отличается от него критерием отбрасывания концов.

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

где — некоторое число в интервале (0; (ba)/2).

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

  • Если , то берётся отрезок , а отрезок отбрасывается.

  • Иначе берётся зеркальный относительно середины отрезок , а отбрасывается .

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

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

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

,

Из этого соотношения можно найти точку деления:

Так как нас интересует только положительное решение, то

Отсюда

Поскольку заранее неизвестно в какой последовательности ( и или и ) делить интервал неопределенности, то рассматривают внутренние точки, соответ-ствующие двум этим способам деления.

Точки и выбирают с учетом полученных значений частей отрезка. В данном случае:

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

Вторая точка выбирается на таком же расстоянии от левой границы отрезка, т.е.

И снова интервал неопределенности уменьшается до величины

Используя полученные соотношения, можно записать координаты точек деления и на отрезке на шаге:

При этом длина интервала неопределенности равна:

Процесс оптимизации заканчивается при выполнении условия

  1. Метод Фибоначчи

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

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

Чтобы сузить интервал неопределенности для произвольной строго унимодальной функции, нужно знать не менее двух ее пробных значений. В методе Фибоначчи внутри каждого текущего интервала неопределенности (ai, bi) подбираются ровно две пробные точки симметрично от середины интервала. Далее, от одной из пробных точек отбрасывается конец интервала с наихудшими значениями f(x). Получается ( а i+1 , bi+1), где в дополнение к оставшейся старой пробной точке симметрично строится новая. Отсюда для длин интервалов следует рекуррентное уравнение

(Помимо прочего выше предполагалось, что выполнено условие перекрывания Решение уравнения при условии дает

где числа Фибоначчи:

F0 = 0, F1 = 1, Fn = Fn 1+ Fn –2 .

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

В простейшем варианте метода Фибоначчи (когда предполагается, что пробные точки и пробные значения f(x) определяются абсолютно точно), чтобы сузить исходный интервал неопределенности с до надо взять число пробных точек из неравенства

4. Методы с использованием информации о производной функции

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

f (x) = 0

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

4.1. Метод Ньютона (метод касательных). Если строго унимодальная на отрезке [a, b] функция f(x) дважды непрерывно дифференцируема на этом отрезке, то точку x* минимума этой функции можно найти путем решения уравнения f (x) = 0 методом Ньютона, иногда называемым методом касательных. Выбираем x0  начальное приближение, называемое обычно начальной точкой. Линеаризуем функцию f(x) в окрестности начальной точки, приближенно заменив дугу графика этой функции касательной в точке (x0, f (x0)). Выберем в качестве следующего приближения к х* точку x1 пересечения касательной с осью абсцисс.

В общем случае сходимость метода Ньютона существенно зависит от выбора начальной точки x0. Поэтому говорят, что метод Ньютона обладает локальной сходимостью в том смысле, что надо выбрать хорошее начальное приближение, попадающее в такую окрестность точки х*, где f ''(x) > 0. Однако проверка выполнения этого условия не всегда возможна. Достаточным условием монотонной сходимости метода Ньютона будут постоянство в интервале между точками x0 и х* знака производной f ''' (x) и совпадение его со знаком f ' (x). Оказывается, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой окрестности точки х*.

4.2. Метод секущих. Метод секущих похож на метод Ньютона, но строится не касательная к графику производной, а секущая. Геометрическая интерпретация этого метода состоит в том, что в качестве очередного приближения xk+1 выбирают точку пересечения с осью абсцисс секущей к графику функции f ' (x).

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

Лабораторная работа № 5

Задания:

  1. для заданной функции определить интервал, на котором она унимодальная;

  2. методом золотого сечения найти минимум функции и сравнить его с точным значением (ε = 10-3).

Данные к заданию:

варианта

Задание

1

2

3

4

5

6

7

8

9

10

11

12

ЛИТЕРАТУРА

  1. Б.П. Демидович, И.А. Марон. Основы вычислительной математики – М.: Наука, 1970.

  2. Л.И. Турчак. Основы численных методов – М.: Наука, 1987.

  3. Г.Н. Воробьева, А.Н. Данилова. Практикум по вычислительной математике.­ – М.: Высшая школа, 1990.

  4. В.М. Заварыкин, В.Ч. Житомирский, М.П. Лапчик. Численные методы – М.: Просвещение, 1990.

  5. Е. А. Волков. Численные методы. – М.: Наука, 1982.

  6. Г.И. Марчук. Методы вычислительной математики. – М.: Наука, 1980.

  7. Р.В. Хемминг. Численные методы. – М.: Наука,1968.

  8. Н.С. Бахвалов. Численные методы. – М.: Наука, 1973.

6