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

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

1. Основные понятия

1.1 Определения.

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых параметров, определяющих данную задачу. При решении инженерных задач их принято называть проектными параметрами, а в экономических задачах их обычно называют параметрами плана. В качестве проектных параметров могут быть, в частности, значения линейных размеров объекта, массы, температуры и т.п. число n проектных параметров x1,x2,…,xn характеризует размерность ( и степень сложности) задачи оптимизации.

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

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

U=F(x1, x2,…,xn). (1.1)

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

В случае одного проектного параметра целевая функция (1.1) является функцией одной переменной, и се график - некоторая кривая на плоскости. При целевая функция является функцией двух переменных, и ее график поверхность в трехмерном пространстве.

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

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

1.2 Задачи оптимизации.

Можно выделить два типа задач оптимизации безусловные и условные. Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (1.1) при действительных переменных и определении соответствующих значений аргументов на некотором множестве σ n-мерного пространства. Обычно рассматриваются задачи минимизации; к ним легко сводятся и задачи на поиск максимума путем замены знака целевой функции на противоположный.

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

Ограничения-равенства выражают зависимость между, проектными параметрами, которая должна учитываться при нахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т. п.

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

www.studsell.com

Доклад - Методы одномерой оптимизации

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

Постановка: требуется оптимизировать х (формальная постановка)

- функция одной переменной

- целевая функция.

Решение: найти х, при котором принимает оптимальное значение.

2 варианта:

Рассмотрим случай минимизации

2 способа:

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

Пусть функция определена в некоторой области S (), в случае одномерной оптимизацииS – интервал :

точка называется глобальным минимумом, если для
точка называется строгим глобальным минимумом, если для
точка называется локальным минимумом, если для
точка называется строгим локальным минимумом, если для

Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно.

Аналитический способ нахождения локального минимума.

- дифференцируема

- необходимое условие точки локального минимума.

Численные методы.

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

аb

Если из того что следует, что, то функция называется монотонно возрастающей. Если из того чтоследует, что, то функция называется монотонно убывающей.

Методы одномерного поиска.

Разобьем и вычислим значение функции в каждой точке.

искомый минимум

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

Интервал неопределенности – интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение – двумя точками на 3 равных отрезка.

- после выполнения n шагов сокращение исходного интервала

- точность с которой надо найти решение задачи.

N=2n, где n – число шагов, N – число вычислений (мера эффективности данного решения).

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

Точки должны быть расположены на равном расстоянии.

а b

; ;;

; - золотое сечение.

- величина сокращения на каждом шаге

число итераций растет как логарифм функции.

Одномерная оптимизация с использованием производных.

. Пусть целевая функция дифференцируема .


точка локального минимума	точка локального максимума	точка перегиба

Методы для нахождения корня уравнения функции 1-ой производной от исходной.

Нахождение локального минимума или максимума сводится к нахождению корней первой производной от данной

f’(x)=0

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

Решение уравнения вида разбивается на два этапа:

отделение корней, т.е. отыскание достаточно малых областей, в каждой из которых заключен один и только один корень уравнения;
вычисление выделенного корня с заданной точностью.

На первом этапе может помочь построение приближенного графика функции f(x) или, если функция достаточно сложная, то можно попытаться представить уравнение в виде и построить два графикаи, тогда корнями уравнения будут абсциссы точек пересечения этих кривых.

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

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

Метод половинного деления

Суть метода половинного деления (дихотомии) заключается в следующем.

Отрезок делится пополам и за первое приближение корня принимается точка c, которая является серединой отрезка, т.е.. Если, это корень уравнения. Если нет, то далее выбирается тот из отрезков [a, c] или [c, b], на концах которого функция имеет разные знаки. Полученный отрезок снова делится пополам, и проводятся те же рассуждения. Деление продолжается до тех пор, пока длина отрезка не станет меньше заданного .

Графическая интерпретация метода представлена на рис. 1.1. Метод половинного деления реализуется в виде следующего алгоритма:

Найти точку c = (a + b)/2.

Если f(a)f(c) <0, то корень лежит на интервале [a, c], если нет, то корень лежит на интервале [c, b].

Если величина интервала не превышает некоторое достаточно малое число е, то найден корень с точностью е, иначе возврат к п.1.

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

Блок-схема алгоритм решения уравнения методом деления пополам.

Метод Ньютона (метод касательной):

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

В качестве начального приближения корня уравнения примем абсциссу точки пересечения этой касательной с осью Ох. Тогда, полагая в уравнении касательной , можно найти абсциссу точки пересечения:

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

Алгоритм, реализующий метод касательных, можно представить так:

Определяется начальное приближение: если , то начальное приближение, иначе.

Уточняется значение корня по формуле .

Если абсолютное значение функции в найденной точке не превышает некоторое достаточно малое число , то найден корень с точностью, иначе возврат к п.2.

Алгоритм решения уравнения методом Ньютона

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРЗОВАНИЯ

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

РЕФЕРАТ

По теме:

«Методы одномерной оптимизации »

Выполнил: ********************

Руководитель: *************

г. Уфа. 2008 г.

studfiles.net

Методы оптимизации — реферат

Потенциал первого столбца v1 = u2 + c21 = 0 + 4 = 4;

второго: v2 = u2 + c22 = 0 + 7 = 7;

третьего: v3 = u2 + c23 = 0 + 13 = 13;

пятого: v5 = u2 + c25 = 0 + 2 = 2.

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

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и базисной клетке А1В3 по формуле

, (3.5)

где u1 = v3 – c31 = 13 – 8 = 5.

Для строки 3 потенциал будет равен:

u3 = v5 – c35 = 2 – 1 = 1.

Также рассчитываем потенциалы для всех строк и столбцов (табл. 5).

Расстановка потенциалов и перераспределение поставок

Таблица 5

Операция 2.2. Проверка небазисных клеток на соответствие их условию оптимальности.

Оптимальный план транспортной задачи должен отвечать критерию оптимальности, который выражается в том, соответствуют ли небазисные клетки матрицы условию, формулируемому следующим выражением:

, (3.6)

Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже cij, значит, использование данного маршрута не улучшит план, а если cij ниже разности потенциалов, т. е. условие (2.8) не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.

Проверим условие (2.8) для табл. 5.

Клетка А1В1: 4 – 5 < 10, условие выполняется.

Клетка А1В2: 7 – 5 < 9, условие выполняется и т. д.

Если для всех небазисных клеток условие 3 выполняется, то рассматриваемый план будет оптимален. Дальнейшие действия переходят по алгоритму к операции 4.

Однако для нашего примера это не так. Не выполняется условие для клетки А2В4 (10 – 0> 6), клетки А3В3 (13 – 1 > 9), а также для клеток А3В4, А4В3, из чего следует, что разработанный опорный план не оптимален. Отметим эти клетки.

Операция 3. Улучшение плана.

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

Операция 3.1. Построение цепи (контура, цикла) перераспределения поставок.

Улучшение плана осуществляется по одной из небазисных клеток, для которой условие оптимальности оказалось невыполненным. В нашем плане имеется четыре такие клетки. Выбираем одну из них, для которой условие оптимальности не выполняется в наибольшей степени. В нашем плане это клетка А2В4. Для нее условие оптимальности не выполнено на 4 единицы (10 – 0 – 6 = 4). Для этой клетки строим цепь перераспределения поставок. Цепь перераспределения поставок – это такая замкнутая ломаная линия, которая проходит по клеткам матрицы ходом шахматной ладьи. В вершинах контура обязательно лежит одна небазисная клетка (несоответствующая условию оптимальности, найденная ранее), а остальные соответствуют только базисным клеткам. Линии контура могут пересекаться. Для небазисной клетки А2В4 цепь будет проходить по клеткам А1В4, А1В3, А2В3 (табл. 6).

