Все Лекции по Оптимизации (g2)

Посмотреть архив целиком

5



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

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

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

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


Условимся записывать задачу на минимум в виде:

( 2.1.0 )

где

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

- допустимое множество

- допустимая точка задачи ( 2.1 .0 ).


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

Точка , являющаяся решением задачи ( 2.1 .0 ), может быть точкой глобального или локального минимума.


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

Точка называется

1) точкой глобального минимума функции на множестве или глобальным решением задачи ( 2.1 .0 ), если

( 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.1 .0 ) - экстремальными задачами.

Ясно, что задача ( 2.1 .0 ) эквивалентна задаче

, ,

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


При изучении задач оптимизации в первую очередь возникает вопрос о существовании решения. Ответ на этот вопрос дает теорема Вейерштрасса.


Теорема Вейерштрасса.

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

Напоминание:

Компакт - замкнутое ограниченное множество.

    1. Классификация задач оптимизации.

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

  1. детерминированные, стохастические, задачи оптимизации с неопределенностями;

  2. статические, динамические (например, задачи управления);

  3. безусловной и условной оптимизации;

  4. с непрерывными и дискретными переменными (частично - целочисленные, целочисленные, с булевыми переменными);

  5. однокритериальные и многокритериальные;

  6. линейные и нелинейные;

  7. одномерные и многомерные, причем многомерные задачи могут быть малой и большой размерности;

  8. с выпуклыми и невыпуклыми целевыми функциями;

  9. одноэкстремальные и многоэкстремальные.

    1. Понятие о численных методах оптимизации.

В большинстве случаев задачу оптимизации:

, ( 2.3.0 )

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

Любой численный метод имеет два этапа:

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


  1. во втором этапе, на основании полученной информации строится приближение к решению задачи - искомой точке минимума, или, если такая точка не единственна, к множеству точек минимума.


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

.

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

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

  1. нулевого порядка - в них используется информация только о значениях минимизируемой функции;

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

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

и так далее.


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


В зависимости от способа выбора точек вычисления, алгоритмы делятся на пассивные и активные(последовательные).


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

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

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

и набором отображений вида

при этом

( 2.3.0 )

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

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

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


В дальнейшем для нахождения будем пользоваться соотношением вида

( 2.3.0 )

При этом конкретный алгоритм определяется:

  1. заданием точки ;

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

  3. условием остановки.


Правила выбора и чисел могут предусматривать вычисления характеристик не только в точках , но и в других точках, отличных от . Именно поэтому в формулах ( 2.3 .0 ) и ( 2.3 .0 ) употреблены различные индексы.


Вектор определяет направление -го шага метода минимизации, а коэффициент - длину этого шага.

Обычно название метода минимизации определяется способом выбора , а его различные варианты связываются с разными способами выбора .

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


Среди методов минимизации можно условно выделить:

  • конечношаговые методы;

  • бесконечношаговые методы.


Конечношаговыми (или конечными) называются методы, гарантирующие отыскание решения задачи за конечное число шагов.

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

    1. Сходимость методов оптимизации.

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

Метод сходится если , где - решение задачи

.

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


Пример:

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


В случае, когда точка минимума не единственна, под сходимостью метода понимается сходимость к множеству точек минимума функции .

Пусть .

Говорят, что:

1) последовательность сходится к точке линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы и , что

при ( 2.4.0 )

2) последовательность сходится к точке сверхлинейно(со сверхлинейной скоростью), если:

, при ( 2.4.0 )

3) последовательность сходится к точке с квадратичной скоростью сходимости, если существуют такие константы и , что

при ( 2.4.0 )

Иногда, сохраняя ту же терминологию, неравенства ( 2.4 .0 ) - ( 2.4 .0 ) заменяют соответственно на неравенства


при ( 2.4.0 )

( 2.4.0 )

при , ( 2.4.0 )

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

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

    1. Условия остановки.

(критерии окончания счета).

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

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

( 2.5.0 )

( 2.5.0 )

( 2.5.0 )

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


Критерий ( 2.5 .0 ) относится лишь к задачам безусловной оптимизации. Его выполнение означает, что в точке с точностью выполняется условие стационарности.

В задаче условной оптимизации критерий ( 2.5 .0 ) следует заменить на критерий - стационарности, соответствующий данной задаче.


Случайные файлы

Файл
34055.rtf
145383.rtf
118734.rtf
182271.rtf
20507-1.rtf