<<
>>

МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 5.1.1. Постановка задачи и стратегии поиска

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

Требуется найти безусловный минимум функции /(х) одной переменной,

т.е. такую точку х* е Я, что /(**) = пип /(х).

X € Я

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

§ 2).

Однако проблема получения решения уравнения = о может оказаться

ах

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

Замечания 5.1.

1. Для методов одномерной минимизации типично задание априорной ин­формации о положении точки минимума с помощью начального интервала не­определенности 1о=[яо»^gt;] (Рис- 5.1). Предполагается, что точка минимума х* принадлежит интервалу Ц, но ее точное значение неизвестно.

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

Определение 5.1. Функция /(х) называется унимодальной на интервале

Ц = [яоgt;^gt;]» если она достигает глобального минимума на [д0, в единственной

точке х*, причем слева от х* эта функция строго убывает, а справа от х* строго возрастает. Если а0 pound; у lt; г lt; х*, то /(у) gt; /(г), а если х* lt; у lt; г ^ Ь0, то /(у) lt; /(г) (рис. 5.1, а).

Отметим, что непрерывная строго выпуклая функция является унимодаль­ной. Однако .определению 5.1 могут удовлетворять и функции, не являющиеся непрерывными и выпуклыми (рис. 5.1, б).

3. Методы одномерной минимизации широко применяются в методах первого и второго порядков для нахождения оптимальной величины шага (см.

§ 6 и 7). При этом левая граница начального интервала неопределенности, как правило, совпадает с началом координат, т.е. а0 = 0.

Стратегии поиска

Существуют две принципиально различные стратегии выбора точек, в ко­торых производится вычисление значений функции. Если все точки задаются заранее, до начала вычислений, - это пассивная (параллельная) стратегия. Если эти точки выбираются последовательно в процессе поиска с учетом результатов предыдущих вычислений,- это последовательная стратегия. Примером реализации пассивной стратегии является метод равномерного поиска (см. разд. 5.1.1).

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

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

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

Стратегия поиска включает в себя три этапа:

1. Выбор начального интервала неопределенности. Границы д0,^ ин­тервала должны быть такими, чтобы функция /(*) была унимодальной (см.

определение 5.1).

2. Уменьшение интервала неопределенности.

3. Проверку условия окончания. Поиск заканчивается, когда длина теку­щего интервала неопределенности \ak, bk ] оказывается меньше установленной величины.

Ответом является множество точек, принадлежащих последнему интервалу неопределенности, среди которых каким-либо образом выбирается решение за­дачи X* .

Замечания 5.2.

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

2. Для эвристического выбора начального интервала неопределенности можно применить алгоритм Свенна [Swann W.H.]:

1) задать произвольно следующие параметры: х° - некоторую точку, / gt; 0 - величину шага. Положить к = 0 ;

2) вычислить значение функции в трех точках: х° -1, х°, х° +1\

3) проверить условие окончания:

а) если f[x° - gt; f[x°j lt; /(x° + /), то начальный интервал неопре­

деленности найден: [яоgt;^о] = [*° - *» *° +

б) если /(х° - г) й /(дс°) pound; /( х° + *|, то функция не является унимодаль­ной (см.

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

в) если условие окончания не выполняется, то перейти к шагу 4;

4) определить величину Д :

а) если /(х° - /) gt; /(*°) ^ /(*° + /), то Д = /; а0 = х°; х1 = х° + *; к = 1 ;

б) если /(х° -*)lt; /(х°)lt;/(х° + /), то Д = - Аь =х°; х1 = х° - г ;pound; = 1 ;

5) найти следующую точку хк+{ = хк + 2к Д;

6) проверить условие убывания функции:

а) если /(х*+1) lt; /(**) и Д = Г , то л0 = ;

если /(х*+1) lt; /(**) и Д = -г, то Ьц = хк;

в обоих случаях положить к = к +1 и перейти к шагу 5;

б) если /(х*+1) gt; /(**), процедура завершается. При Д = г положить

