Рубежный контроль. 1 Рубежка Методы оптимизации. 1. в чем заключается математическая постановка задачи безусловной минимизации (оптимизации)

• Название: 1. в чем заключается математическая постановка задачи безусловной минимизации (оптимизации)
• Анкор: Рубежный контроль
• Дата: 28.10.2020
• Размер: 0.61 Mb.
• Имя файла: 1 Рубежка Методы оптимизации.docx
• Тип: Документы; #146380

1.В чем заключается математическая постановка задачи безусловной минимизации (оптимизации)

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

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

Ошибка заключается в том, что ставится задача поиска оптимума 2-х величин, противостоящих друг другу по своей сути.

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности.

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

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

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

4. Учет ограничений.

Как правило, формулировка задачи оптимизации включает:

1) выбор критерия оптимальности;

2) установление ограничений;

3) выбор оптимизирующих факторов;

4) запись целевой функции.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

Наиболее общей постановкой оптимальной задачи является выражение критерия оптимальности в виде экономической оценки (производительность, себестоимость продукции, прибыль, рентабельность). Однако в частых задачах оптимизации, когда объект является частью технологического процесса, не всегда удается или не всегда целесообразно выделять прямой экономический показатель, который бы полностью характеризовал эффективность работы рассматриваемого объекта. В таких случаях критерием оптимальности может служить технологическая характеристика, косвенно оценивающая экономичность работы агрегата (время контакта, выход продукта, степень превращения, температура). Например, устанавливается оптимальный температурный профиль, длительность цикла –«реакция-регенерация». Но в любом случае любой критерий оптимальности имеет экономическую природу.

Рассмотрим более подробно требования, которые должны предъявляться к критерию оптимальности.

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

2. Критерий оптимальности должен быть единственным.

3. Критерий оптимальности должен отражать наиболее существенные стороны процесса.

4. Желательно, чтобы критерий оптимальности имел ясный физический смысл и легко рассчитывался.

2. Отличие модели задачи условной оптимизации от модели безусловной оптимизации.

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

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации. Существуют также приближенные методы решения нелинейных задач. Это методы основанные на методе кусочно-линейной аппроксимации. Точность нахождения решений зависит от количества интервалов, на которых мы находим решение линейной задачи, максимально приближенной к нелинейной. Такой метод позволяет производить расчеты с помощью симплекс-метода. Обычно в линейных моделях коэффициенты целевой функции постоянны и не зависят от значения переменных. Однако существует ряд задач, где затраты зависят от объема нелинейно.

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

4. Дать классификацию и краткую характеристику методов безусловной оптимизации.

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

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

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

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

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

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

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

 

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

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

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

Метод случайного поиска. Метод имеет большое количество модификаций. Общее для них состоит в использовании элемента случайности (путем розыгрыша случайного события) при определении направления поиска и величины шага изменения параметров. Метод эффективен для сложных систем с большим числом параметров (см. [6.44]).

 
Методы первого порядка

 

Методы первого порядка используют, если возможно найти первую производную исследуемой функции. К данному классу относятся градиентные методы. Их суть заключается в определении лучшего направления и шага поиска минимума функции по значениям первых производных в некоторой точке х^(k). Наибольшее значение производной показывает направление наискорейшего уменьшения функции, и в этом направлении рассчитывается следующее приближение функции у = f(x^(k+1)), параметры которой отличаются на величину некоторого шага Dх. В зависимости от способа задания этого шага и производится классификация градиентных методов: градиентный спуск; наискорейший спуск; градиентный спуск с постоянным шагом; градиентный спуск с переменным шагом. Методы эффективны Для функций со слабовыраженной нелинейностью (см. [6.44]).

 

Методы второго порядка

 

Методы второго порядка используют, если возможно найти вторую производную исследуемой функции. Их основой является метод Ньютона, предполагающий аппроксимацию исследуемой функции Y = f(x) квадратичным полиномом в окрестностях некоторой точки x^(k)(точки начального приближения). Следующее приближение x^(k+1) определяется путем минимума квадратичной аппроксимации функции F(x), т.е. такой точки в окрестности x^(k)в которой вид функции в наибольшей степени "похож" на квадратичную. Различные модификации метода Ньютона в основном отличаются друг от друга способами расчета вторых производных. Методы второго порядка сходятся быстрее градиентных, однако требуют вычислений вторых производных (см. [6.44]).

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

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

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

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

Метод случайного поиска. Метод имеет большое количество модификаций. Общее для них состоит в использовании элемента случайности (путем розыгрыша случайного события) при определении направления поиска и величины шага изменения параметров. Метод эффективен для сложных систем с большим числом параметров (см. [6.44]).

6. Сущность метода деформированного многогранника



