Оглавление

 

    

    Введение

    Методы - это определенные приемы и способы, которые применяются для достижения поставленной цели. Каждая наука имеет  в своём распоряжении как общенаучные, так и частнонаучные (или конкретнонаучные) приемы. К общенаучным относятся: анализ, синтез, сравнение и многие другие. К сожалению, оптимизация еще не стала наукой в традиционном смысле этого слова, поэтому не имеет присущих только ей методов.

    Оптимизация как раздел математики существует достаточно давно. Оптимизация – выбор, нахождение наилучшего пути для решения конкретной задачи. При этом понятие "наилучшее" (или оптимальное) решение для каждого случая будет своим. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

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

    Задачей оптимизации в математике называется задача о нахождении экстремума вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие Rⁿ и заданные набором равенств и неравенств.

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

    В зависимости от типа экстремума различают  методы условной, безусловной, локальной  и глобальной оптимизации. Большинство  методов относятся к методам  безусловной оптимизации. Исключение составляют немногие методы, специально разработанные для поиска при наличии ограничений. Из сказанного не следует делать вывод о неприменимости методов безусловной оптимизации к большинству экстремальных задач технического проектирования, где имеют место условные экстремумы. Существуют и широко используются приемы сведения задач условной оптимизации к безусловной. Подавляющее большинство методов оптимизации ориентировано на поиск локальных экстремумов. Глобальная оптимизация несравненно сложнее, к тому же существующие методы глобальной оптимизации весьма трудоемки и не дают стопроцентной гарантии определения глобального экстремума.

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

 

    1. Методы одномерной  оптимизации

    1.1 Метод дихотомии

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

    Метод дихотомии также называется методом бисекции и методом половинного деления.

    Дихотомическое деление привлекательно своей простотой. Действительно, при дихотомии мы всегда имеем дело лишь с двумя классами, которые исчерпывают объём делимого понятия. Таким образом, дихотомическое деление всегда соразмерно; члены деления исключают друг друга, так как каждый объект делимого множества попадает только в один из классов а или не а; деление проводится по одному основанию – наличие или отсутствие некоторого признака. Обозначив делимое понятие буквой а и выделив в его объёме некоторый вид, скажем, b, можно разделить объём а на две части – b и не b.

    Дихотомическое  деление имеет недостаток: при  делении объёма понятия на два противоречащих понятия каждый раз остаётся крайне неопределённой та его часть, к которой относится частица «не». Если разделить учёных на историков и не историков, то вторая группа оказывается весьма неясной. Кроме того, если в начале дихотомического деления обычно довольно легко установить наличие противоречащего понятия, то по мере удаления от первой пары понятий найти его становится всё труднее.

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

    Пускай  задана функция f(x): [a, b] ® R, f(x) ÎC([a, b]).

    Разобьём  мысленно заданный отрезок пополам  и возьмём две симметричные относительно центра точки x₁ и x₂ так, что x₁=(a+b)/2-d и x₁=(a+b)/2-d, где - некоторое число в интервале (0; (b-a)/2).

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

    - если f(x₁) > f(x₂), то берётся отрезок [x₁, b], а отрезок [a, x₁] отбрасывается;

    - иначе берётся зеркальный относительно середины отрезок [a, x₂], а отбрасывается [x₂, b].

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

    На  каждой итерации приходится вычислять новые точки. Можно добиться того, чтобы на очередной итерации было необходимо высчитывать лишь одну новую точку, что заметно способствовало бы оптимизации процедуры. Это достигается путём зеркального деления отрезка в золотом сечении, в этом смысле метод золотого сечения можно рассматривать, как улучшение метода дихотомии с параметром: d=(b-a)(1/2-1/f).

 
    1.2 Метод деления  отрезка пополам

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

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

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

 
    1.3 Метод касательных

    Метод касательных – это итерационный численный метод нахождения корня (нуля) заданной функции.

    Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность.

    Этот  метод применяется, если уравнение имеет корень, и выполняются условия:

    1) функция принимает значения разных знаков на концах отрезка;

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

    Пусть на отрезке [a; b] отделен корень с уравнения f (x) = 0 и f – функция непрерывная на отрезке [a; b], а на интервале [a; b] существуют отличные от нуля производные f’ и f”. Рассмотрим график функции y=f(x). Пусть для определенности f‘(x) > 0 и f“(x) > 0. Проведем касательную к графику функции в точке B (b, f(b)). Ее уравнение будет иметь вид: y=f(b)+f’(b)(x-b). 

    Полагая в уравнении y=0 и учитывая что f'(x) 0, решаем его относительно x. Получим: x=b-(f(b)/f’(b))

    Нашли абсциссу x₁ точки c₁ пересечения касательной с осью ox:    x₁=(f(f(b)-f’(b)).

    Проведем  касательную к графику функции  в точке b₁(x₁;f(x₁)). Найдем абсциссу x₂ точки c₂ пересечения касательной с осью оx: x₂=x₁-(f(x₁)-f’(x₁)).

    Вообще: x_k+1=(f(x_k)-f’(x_k)).

    Таким образом, формула x_k+1=(f(x_k)-f’(x_k)) дает последовательные приближения (x_k) корня, получаемые из уравнения касательной, проведенной к графику функции в точке b_k=(x_k;f(x_k0) метод уточнения корня c [a;b] уравнения          f(x)=0 с помощью формулы x_k+1=(f(x_k)-f’(x_k)) называется методом касательной или методом Ньютона.

    Геометрический  смысл метода касательных состоит  в замене дуги y=f(x) касательной, к одной из крайних точек. Начальное приближение x₀=a или x₀=b брать таким, чтобы вся последовательность приближения x_k принадлежала интервалу [a; b] . В случае существования производных f’, f ”, сохраняющих свои знаки в интервале, за x₀ берется тот конец отрезка [a; b], для которого выполняется условие f’(x₀)*f(x₀) > 0. Для оценки приближения используется общая формула: |c-x_k-1| ³ |f(x_k+1)/m|, где m = min f’(x) на отрезке [a; b].

    На  практике проще пользоваться другим правилом : если на отрезке [a; b] выполняется условие 0 < m < |f(x)| и - заданная точность решения, то неравенство |x_k+1-x_k| ≤ e влечет выполнение неравенства |c-x_k-1| ≤ e 
В этом случае процесс последовательного приближения продолжают до тех пор, пока не выполнится неравенство: |c-x_k-1| ≤ e.

 

    

    2. Метод многомерной  оптимизации

    2.1 Постановка задачи

    В задаче многомерной оптимизации  требуется найти безусловный  минимум функции f(x) многих переменных, т.е. найти точку х^* Î Rⁿ,   что f(x^*)=min f(x),   х Î Rⁿ.

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

 
    2.2 Метод экстремального  покоординатного  поиска

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

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

    Алгоритм  экстремального покоординатного поиска имеет следующий вид:

    Шаг 1.

       x’:=x₀

       x*:=x₀ 

    Шаг 2.

       Для k=1 до n делать

       Начало.