Возможные варианты построения цикла перераспределения

Таблица 6

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

Операция 3.2. Перераспределение поставок.

Перераспределение поставок (см. табл. 5) производится по цепи. Вначале определим объем перераспределения поставок. Для этого присвоим клеткам – вершинам цепи – знаки. В небазисную клетку А2В4 ставим «+», поскольку в нее будет вводиться поставка. Далее, чередуя «+» с «–», расставляем знаки по остальным вершинам контура. Величина объема перераспределения поставок принимается равной минимальной поставке в отрицательной клетке. Для нашего случая это 50 единиц груза. Перераспределение заключается в том, что к поставкам в положительных клетках найденный объем прибавляется, а для отрицательных клеток отнимается. Результат представлен в табл. 5

Функционал F' нового плана, представленного в табл. 5 (выделенные поставки), составляет 1950 ткм, что на 200 ткм меньше значения функционала F предыдущего плана.

Полученный улучшенный план, представленный в табл. 5, в свою очередь, требует проверки на оптимальность, поэтому необходимо вернуться к операции 2.

Совокупность действий, описанных в операциях 2 и 3, в процессе решения задачи повторяется до тех пор, пока не будет получен оптимальный план. Эта совокупность носит итеративный (циклический) характер, поэтому она называется итерацией. Через определенное число итераций план становится оптимальным. После этого осуществляется переход от второй операции к четвертой (табл. 7).

Повторение операций 2, 3

Таблица 7

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

Покажем дальнейшее решение задачи, основываясь на данных табл. 5 Результат действий второй и третьей итераций приведен в табл. 7

Проверка плана на оптимальность свидетельствует о том, что для двух клеток условия оптимальности не выполняются. После перераспределения поставок по клетке А4В3, получаем новый план (табл. 8).

Оптимальный план поставок

Таблица 8

Проверка плана перевозок на оптимальность по условию (3.6) показала, что для всех небазисных клеток матрицы условия оптимальности выполняются. Функционал F'' оптимального плана равен 1920 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.

Заключение.

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

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

Оптимизация системы состоит в поиске такого набора параметров управления, при котором целевая функция достигает экстремума. Этим достигается новое качественное состояние системы — экстремальность результата ее функционирования по заданному критерию качества. Новое качество постигается сознанием в этом процессе на более высокой ступени познания не как первичная логическая категория, обеспечивающая лишь весьма элементарные различения и оценку качества (типа “больше - меньше”), а как значительно более развитая категория количественно определенной оценки качества. Оптимальное (наилучшее из всех возможных) состояние управляемой системы и представляет собой такую количественно определенную оценку качественного состояния системы. Оптимизация решений в сложных системах придает им новое качество, количественно выражающееся в существенном повышении эффективности их функционирования.

Список использованной литературы.

1.Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации, 2008-440с 2.Корнев В.В, Курдюмов В.В. Прикладные методы оптимизации, 2009 –172с

3.Пантелеев, А.В. Методы оптимизации в примерах и задачах, 2009- 544с.

4.Юдин Д. Б. Вычислительные методы теории принятия решений, 2010 г.- 320 с.

myunivercity.ru

Реферат: Методы поисковой оптимизации

1. Назначение и классификация методов поисковой оптимизации

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

Исходными данными в методах поиска являются требуемая точность метода и начальная точка поиска Х0.

Затем выбирается величина шага поиска h, и по некоторому правилу происходит получение новых точек Хk+1по предыдущей точке Хk, при k = 0,1,2,… Получение новых точек продолжают до тех пор, пока не будет выполнено условие прекращения поиска. Последняя точка поиска считается решением задачи оптимизации. Все точки поиска составляют траекторию поиска.

Методы поиска могут отличаться друг от друга процедурой выбора величины шага h (шаг может быть одинаковым на всех итерациях метода или рассчитываться на каждой итерации), алгоритмом получения новой точки и условием прекращения поиска.

Для методов, использующих постоянную величину шага, h следует выбирать значительно меньше точности h » Öe). Если при выбранной величине шага h не удается получить решение с требуемой точностью, то нужно уменьшить величину шага и продолжить поиск из последней точки имеющейся траектории.

В качестве условий прекращения поиска принято использовать следующие:

все соседние точки поиска хуже, чем предыдущая;

çФ(Xk+1) - Ф(Xk)ç£ e, то есть значения целевой функции Ф(Х) в соседних точках (новой и предыдущей) отличаются друг от друга на величину не больше, чем требуемая точность e;

то есть все частные производные в новой точке поиска практически равны 0 или отличаются от 0 на величину, не превышающую заданной точности e.

Алгоритм получения новой точки поиска Хk+1по предыдущей точке Хkсвой для каждого из методов поиска, но всякая новая точка поиска должна быть не хуже предыдущей: если задача оптимизации является задачей поиска минимума, то Ф(Хk+1) £ Ф(Хk).

Методы поисковой оптимизации принято классифицировать по порядку производной целевой функции, используемой для получения новых точек. Так, в методах поиска нулевого порядка не требуется вычисления производных, а достаточно самой функции Ф(Х). Методы поиска первого порядка используют первые частные производные, а методы второго порядка используют матрицу вторых производных (матрицу Гессе).

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

Эффективность поискового метода определяют по числу итераций и по количеству вычислений целевой функции Ф(Х) на каждой итерации метода (N). Рассмотрим наиболее распространенные методы поиска, расположив их в порядке уменьшения числа итераций.

Для методов поиска нулевого порядка справедливо следующее: в методе случайного поиска нельзя заранее предсказать количество вычислений Ф(Х) на одной итерации N, а в методе покоординатного спуска N £ 2×n, где n- количество управляемых параметров X = ( x1, x2.,…,xn).

Для методов поиска первого порядка справедливы следующие оценки: в градиентном методе с постоянным шагом N=2×n; в градиентном методе с дроблением шага N = 2×n + n1, где n1– число вычислений Ф(Х), необходимых для проверки условия дробления шага; в методе наискорейшего спуска N=2×n+n2, где n2– число вычислений Ф(Х), необходимых для расчета оптимальной величины шага; а в методе Давидона – Флетчера - Пауэлла (ДФП) N = 2× n + n3, где n3– число вычислений Ф(Х), необходимых для расчета матрицы, приближающей матрицу Гессе ( для величин n1, n2, n3справедливо соотношение n1< n2<< n3).

И, наконец, в методе второго порядка - методе Ньютона N = 3×n2. При получении данных оценок предполагается приближенное вычисление производных по формулам конечных разностей / 6 /:

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

На практике широкое применение нашли метод наискорейшего спуска и метод ДФП, как методы с оптимальным соотношением числа итераций и их трудоемкости.

2. Методы поиска нулевого порядка

2.1. Метод случайного поиска

В методе случайного поиска исходными данными являются требуемая точность метода e, начальная точка поиска Х0= ( x10, x2.0,…,xn0) и величина шага поиска h. Поиск новых точек производится в случайном направлении, на котором и откладывается заданный шаг h (рис. 2.1), таким образом получают пробную точку Х^и проверяют, является ли пробная точка лучшей, чем предыдущая точка поиска. Для задачи поиска минимума это означает, что

Ф(Х^) £ Ф(Хk),k = 0,1,2… (2.4)

Если условие (2.4) выполнено, то пробную точку включают в траекторию поиска Хk+1= Х^. В противном случае, пробную точку исключают из рассмотрения и производят выбор нового случайного направления из точки Хk, k = 0,1,2,.

Несмотря на простоту данного метода, его главным недостатком является тот факт, что заранее неизвестно, сколько случайных направлений потребуется для получения новой точки траектории поиска Хk+1, что делает затраты на проведение одной итерации слишком большими. Кроме того, поскольку при выборе направления поиска не используется информация о целевой функции Ф(Х), число итераций в методе случайного поиска очень велико.

В связи с этим метод случайного поиска используется для исследования малоизученных объектов проектирования и для выхода из зоны притяжения локального минимума при поиске глобального экстремума целевой функции /6/.

2.2. Метод покоординатного спуска

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

Исходными данными в методе покоординатного спуска являются величина шага h и начальная точка поиска Х0= ( x10, x2.0,…,xn0). Движение начинаем из точки Х0вдоль оси x1 в сторону увеличения координаты. Получим пробную точку Х^с координатами ( x10+h, x20,…,xn0), при k = 0.

Сравним значение функции Ф(Х^) с значением функции в предыдущей точке поиска Хk. Если Ф(Х^) £ Ф(Хk) (мы предполагаем, что требуется решить задачу минимизации целевой функции Ф(Х)), то пробную точку включают в траекторию поиска ( Хk+1= Х^).

В противном случае, пробную точку исключаем из рассмотрения и получаем новую пробную точку, двигаясь вдоль оси x1 в сторону уменьшения координаты. Получим пробную точку Х^= ( x1k-h, x2.k,…,xnk). Проверяем, если Ф(Х^) > Ф(Хk), то продолжаем движение вдоль оси x2в сторону увеличения координаты. Получим пробную точку Х^= ( x1k, x2.k+h,…,xnk) и т.д. При построении траектории поиска повторное движение по точкам, вошедшим в траекторию поиска, запрещено. Получение новых точек в методе покоординатного спуска продолжается до тех пор, пока не будет получена точка Хk, для которой все соседние 2×n пробных точек (по всем направлениям x1, x2.,…,xn в сторону увеличения и уменьшения значения каждой координаты) будут хуже, то есть Ф(Х^) > Ф(Хk). Тогда поиск прекращается и в качестве точки минимума выбирается последняя точка траектории поиска Х* = Хk.

3. Методы поиска первого порядка

3.1. Структура градиентного метода поиска

В методах поиска первого порядка в качестве направления поиска максимума целевой функции Ф(Х) выбирается вектор градиент целевой функции grad (Ф(Хk)), для поиска минимума – вектор антиградиент -grad (Ф(Хk)). При этом используется свойство вектора градиента указывать направление наискорейшего изменения функции:

Для изучения методов поиска первого порядка важно также следующее свойство: вектор градиент grad (Ф(Хk)) направлен по нормали к линии уровня функции Ф(Х) в точке Хk(см. рис. 2.4). Линии уровня – это кривые, на которых функция принимает постоянное значение (Ф(Х) = соnst).

В данной главе мы рассмотрим 5 модификаций градиентного метода:

градиентный метод с постоянным шагом,

градиентный метод с дроблением шага,

метод наискорейшего спуска,

метод Давидона-Флетчера-Пауэлла,

двухуровневый адаптивный метод.

3.2. Градиентный метод с постоянным шагом

В градиентном методе с постоянным шагом исходными данными являются требуемая точность e, начальная точка поиска Х0и шаг поиска h.

Получение новых точек производится по формуле:

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

Каждая из формул (2.6), (2.7) является векторным соотношением, включающим n уравнений. Например, с учетом Хk+1= ( x1k+1, x2.k+1,…,xnk+1), Хk= ( x1k, x2.k,…,xnk) формула (2.6) примет вид:

или в скалярном виде

В общем виде (2.9) можно записать:

В качестве условия прекращения поиска во всех градиентных методах используется, как правило, комбинация двух условий: ç Ф(Xk+1) - Ф(Xk) ç £ e или

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

3.3. Градиентный метод с дроблением шага

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