Ь0 = хк+х, а при Д = -/ положить д0 = **+1 • ® результате имеем [яо»^ь] - иско­мый начальный интервал неопределенности.

3. Уменьшение интервала неопределенности, осуществляемое при исполь­зовании последовательной стратегии, производится на основании вычисления функции в двух точках текущего интервала. Свойство унимодальности позволяет определить, в каком из возможных подынтервалов точка минимума отсутствует. Пусть в точках у иг интервала [д,pound;] вычислены значения функции: /(у) и

/(г). Если /(у)gt;/(г), то х* г[д,у) и поэтому х* е[у,Ь] (рис. 5.2, а). Если

/(у) lt;/(*)gt; то х* ё(г,pound;] и поэтому х* е[д,г] (рис. 5.2, б). Иными словами, в качестве нового интервала берется quot;гарантирующий интервалquot;, наверняка со­держащий точку минимума. Если /(у) = /(г), в качестве нового интервала мож­но взять любой из изображенных на рис. 5.2.

Для оценки эффективности алгоритмов уменьшения интервала не­определенности при заданном числе N вычислений функции введем критерий.

Определение 5.2. Характеристикой относительного уменьшения началь­ного интервала неопределенности называется отношение длины интервала, полу­чаемого в результате N вычислений функции, к длине начального интервала не­определенности: /?(ЛГ) =

Пример 5.1. Найти начальный интервал неопределенности для поиска ми­нимума функции /(х) = (х - 5)2.

? Воспользуемся алгоритмом Свенна.

1. Зададим х° = 1 и t = 1. Положим к = О.

2°. Вычислим значения функции в точках х° - г = 0; х° = 1; х° + / = 2:

/(0) = 25, /(1) = 16; /(2) = 9.

3°. Условия окончания не выполняются.

4°. Так как /(0) gt; /(1) gt; /(2), то А = 1, а0 = 1, х1 = х° + * = 2, к = 1.

5°. Найдем следующую точку х2 = х1 + 2Д = 2 + 2 = 4.

6°. Так как /(*2) = 1 lt; /(х1) и А = 1, то а0 = х1 = 2. Положим к = 2 и пе­рейдем к шагу 5.

51. Найдем следующую точку х3 = х2+4Д = 4 + 4 = 8.

61. Так как /(*3) = 9 gt; /(*2) = 1 и А = * = 1, то поиск завершен и правая

граница ^ = х3 = 8. Поэтому начальный интервал неопределенности имеет вид [доЛ] = [2,8]. #9632;

5.1.2.

<< | >>
Источник: Пантелеев А. В., Летова Т. А.. Методы оптимизации в примерах и задачах: Учеб. посо- бие/А. В. Пантелеев, Т. А. Летова. — 2-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 5.1.1. Постановка задачи и стратегии поиска:

  1. 2.5. РОЛЬ ПОЛЬЗОВАТЕЛЯ В СОЗДАНИИ АИС И АИТ И ПОСТАНОВКЕ ЗАДАЧ
  2. 2.6. ТЕХНОЛОГИЯ ПОСТАНОВКИ ЗАДАЧИ
  3. 4. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ (МИНИМИЗАЦИИ) УНИМОДАЛЬНЫХ ФУНКЦИЙ
  4. Отсутствие постановки задачи менеджмента на предприятии.
  5. Глава 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  6. Общая постановка задачи динамического программирования
  7. § 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
  8. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
  9. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 5.1.1. Постановка задачи и стратегии поиска
  10. ПОСТАНОВКА ЗАДАЧИ И СТРАТЕГИЯ РЕШЕНИЯ
  11. § 14. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ
  12. 3.4 Постановка задачи 3.4.1 Цель и назначение автоматизированного варианта решения задачи
  13. §7.1. Общая постановка задачи. Линейная модель
  14. 6.1. Постановка задачи моделирования
  15. 14.3. Постановка задач и выбор метода ценообразования
  16. Постановка задач
  17. ЧАСТЬ III. ТОП-МЕНЕДЖМЕНТ: ЗАДАЧИ, ОРГАНИЗАЦИЯ, СТРАТЕГИИ