Лекция 12. Методы оптимизации.

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

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

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

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

- Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции от n действительных переменных и определении соответствующих значений аргументов

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

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

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

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

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

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

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

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

В последнем случае достаточно выполнения неравенства .

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

1 шаг: внутри отрезка выбираем некоторые внутренние точки и и вычисляем значения целевой функции и (рис. 12.1).

Рисунок 12.1 – Иллюстрация 1-го шага алгоритма

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

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

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке . Пусть длина интервала неопределенности равна l, а точка деления разбивает его на части , .

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

Из этого соотношения можно найти точку деления, вычислив отношения и . Преобразуем выражение и найдем значения и :

; ; ;

; ; .

Поскольку нас интересует только положительное решение, то

; .

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

В данном случае имеем ; ; ; .

Аналогично, .

Начальная длина интервала неопределенности составляет . После первого шага оптимизации получается новый интервал неопределенности — отрезок . Его длина равна .

На втором шаге отрезок также делится в соотношении золотого сечения. При этом одной из точек деления будет точка . Покажем это:

Последнее равенство следует из соотношения .

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

По аналогии можно записать координаты точек деления у и z отрезка на k-м шаге оптимизации : , .

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

СПИСОК ЛИТЕРАТУРЫ

1. Месарович М., Такахара Я. Общая теория систем. – М.: Мир, 1978. — 311с.

2. Уемов А.И. Системный подход и общая теория систем. – М.: Мысль. — 1978, — 272 с.

3. Анфилатов В.С., Емельянов А.А., Кукушкин А.А. Системный анализ в управлении. - М.: Радио и связь, 2002. — 368 с.

4. Тихонов В.И. Статистическая радиотехника. – М.: Радио и связь, 1982. — 624 с.

5. Справочник по теории автоматического управления / Под ред. А.А. Красовского. – М.: Наука, 1987. — 712 с.

6. Сейдж Э., Дж. Мэлс. Теория оценивания и ее применение в связи и управлении. — М.: Связь, 1976. — 496.

7. Невельсон М., Хасьминский Р. Стохастическая аппроксимация и рекурентное оце-нивание — М.: Наука, 1972. — 232 с.

8. Саридис Дж. Самоорганизующиеся стохастические системы управления. - М.: Нау-ка, 1980. — 400 с.

9. Цыпкин Я.З. Основы теории обучающихся систем — М.: Наука, 1970. — 384 с.

10. Поповский В.В., Олейник В.Ф. Математические основы управления и адаптации в телекоммуникационных системах — Х.: СМИТ, 2011. — 362 с.

11. Математичні основи теорії телекомунікаційних систем/ За загальною ред. В.В. По-повського — Харків — Х.: СМІТ, 2006. — 564 с.

12. Popovskij V. Control and Adaptation in Telecommunication Systems: Mathematical Foundations (Lecture Notes in Electrical Engineering) // Publisher: Springer, 2011. – 187 p.

13. Тарков М.С. Нейкомпьютерные системы — М.: Б13, 2006. — 142 с.

13.

14. Осин А.В., Смольский С.М., Шелухин О.И Самоподобие и фракталы. Телекоммуникационные приложения – М.: Физматлит, 2008 - 368 c.