Исходными данными являются требуемая точность e, начальная точка поиска Х0и начальная величина шага поиска h (обычно h = 1). Получение новых точек производится по формуле:

где hk– величина шага на k-ой итерации поиска, при hkдолжно выполняться условие:

Если величина hkтакова, что неравенство (2.13) не выполнено, то производится дробление шага до тех пор, пока данное условие не будет выполнено. Дробление шага выполняется по формуле hk= hk×a, где 0 < a < 1.Такой подход позволяет сократить число итераций, но затраты на проведение одной итерации при этом несколько возрастают.

3.4. Метод наискорейшего спуска

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

Исходными данными являются требуемая точность e, начальная точка поиска Х0.

Получение новых точек производится по формуле:

то есть выбор шага производится по результатам одномерной оптимизации по параметру h.

Основная идея метода наискорейшего спуска заключается в том, что на каждой итерации метода выбирается максимально возможная величина шага в направлении наискорейшего убывания целевой функции, то есть в направлении вектора-антиградиента функции Ф(Х) в точке Хk( рис. 2. 4).

При выборе оптимальной величины шага необходимо из множества ХМ = { Х½ Х = Хk– h×grad Ф(Хk), hÎ[0,¥) } точек, лежащих на векторе градиенте функции Ф(Х), построенном в точке Хk, выбрать ту, где функция Ф(h) = Ф(Хk– h ×grad Ф(Хk)) принимает минимальное значение.

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

4. Методы поиска второго порядка

Несмотря на простоту реализации, метод наискорейшего спуска не рекомендуется в качестве “серьезной” оптимизационной процедуры для решения задачи безусловной оптимизации функции многих переменных, так как для практического применения он работает слишком медленно. Причиной этого является тот факт, что свойство наискорейшего спуска является локальным свойством, поэтому необходимо частое изменение направления поиска, что может привести к неэффективной вычислительной процедуре. Более точный и эффективный метод решения задачи параметрической оптимизации (1.5) можно получить, используя вторые производные целевой функции (методы второго порядка). Они базируются на аппроксимации (то есть приближенной замене) функции Ф(Х) функцией j(Х),

где G(X0)- матрица Гессе (гессиан, матрица вторых производных), вычисленная в точке Х0:

Формула (2.17) представляет собой первые три члена разложения функции Ф(Х) в ряд Тейлора в окрестности точки Х0, поэтому при аппроксимации функции Ф(Х) функцией j(Х) возникает ошибка не более чем (½Х-Х0½)3. С учетом (2.17) в методе Ньютона исходными данными являются требуемая точность e и начальная точка поиска Х0, а получение новых точек производится по формуле:

где G-1(Хk) – матрица, обратная к матрице Гессе, вычисленная в точке поиска Хk( G(Хk)× G-1(Хk) = I, где I - единичная матрица).

Библиографический список

1. Кофанов Ю.Н. Теоретические основы конструирования, технологии и надежности радиоэлектронных средств. - М.: Радио и связь, 1991. - 360 с.

2. Норенков И.П., Маничев В.Б. Основы теории и проектирования САПР.- М.: Высш. шк., 1990.- 335 с.

3. Самойленко Н.Э. Основы проектирования РЭС. - Воронеж: ВГТУ, 1998. - 60 с.

4. Фролов В.Н., Львович Я.Е. Теоретические основы конструирования, технологии и надежности РЭА. - М.: Радио и связь, 1988. - 265 с.

5. Батищев Д.И. Поисковые методы оптимального проектирования. - М.: Сов. Радио, 1975. - 216 с.

6. Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.- 128 с.

7. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во Воронеж. гос. ун-та, 1997. 416 с.

8. Автоматизация проектирования РЭС: Учеб. пособие для вузов / О.В. Алексеев, А.А. Головков, И.Ю. Пивоваров и др.; Под. ред О.В. Алексеева. М: Высш. шк., 2000. 479 с.

superbotanik.net

Смотрите также

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..