Этот метод может непосредственно применяться к унимодальным функциям одной переменной. Он может быть очень полезным для поиска частного оптимума по отдельным направлениям при решении задач многомерной оптимизации.
В предыдущих двух методах была сделана попытка найти малый интервал, в котором находятся оптимум функции I(x). В рассматриваемом методе применяется иной подход. Он заключается в построении аппроксимирующей модели оптимизируемой функции I(x). Функция I(y) может быть аппроксимирована полиномом второго порядка
(1.5)
по крайней мере, в небольшой области значений, в том числе в области оптимума. При этом положение экстремума I(x) определяется положением экстремума полинома (1.5), поскольку последний вычислить проще.
Экстремум функции Ia(x), как известно, расположен в точке
. (1.6)
Положим, что окрестность некоторой исходной точки x=x1 на области определения I(x) аппроксимирована полиномом (1.5). Задача поиска заключается в определении смещения
, (1.7)
которое приводит из исходного состояния x=x1 в экстремальное x=x*. Если I(x) строго квадратичная функция, то смещение Dx после первого шага сразу приведет к x*. В противном случае достижение x*требует выполнения итерационной процедуры.
Для определения смещения Dx нужно определить коэффициенты параболы (4.5). Эта задача легко решается, если известны значения I(x) в трех точках. Пусть вычисление I(x) производилось в районе исходного состояния x=x1 в точках x1, x=x1 -h, x2=x1+h и при этом получено три значения этой функции:
, (1.8)
где h – полуинтервал интерполяции, малая постоянная положительная величина.
Подставляя эти значения в уравнение (1.5), получаем систему из трех линейных уравнений с тремя неизвестными a, b и с:
. (1.9)
Для того, чтобы эта система имела решение, необходимо, чтобы ее определитель не был равен нулю, то есть
. (1.10)
Раскрывая этот определитель, находим
,
что всегда выполняется, поскольку h¹0.
Разрешая систему уравнений (1.9), получаем интересующие нас значения параметров a, b, c и, подставляя их в формулу (1.6), находим положение экстремума параболы
. (1.11)
Величина рабочего смещения Dx равна
. (1.12)
Зная коэффициенты a, b, с можно определить и экстремальное значение функции (1.5) по формуле
, (1.13)
которое является оценкой экстремума критерия I(x).
После выполнения рабочего шага Dx следует проверить, действительно ли найден экстремум. Для этого достаточно вычислить значение функции цели I(x) в предполагаемом экстремуме 
и сопоставить его с оценкой (1.13). Если эти величины отличаются не более чем на e, то есть
, (1.11)
где e – заданная погрешность определения экстремума, то задачу отыскания экстремума можно считать выполненной. При этом x*=x1+Δx.
Если же условие (1.11) не соблюдается, то это означает, что исходное предположение о квадратичности целевой функции не выполняется и следует продолжать процесс поиска, то есть выполнить следующий цикл, но построение модели производить в окрестности точки x*=x1. Эта процедура повторяется до тех пор, пока не выполнится условие (1.11).
Вполне очевидно, что критерием окончания процесса поиска экстремума может служить выполнение условия
. (1.15)
Таким образом, с помощью итерационной процедуры значение x * уточняется до получения его с заданной погрешностью e.
1 Методы одномерной оптимизации на основе преобразования задач
Многие инженерные задачи связаны с оптимизацией при наличии различного вида ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. Однако, несмотря на это, процесс оптимизации становится более сложным, поскольку известные критерии оптимальности решения задачи безусловной оптимизации нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Часто оптимум достигается в точке, не являющейся стационарной точкой функции 
. Указанные трудности наталкивают на мысль использовать безусловную оптимизацию вспомогательных функций, составленных с учётом ограничений, для отыскания точки условного оптимума.
Идея преобразования задачи с ограничениями в последовательность задач без ограничений представляется эффективной в связи с наличием надёжных методов безусловной оптимизации. Это позволяет отыскать условный оптимум с приемлемой точностью путём решения относительно небольшого числа не слишком сложных задач.
Ниже рассматривается задача нелинейного программирования следующего вида:
, 
, (2.1)
, 
, 
; (2.2)
, 
. (2.3)
Начнём рассмотрение с краткого обсуждения метода классического анализа поиска экстремума функции многих переменных без ограничений. Этот метод часто является неотъемлемой частью методов решения преобразованной задачи оптимизации.
экстемум интерполяция итерация
Задачей оптимизации в математике, информатике и исследовании операций называется задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и / или нелинейных равенств и / или неравенств.
Методы квадратичной интерполяции и золотого сечения принадлежат к методам одномерной минимизации.
Целью этих методов является нахождение безусловного минимума функцииодной переменной, т.е. такую точку, что при
Метод квадратичной интерполяции основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации.
Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации. Интервал неопределенности делится на две равные части так, что отношение длины большого отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего отрезка.
Целью курсовой работы является сравнительный анализ методов квадратичной интерполяции и дихотомии.
Требуется найти безусловный минимум функцииодной переменной, т.е. такую точку, что при
Стратегия поиска
Метод квадратичной интерполяции (метод Пауэлла) относиться к последовательным стратегиям. Задается начальная точка и с помощью пробного шага находятся три точки так, чтобы они были как можно ближе к искомой точке минимума. В полученных точках вычисляются значения функции. Затем строится интерполяционный полином второй степени, проходящий через имеющиеся три точки. В качестве приближения точки минимума берется точка минимума полинома. Процесс поиска заканчивается, когда полученная точка отличается от наилучшей из трех опорных точек не более чем на заданную величину.
Задать начальную точку величину шага ?x>0, и — малые положительные числа, характеризующие точность.
а) если , положить = . (рис 1, а).
б) если , положить = . (рис 1, б).
Вычислить точку минимума интерполяционного полинома, построенного по трем точкам:
и величину функции (рис 1).
Если знаменатель в формуле для на некоторой итерации обращается в нуль, то результатом интерполяции является прямая. В этом случае рекомендуется обозначить и перейти к шагу 2.
Проверить выполнение условия окончания:
а) если оба условия выполнены, процедура закончена и
б) если хотя бы одно из условий не выполнено и,
выбрать наилучшую точку и две точки по обе стороны
от нее. Обозначить эти точки в естественном порядке и перейти к
в) если хотя бы одно из условий не выполнено и , то
Интерполяция функции Y(x) одной переменной х, заданной (n+1) узлами y(x), где i=0,1,2,…n, заключается в нахождении значений Y по значениям х, находящихся в отрезке [X0. Xn). При интерполяции функция f(x) заменяется интерполяционным полиномом p(x),значения которого p(x) в узлах точно совпадают с y(x). Значение n задает степень полинома p(x). Существует ряд специальных видов полинома p(x).
Экстраполяция — получение значений Y(x) при х, не принадлежащих отрезку [X0. Xn]. Для гладких y(x) экстраполяция целесообразна при х, выходящих за указанные пределы не более чем на h/2.
Метод заключается в замене f(x) в промежутке X1+(-)h, где X1 — начальное приближение, квадратичной параболой, экстремум которой вычисляется аналитически. После приближенного нахождения экстремума Xm можно задать X1=Xm и повторить поиск. Таким образом, с помощью итерационной процедуры значение Xm уточняется до получения его с заданной погрешностью e.
Этот метод обеспечивает поиск как максимумов, так и минимумов f(x), в том числе для случая f(x)=0, причем точка Xm может лежать в интервале X1+(-)h (интерполяция) и быть вне его (экстраполяция).
1. Задаем начальное приближение X1 для Xm и вычисляем два смежных значения аргумента F(x): x0=x1-h и x2=x1+h, где h — полуинтервал интерполяции — экстраполяции.
2. Вычисляем три значения F(x): F(x)=F0, F(x1)=F1, F(x2)=F2.
3. Находим коэффициенты параболы Y(Х)=X^2+BX+C,
Проходящей через выбранные три узла интерполяции — экстраполяции
F(x), и по ним вычисляем аналитически положение экстремума
4. Проверяем выполнение условия ABS(Xm-X1) 2013-07-07