7. Перечислить основные шаги метода деформированного многогранника





8. В чем заключается идея метода параллельных касательных.

Суть метода такова. Выбирается некоторая начальная точка х[0] и выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х[1] . Затем выбирается точка х[2], не лежащая на прямой х[0] - х[1], и осуществляется одномерный поиск вдоль прямой, параллельной х[0] - х[1],. Полученная в результате точка х[3] вместе с точкой х[1] определяет направление x[1] ‑ х[3] одномерного поиска, дающее точку минимума х^*. В случае квадратичной функции n переменных оптимальное значение находится за п итераций. Поиск минимума при этом в конечном счете осуществляется во взаимно сопряженных направлениях. В случае неквадратичной целевой функции направления поиска оказываются сопряженными относительно матрицы Гессе. Алгоритм метода параллельных касательных состоит в следующем.

9. В чем заключается сущность метода покоординатного спуска.
Суть метода заключается в поочередном поиске минимума функции по одной из координат, полагая, что другие координаты фиксированы какими-то начальными значениями (таким образом получаем задачу поиска минимума одномерной функции). После нахождения точки минимума по одной координате осуществляется поиск минимума по другой координате и так далее пока не пройдем по всем координатам. Более подробное описание метода с математическим обеспечением можно без проблем найти в интернете.
Для нормального выполнения метода (именно в моей реализации) требуется целевая функция, начальная точка отсчета (любая случайная), допустимая погрешность результата и максимально допустимое количество итераций цикла. Последний входной параметр нужен для того, чтоб можно было закончить программу, если заданная погрешность не может быть достигнута. В некоторых реализациях еще одним требуемым параметром является шаг, с которым будет осуществляться спуск по координате при поиске минимума. В данной реализации шаг не требуется, поскольку поиск минимума одномерной функции осуществляется методом золотого сечения.

10.В чем заключается сущность метода дихотомического поиска.

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

Пример:

Пускай задана функция .

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

,

где — некоторое число в интервале

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

Запасной вариант:

Дихотоми́я (греч. διχοτομία: δῐχῆ, «надвое» + τομή, «деление») — раздвоенность, последовательное деление на две части, более связанные внутри, чем между собой. Способ логического деления класса на подклассы, который состоит в том, что делимое понятие полностью делится на два взаимоисключающих понятия. Дихотомическое деление в математике, философии, логике и лингвистике является способом образования подразделов одного понятия или термина и служит для образования классификации элементов.

11.Изложить метод Фибоначчи.

Метод Фибоначчи — это улучшение реализации поиска с помощью золотого сечения, служащего для нахождения минимума/максимума функции. Как и в методе золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.
12.В чем заключается сущность метода золотого сечения.

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



13. Объяснить алгоритм метода золотого сечения.

Алгоритм:

1. 
   На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
   
2. 
   После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.
   
3. 
   На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
   
4. 
   Процедура продолжается до тех пор, пока не будет достигнута заданная точность.
   

14. Правила постановки задач оптимизации.

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

"Получить максимальную производительность при минимальной себестоимости".

Ошибка заключается в том, что ставится задача поиска оптимума 2-х величин, противоречащих друг другу по своей сути.

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

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

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

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

4. Учет ограничений.

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

15.Правила выбора критерия оптимальности.

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

Наиболее общей постановкой оптимальной задачи является выражение критерия оптимальности в виде экономической оценки (производительность, себестоимость продукции, прибыль, рентабельность). Однако в частых задачах оптимизации, когда объект является частью технологического процесса, не всегда удается или не всегда целесообразно выделять прямой экономический показатель, который бы полностью характеризовал эффективность работы рассматриваемого объекта. В таких случаях критерием оптимальности может служить технологическая характеристика, косвенно оценивающая экономичность работы агрегата (время контакта, выход продукта, степень превращения, температура). Например, устанавливается оптимальный температурный профиль, длительность цикла –«реакция-регенерация». Но в любом случае любой критерий оптимальности имеет экономическую природу.

Рассмотрим более подробно требования, которые должны предъявляться к критерию оптимальности.

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

2. Критерий оптимальности должен быть единственным.

3. Критерий оптимальности должен отражать наиболее существенные стороны процесса.

4. Желательно, чтобы критерий оптимальности имел ясный физический смысл и легко рассчитывался.

16. Виды ограничений.





17. Выпуклые функции.

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

18.Стратегия поиска экстремумов унимодальной функции.

Функция одной переменной, имеющая в интервале исследова­ния один горб (впадину), называется унимодальной, или: функция у—унимодальная, если х\<Хот (xi>Xoirr), х<2<Хот (л:2>^опт) я х,<х,,то Y(xi)Y(x,)) [18].

19. В чем заключается сущность алгоритма Свенна.

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