g2 (Акчурин)
Описание файла
Файл "g2" внутри архива находится в папке "Акчурин". Документ из архива "Акчурин", который расположен в категории "". Всё это находится в предмете "базы данных" из 7 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "базы данных" в общих файлах.
Онлайн просмотр документа "g2"
Текст из документа "g2"
5
-
Основные понятия.
1Постановка задачи оптимизации.
Сама по себе постановка задачи оптимизации проста и естественна:
заданы множество и функция , определенная на , требуется найти точки минимума или максимума.
Условимся записывать задачу на минимум в виде:
где
- целевая функция;
- допустимое множество
- допустимая точка задачи ( 2.1 .0 ).
В основном мы будем иметь дело с конечномерными задачами оптимизации, то есть с задачами, в которых допустимое множество лежит в евклидовом пространстве ( ).
Точка , являющаяся решением задачи ( 2.1 .0 ), может быть точкой глобального или локального минимума.
Определение.
1) точкой глобального минимума функции на множестве или глобальным решением задачи ( 2.1 .0 ), если
2) точкой локального минимума функции на множестве или локальным решением задачи ( 2.1 .0 ), если
Если неравенство в ( 2.1 .0 ) или в ( 2.1 .0 ) выполняется как строгое при то - точка строгого минимума (строгое решение) в глобальном или локальном смысле.
Ясно, что глобальное решение является и локальным; обратное неверно.
Для отражения того факта, что точка является точкой глобального минимума функции на множестве , обычно используется запись
Множество всех точек глобального минимума на , обозначают через
где - минимальное значение функции на множестве .
В этом случае - это просто произвольная точка из множества
По аналогии с ( 2.1 .0 ) записывают задачу максимизации функции на множестве , в виде
Заменяя в данных выше определениях слово «минимум» на «максимум» и заменяя знак неравенств в ( 2.1 .0 ), ( 2.1 .0 ) на противоположный, получаем соответствующие понятия для задачи ( 2.1 .0 ).
Решения задач ( 2.1 .0 ), ( 2.1 .0 ), то есть точки минимума и максимума функции на множестве , называются также точками экстремума, а сами задачи ( 2.1 .0 ), ( 2.1 .0 ) - экстремальными задачами.
Ясно, что задача ( 2.1 .0 ) эквивалентна задаче
в том смысле, что множества глобальных и локальных, строгих и нестрогих решений этих задач соответственно совпадают. Это позволяет без труда переносить результаты, полученные для задачи минимизации, на задачи максимизации, и наоборот.
При изучении задач оптимизации в первую очередь возникает вопрос о существовании решения. Ответ на этот вопрос дает теорема Вейерштрасса.
Теорема Вейерштрасса.
Пусть - компакт в , - непрерывная функция на множестве . Тогда точка глобального минимума функции на существует (глобальное решение задачи существует).
Напоминание:
Компакт - замкнутое ограниченное множество.
2Классификация задач оптимизации.
Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции и множества :
-
детерминированные, стохастические, задачи оптимизации с неопределенностями;
-
статические, динамические (например, задачи управления);
-
безусловной и условной оптимизации;
-
с непрерывными и дискретными переменными (частично - целочисленные, целочисленные, с булевыми переменными);
-
однокритериальные и многокритериальные;
-
линейные и нелинейные;
-
одномерные и многомерные, причем многомерные задачи могут быть малой и большой размерности;
-
с выпуклыми и невыпуклыми целевыми функциями;
-
одноэкстремальные и многоэкстремальные.
3Понятие о численных методах оптимизации.
В большинстве случаев задачу оптимизации:
не удается решить опираясь на необходимые и достаточные условия оптимальности или на геометрическую интерпретацию задачи, и приходится ее решать численно с применением вычислительной техники. Причем, наиболее эффективными оказываются методы, разработанные специально для решения конкретного класса задач оптимизации, так как они позволяют полнее учесть ее специфику.
Любой численный метод имеет два этапа:
-
первый этап любого численного метода (алгоритма) решения задачи оптимизации основан на точном или приближенном вычислении ее характеристик (значений целевой функции; значений функций, задающих допустимое множество, а также их производных);
-
во втором этапе, на основании полученной информации строится приближение к решению задачи - искомой точке минимума , или, если такая точка не единственна, к множеству точек минимума.
Иногда, если только это требуется, строится и приближение к минимальному значению целевой функции
.
Для каждой конкретной задачи вопрос о том, какие характеристики следует выбрать для вычисления, решается в зависимости от свойств минимизируемой функции, ограничений и имеющихся возможностей по хранению и обработки информации.
В зависимости от того какие характеристики, в частности, целевой функции берутся, алгоритмы делятся на алгоритмы:
-
нулевого порядка - в них используется информация только о значениях минимизируемой функции;
-
первого порядка - использующие информацию также и о значениях первых производных;
-
второго порядка - использующие, кроме того, информацию о вторых производных;
и так далее.
Когда решен вопрос о том, какие именно характеристики решаемой задачи следует вычислять, то для задания алгоритма достаточно указать способ выбора точек вычисления.
В зависимости от способа выбора точек вычисления, алгоритмы делятся на пассивные и активные(последовательные).
В пассивных алгоритмах все точки выбираются одновременно до начала вычислений.
В активных (последовательных) алгоритмах точки вычисления выбираются поочередно, то есть точка выбирается, когда уже выбраны точки предыдущих вычислений и в каждой из них произведены предусмотренные алгоритмом вычисления, результаты которых будем обозначать соответственно через .
Таким образом, последовательный алгоритм определяется точкой
при этом
( 2.3.0 )
На практике обычно используются наиболее простые виды зависимости, например:
то есть выбор точки очередного вычисления зависит лишь от точки предыдущего вычисления и полученного результата или
то есть выбор зависит от и линейной комбинации всех полученных результатов(например, в методе сопряженных градиентов).
В дальнейшем для нахождения будем пользоваться соотношением вида
При этом конкретный алгоритм определяется:
-
заданием точки ;
-
правилами выбора векторов и чисел на основе полученной в результате вычислений информации;
-
условием остановки.
Правила выбора и чисел могут предусматривать вычисления характеристик не только в точках , но и в других точках, отличных от . Именно поэтому в формулах ( 2.3 .0 ) и ( 2.3 .0 ) употреблены различные индексы.
Вектор определяет направление -го шага метода минимизации, а коэффициент - длину этого шага.
Обычно название метода минимизации определяется способом выбора , а его различные варианты связываются с разными способами выбора .
Наряду с термином шаг метода мы будем пользоваться также термином итерация метода.
Среди методов минимизации можно условно выделить:
-
конечношаговые методы;
-
бесконечношаговые методы.
Конечношаговыми (или конечными) называются методы, гарантирующие отыскание решения задачи за конечное число шагов.
Для бесконечно шаговых методов достижение решения гарантируется лишь в пределе.
4Сходимость методов оптимизации.
Важной характеристикой бесконечношаговых методов является сходимость.
Метод сходится если , где - решение задачи
Если , то иногда также говорят, что метод ( 2.3 .0 ) сходится (по функции), при этом последовательность называют минимизирующей. Минимизирующая последовательность может не сходится к точке минимума.
Пример:
В данном примере минимизирующая последовательность не сходится к точке минимума .
В случае, когда точка минимума не единственна, под сходимостью метода понимается сходимость к множеству точек минимума функции .
Говорят, что:
1) последовательность сходится к точке линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы и , что
2) последовательность сходится к точке сверхлинейно(со сверхлинейной скоростью), если: