Использование градиентных методов оптимизации

для решения задач оценки параметров математических моделей

МИНистерство ОБРАЗОВАНИЯ И НАУКИ РФ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ГОУ ВПО «ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Автоматизированные системы обработки информации

и управления»

Использование градиентных методов

оптимизации

для решения задач оценки параметров

математических моделей

Часть 2

Методические указания к лабораторной работе

по дисциплине «Методы оптимизации»

Волгоград

2011

УДК 519.87

И 88

Использование градиентных методов оптимизации для решения задач оценки параметров математических моделей: методические указания к лабораторной работе по дисциплине «Методы оптимизации». Часть 2 / Сост. Е. Г. Крушель, Е. А. Алейникова. – Волгоград: ИУНЛ ВолгГТУ, 2011. – 35 с.

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

Форма изложения полностью соответствует форме изложения первой части методических указаний.

Методические указания предназначены в помощь студентам, обучающимся по направлению 230100 «Информатика и вычислительная техника».

Ил. 14. Табл. 2. Библиогр.: 8 назв.

Рецензент к. т. н. В. О. Петров 

Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

Ó Волгоградский

государственный

технический

университет, 2011

Содержание

ВВЕДЕНИЕ.. 4

1 МЕТОДИКА ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ... 7

1.1 Использование масштабирования производственной функции Кобба-Дугласа 7

1.2 Описание процедуры масштабирования производственной функции Кобба-Дугласа 7

1.3 Задача идентификации с использованием масштабирования. 9

1.4 Основные соотношения, используемые в градиентных методах с использованием масштабирования 10

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

1.5.1 Градиентный метод с постоянным шагом.. 12

1.5.2. Градиентный метод с переменным шагом, убывающим в ходе итераций независимо от формы минимизируемой функции. 15

1.5.3 Метод наискорейшего спуска. 18

1.5.4 Метод Ньютона. 19

1.6 Оценка качества решения задачи идентификации параметров производственной функции Кобба-Дугласа градиентными методами с использованием масштабирования. 21

1.6.1 Сводка результатов идентификации параметров. 21

1.6.2 Значения показателей качества для градиентных методов с использованием масштабирования 21

1.6.3 Анализ применимости градиентных методов для идентификации параметров производственной функции Кобба-Дугласа с использованием масштабирования. 23

1.7 Общий вывод об эффективности использования масштабирования для решения задачи идентификации параметров производственной функции Кобба-Дугласа. 24

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

2.1 Исследование влияния настроечных параметров градиентных алгоритмов на качество идентификации 26

2.2 Исследование влияния на качество идентификации точности определения параметров и объема экспериментальных данных. 26

Требования к содержанию отчета.. 28

Контрольные вопросы... 28

Список литературы... 30

ПРИЛОЖЕНИЕ.. 31

ВВЕДЕНИЕ

Время выполнения лабораторной работы (аудиторные часы) – 4 часа.

Время самостоятельной работы студента (дополнительные часы) – 4 часа.

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

Лабораторная работа состоит из двух частей:

Часть первая: Решение задачи идентификации параметров производственной функции градиентными методами.

Часть вторая: Инженерный подход к решению задачи оценки параметров производственной функции.

Первая часть лабораторной работы описана в методических указаниях [1].

Общие сведения:

Описание задачи параметрической идентификации и идеи ее решения, положенные в основу написания методических указаний, основаны на информации, представленной в [2].

Использование методов нахождения экстремума скалярной функции векторного аргумента в задаче параметрической идентификации иллюстрируется в [1] на примере оценки параметров модели производственной функции Кобба-Дугласа [2].

Как указанно в [1], затраты на ресурсы растут квадратично в зависимости от количества этих ресурсов, а доход зависит от ресурсов согласно производственной функции Кобба-Дугласа:

(1)

где Y(•)– выпуск продукции в стоимостном выражении (доход); К – стоимость производственных фондов; L – объем трудовых ресурсов стоимостном выражении; А, a, b > 0 – константы, a + b £ 1.

При решении задачи определения параметров функции Кобба-Дугласа с использованием известных методов параметрической идентификации необходимо найти оценки неизвестных параметров A, a , b, которые должны доставлять минимум критерию, построенному на квадратичной функции отклонений расчетов по модели (1) от фактических значений производственной функции:

(2)

где . (3)

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

Следует отметить, что при отсутствии искажений в исходных данных, критерий (3) имеет очевидный минимум (равный нулю) когда оценки неизвестных параметров функции Кобба-Дугласа точно совпадают истинными значениями A, a , b. Можно надеяться, что все известные градиентные методы оптимизации позволят приблизиться к точке минимума и в результате найти оценки параметров, близкие к истинным.

Основываясь на информации полученной студентами при изучении дисциплины «Методы оптимизации», а так же источниках [3-5], для применения градиентных методов следует провести детальный анализ особенностей критерия (3).

Особенность 1 критерия оптимальности: Производственная функция (1) представляет собой произведение частично взаимозаменяемых параметров, следовательно, можно обеспечить почти одинаковое значение критерия при разных комбинациях параметров A, a, b.

Особенность 2 критерия оптимальности: отсутствие строгой выпуклости.

По результатам исследования градиентных алгоритмов, приведенных в первой части методических указаний [1], сделан вывод: «лобовое» использование градиентных методов для решения задачи идентификации параметров производственной функции Кобба-Дугласа нерезультативно, поскольку точность оценивания параметров неудовлетворительна.

Исключением можно считать алгоритм Ньютона, но только в случае успешно заданных начальных условий.

В [1] сформулированы причины неудовлетворительных результатов применения градиентных алгоритмов для идентификации параметров производственной функции Кобба-Дугласа:

Первая причина – разномасштабность оцениваемых параметров. Истинные значения A, a, b таковы: A = 20, a = 0.6, b = 0.35, причем различия в 2 порядка между A, с одной стороны, и (a, b), с другой стороны, объективно определяется свойствами функции Кобба-Дугласа. Такое различие является проявлением глубокого оврага в минимизируемой функции (как известно, для функций с глубоким оврагом не всегда обеспечивается сходимость к значениям аргументов минимизируемой функции).

Вторая причина – взаимозаменяемость параметров. Производственная функция представляет собой произведение: . Поэтому можно обеспечить почти одинаковое значение критерия при разных комбинациях параметров A, a, b.

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

Основные требования:

1)  Вторая часть лабораторной работы опирается на результаты, полученные при выполнении первой части описанной в [1].

2)  Желательно, чтобы студенты владели навыками работы в среде пакета программ для научных расчетов Mathcad. В этом случае выполнение работы будет облегчено, поскольку формулы в тексте записаны с учетом особенностей их реализации в этой среде [7].

Оборудование и программное обеспечение: персональный компьютер с процессором не ниже Intel Pentium 200 МГц.

Лабораторная работа может быть выполнена с использованием любого пакета прикладных программ для научных и инженерных расчетов (Mathcad версии не ниже 11-й, Matlab любой версии, Maple версии не ниже 4-й) на персональной ЭВМ с операционной системой, поддерживающей эти пакеты (Windows 95 и старше). Примеры и программы, содержащиеся в методических рекомендациях, реализованы в среде Mathcad v.11 или выше с операционной системой Windows XP. Поскольку все формулы и программы для рассмотренных примеров записаны в стиле Mathcad, рекомендуемая среда выполнения работы – Mathcad.

1 МЕТОДИКА ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

1.1 Использование масштабирования производственной функции Кобба-Дугласа

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

Цели масштабирования:

1)  снизить размерность задачи идентификации с трех до двух (т. е. идентифицировать только 2 параметра α и β);

2)  снизить разномасштабность искомых параметров;

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

Основная идея: применить градиентные методы (с постоянным шагом; с переменным шагом, не зависящим от формы минимизируемой функции; метод наискорейшего спуска; метод Ньютона) применительно к оценке двух параметров производственной функции Кобба-Дугласа: . Исключение параметра А1 достигается за счет использования масштабирования, а его оценка вычисляется после нахождения оценок α и β.

1.2 Описание процедуры масштабирования производственной функции Кобба-Дугласа

Генерация исходных данных приведена в [1].

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

Полученные значения:

Перейдем к безразмерным аргументам путем деления критерия на Kmax и Lmax :

При этом получим:

(4)

Из (4) видно. что максимальное значение производственной функции (соответствующей точке, в которой и ) равно:

Учитывая (4) получим:

(5)

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

.

Введем безразмерную величину:

(6)

и получим формулу, не содержащую параметра A1:

(7)

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

Формула (7) содержит только два параметра α и β, подлежащих идентификации по предварительно нормированным исходным данным. Если идентификация окажется успешной, третий параметр (А1) может быть просто вычислен по формуле:

(8)

Условие, которым должны удовлетворять исходные данные для получения несмещенных (относительно истинных значений) оценок идентифицируемых параметров α и β: в экспериментальных данных должны присутствовать отчетные данные от одного из предприятий, в котором и стоимость производственных фондов, и численность работающих соответствуют максимальным значениям. Иначе не получится точное соответствие между парой {Kmax, Lmax} и значением максимального объема выпуска продукции Zmax.

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

Для выполнения этого условия намеренно введем в исходные данные пару {Kmax, Lmax} для одного из элементов (любого) массивов K, L:

Таким образом, масштабирование и последующая идентификация проводятся по следующей схеме:

-  найти Kmax, Lmax, Zmax по доступным исходным данным;

-  ввести безразмерные переменные Km, Lm, Zm

-  идентифицировать параметры α и β с помощью соотношения (7);

-  рассчитать третий параметр А1 по формуле (8).

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

1.3 Задача идентификации с использованием масштабирования

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

Задача идентификации при этом будет сформулирована так: найти оценки и неизвестных параметров α и β производственной функции Кобба-Дугласа по результатам экспериментальных данных, представленных массивами из N+1 значений Kj, Lj, Zj, j=1,..,N.

Оценки должны доставлять минимум критерию (9):

(9)

Здесь Kmj и Lmj - масштабированные значения аргументов.

1.4 Основные соотношения, используемые в градиентных методах с использованием масштабирования

Перепишем критерий идентификации (9) как функцию искомых параметров и массива исходных данных, т. е. N+1 точек функции Кобба-Дугласа, соответствующих значениям ее аргументов, записанных в массивах Km, Lm, Zm (в формулах сделаны очевидные переобозначения: α2_exper вместо α_exper, β2_exper вместо β_exper), третий коэффициент, как видно из в формулы (8), равен единице: .

(10)

Исключение разномасштабности идентифицируемых параметров, достигнутое в результате масштабирования, должно проявиться в том, что будет ослаблен эффект овражности зависимости критерия (4) от искомых параметров α2_exper, β2_exper. Подтвердим это графически на рисунке 1, для этого рассчитаем вспомогательные данные:

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

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

Проведем соответствующие расчеты:

а) Расчет градиента критерия (10) в функции аргументов ,

Рис. 1. Поверхность критерия (10)

Используя возможности символьного процессора Mathcad, найдем частные производные критерия по каждому искомому параметру и сформируем формулу для нахождения градиента критерия:

б) Расчет вектора единичной длины, направленного по градиенту (для этого вектор-градиент нужно разделить на его длину):

Для того, чтобы в точке минимума, в которой градиент равен нулю, избежать деления на ноль подправим формулу:

в) Расчет симметричной 2*2 матрицы вторых производных критерия (10) . Элементами матрицы являются:

по каждому из искомых параметров :

С учетом симметричности:

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

1.5.1 Градиентный метод с постоянным шагом

Шаг 1. Задаемся значением шага поиска минимума функции (10):

Lambda_min :=1 Lambda_max :=50

m_L :=100 - масштабный коэффициент для расчета шага для данного алгоритма.

Для удобства можно использовать средства пакета Mathcad (подробнее смотри в приложении А), а именно слайдера для изменения длины шага в алгоритме поиска минимума с постоянным шагом (масштаб m_L:1):

Для примера принято значение

В этом случае длина шага алгоритма минимизации с постоянным шагом:

Шаг 2. Задаемся максимально возможным числом итераций алгоритма:

M5 :=100

Шаг 3. Задаем стартовые условия (начальные значения параметров , , в форме вектора:

Шаг 4. Вводим счетчик итерации алгоритма:

Шаг 5. Записываем алгоритм поиска минимума с постоянным шагом и рассчитываем его итерации:

Шаг 6. Вычисляем параметр A1_exper по формуле (8); предварительно, для снижения эффекта автоколебаний параметров вокруг точки минимума критерия, находим средние значения параметров α и β за две последние итерации:

После усреднения вычисляем параметр A1_exper по формуле (8):

Шаг 7: Анализируем качество работы алгоритма идентификации, т. е. траекторию движения параметров к их истинным значениям.

Для визуализации траектории движения используем следующие расчеты:

а) Для графика поверхности критерия:

Рис. 2. Процесс идентификации параметра α производственной функции Кобба-Дугласа. Непрерывной линией показано рассчитанное значение, прерывистой – истинное значение параметра α. Слева: процесс идентификации, справа - последние такты процесса (иллюстрируют автоколебания вблизи значения оцениваемого параметра, объективно свойственные градиентным алгоритмам с постоянным шагом).

Рис. 3. Процесс идентификации параметра β производственной функции Кобба-Дугласа. Непрерывной линией показано рассчитанное значение, прерывистой – истинное значение параметра β. Слева: процесс идентификации, справа - последние такты процесса.

б) Для траектории движения параметров α и β:

в) Для точки точного минимума критерия (соответствует истинным значениям параметров:

г) Для стартовой точки траектории движения к минимуму:

В результате получим:

Рис. 4. Траектория движения параметров α и β к точке минимума критерия идентификации (10). Слева: проекция траектории на координатную плоскость. Видны блуждания (циклические изменения аргументов) в окрестности минимума. Справа: пространственная траектория движения к минимуму (по поверхности критерия (10). Обозначения: кружком – точные значения параметров, символом квадрата - стартовые значения параметров.

1.5.2. Градиентный метод с переменным шагом, убывающим в ходе итераций независимо от формы минимизируемой функции

Шаг 1. Задаемся максимально возможным числом итераций алгоритма: M6 :=200

Шаг 2. Вводим счетчик итерации алгоритма:

Шаг 3. Задаемся законом уменьшения шага в зависимости от номера v итерации алгоритма поиска минимума функции (10).

В зависимости от варианта выбора переменной Step, которая может принимать значения 1 или 2 можно выбрать два варианта изменения шага:

1) закон убывания шага – гипербола при значении Step = 1;

2) закон убывания шага – экспонента при значении Step =2.

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

Рис. 5. График изменения (уменьшения) длины шага по мере итераций поиска минимума критерия (10)

Шаг 4. Задаем стартовые условия – начальные значения параметров , в форме вектора:

Шаг 5. Записываем алгоритм поиска минимума с переменным шагом и рассчитываем его итерации:

Шаг 6. Вычисляем параметр A1_exper по формуле (8); предварительно, для снижения эффекта автоколебаний параметров вокруг точки минимума критерия, находим средние значения параметров α и β за две последние итерации:

После усреднения вычисляем параметр A1_exper по формуле (8):

Шаг 7. Анализируем качество работы алгоритма идентификации, т. е. траекторию движения параметров к их истинным значениям.

Рис. 6. Процесс идентификации параметра α производственной функции Кобба-Дугласа. Непрерывной линией показано рассчитанное значение, прерывистой – истинное значение параметра α. Слева: процесс идентификации, справа – начальные (иллюстрируют уменьшение шага по мере итераций)

Рис. 7. Процесс идентификации параметра β производственной функции Кобба-Дугласа. Непрерывной линией показано рассчитанное значение, прерывистой – истинное значение параметра β. Слева: процесс идентификации, справа – начальные (иллюстрируют уменьшение шага по мере итераций)

Рис. 8. Траектория движения параметров α и β к точке минимума критерия идентификации (10). Слева: проекция траектории на координатную плоскость. Справа: пространственная траектория движения к минимуму. Обозначения: кружком – точные значения параметров, символом квадрата - стартовые значения параметров.

1.5.3 Метод наискорейшего спуска

Шаг 1. Задаемся максимально возможным числом итераций алгоритма: M7 :=100

Шаг 2. Вводим счетчик итерации алгоритма:

Шаг 3. Задаем стартовые условия (начальные значения параметров , в форме вектора:

Шаг 4. Записываем алгоритм и рассчитываем его итерации.

где (■)=()

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

Значения оценок на последнем такте итерации:

Шаг 5. Вычисляем параметр A1_exper по формуле (8):

Шаг 6. Анализируем качество работы алгоритма идентификации, т. е. траекторию движения параметров к их истинным значениям.

Рис. 9. Процесс идентификации параметра α (слева) и параметра β (справа) производственной функции Кобба-Дугласа. Непрерывной линией показаны рассчитанные значения, прерывистой – истинные значения параметров α и β.

Рис. 10. Траектория движения параметров α и β к точке минимума критерия идентификации (10). Слева: проекция траектории на координатную плоскость. Видны большие скачки алгоритма наискорейшего спуска. Иллюстрируется небольшое число шагов, необходимых для достижения минимума Справа: траектория движения к минимуму (по поверхности критерия (10). Обозначения: кружком – точные значения параметров, символом квадрата - стартовые значения параметров.

1.5.4 Метод Ньютона

Шаг 1. Задаемся максимально возможным числом итераций алгоритма: M8 :=100

Шаг 2. Вводим счетчик итерации алгоритма:

Шаг 3. Задаем стартовые условия (начальные значения параметров , в форме вектора:

Шаг 4. Записываем алгоритм Ньютона и рассчитываем его итерации.

где (■)=()

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

Значения оценок на последнем такте итерации:

Шаг 5. Вычисляем параметр A1_exper по формуле (8):

Шаг 6. Анализируем качество работы алгоритма идентификации, т. е. траекторию движения параметров к их истинным значениям.

Рис. 11. Процесс идентификации параметра α (слева) и параметра β (справа) производственной функции Кобба-Дугласа. Непрерывной линией показаны рассчитанные значения, прерывистой – истинные значения параметров α и β.

Рис. 12. Траектория движения параметров α и β к точке минимума критерия идентификации (10). Слева: проекция траектории на координатную плоскость. Справа: траектория движения к минимуму (по поверхности критерия (10). Обозначения: кружком – точные значения параметров, символом квадрата - стартовые значения параметров.

1.6 Оценка качества решения задачи идентификации параметров производственной функции Кобба-Дугласа градиентными методами с использованием масштабирования

1.6.1 Сводка результатов идентификации параметров

Истинные значения параметров функции Кобба-Дугласа:

Значения параметров функции Кобба-Дугласа определенные в результате применения градиентных методов с использованием масштабирования:

1)  алгоритм с постоянным шагом:

2)  алгоритм с переменным шагом:

3)  метод наискорейшего спуска:

4)  метод Ньютона:

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

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

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

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

-  алгоритм с постоянным шагом:

-  алгоритм с переменным шагом:

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

2)  Относительная величина амплитуды колебаний параметров производственной функции в окрестности экстремума (в процентах от истинных значений параметров):

-  алгоритм с постоянным шагом:

для параметра α:

для параметра β:

-  алгоритм с переменным шагом:

для параметра α:

для параметра β:

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

3)  Скорость сходимости к точке минимума по величине критерия (измеряется в итерациях):

-  алгоритм с постоянным шагом:

-  алгоритм с переменным шагом:

-  метод наискорейшего спуска:

-  метод Ньютона:

4)  Скорость сходимости к точке минимума по величине параметров производственной функции α, β:

-  алгоритм с постоянным шагом:

для параметра α:

для параметра β:

-  алгоритм с переменным шагом:

для параметра α:

для параметра β:

-  метод наискорейшего спуска:

для параметра α:

для параметра β:

-  метод Ньютона:

для параметра α:

для параметра β:

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

-  алгоритм с постоянным шагом:

для параметра A1:

для параметра α:

для параметра β:

-  алгоритм с переменным шагом:

для параметра A1:

для параметра α:

для параметра β:

-  метод наискорейшего спуска:

для параметра A1:

для параметра α:

для параметра β:

для критерия идентификации:

-  метод Ньютона:

для параметра A1:

для параметра α:

для параметра β:

для критерия идентификации:

1.6.3 Анализ применимости градиентных методов для идентификации параметров производственной функции Кобба-Дугласа с использованием масштабирования

Проанализировав результаты работы алгоритмов для оценки параметров производственной функции Кобба-Дугласа можно сделать следующие выводы:

1)  Применение алгоритм минимизации с постоянным шагом позволяет получить оценки близкие к истинным для всех параметров A1, α и β.

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

-  Достоинства алгоритма: высокая скорость сходимости, простота.

2)  Применение алгоритма минимизации с переменным шагом так же позволяет получить оценки близкие к истинным для всех параметров A1, α и β.

-  Недостатки алгоритма: трудности выбора законов уменьшения шага и параметров этих законов (эти недостатки объективно свойственны градиентному алгоритму с переменным шагом, не зависящим от формы минимизируемой функции).

-  Достоинства алгоритма: высокая скорость сходимости, простота.

3)  Алгоритм наискорейшего спуска и алгоритм Ньютона показали очень высокую результативность благодаря масштабированию производственной функции. Оценки, практически совпадающие с истинными значениями, удается получить для всех параметров A1, α и β производственной функции. Скорость сходимости велика (4-5 итераций).

-  Дополнительное достоинство алгоритмов - отсутствие произвола в выборе длины шага.

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

1.7 Общий вывод об эффективности использования масштабирования для решения задачи идентификации параметров производственной функции Кобба-Дугласа

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

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

Рис. 13. Два ракурса зависимости критерия идентификации от

оцениваемых параметров производственной функции Кобба-Дугласа

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

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

2.1 Исследование влияния настроечных параметров градиентных алгоритмов на качество идентификации

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

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

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

Исследование провести для обоих вариантов реализации: для прямого применения градиентных алгоритмов и для градиентных методов с использованием масштабирования.

Сделать выводы по полученным результатам.

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

-  Обосновать влияние начальных условий.

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

Сделать выводы по полученным результатам.

2.2 Исследование влияния на качество идентификации точности определения параметров и объема экспериментальных данных

Эксперимент 2.2.1: Оценить влияние числа предприятий N, о работе которых имеются отчетные сведения. При этом необходимо:

-  Оценить применимость градиентных методов при изменении величины N от 100 до 2000, с шагом равным 500.

-  Ответить на вопрос: возможно ли решить задачу при малом значении величины N например равной 50.

Исследование провести для обоих вариантов реализации: для прямого применения градиентных алгоритмов и для градиентных методов с использованием масштабирования.

Сделать выводы по полученным результатам.

Эксперимент 2.2.2: Оценить влияние диапазона разброса значений технико-экономических параметров (стоимости основных фондов Kmin, Kmax и численности работающих Lmin, Lmax). Изменяя максимальные значения Lmax от 100 до 1600 с шагом 500 и Kmax от 100 до 500 с шагом 100. При исследовании учесть влияние как отдельно каждого параметра, так и влияние двух параметров сразу.

Исследование провести для обоих вариантов реализации: для прямого применения градиентных алгоритмов и для градиентных методов с использованием масштабирования.

Сделать выводы по полученным результатам.

Эксперимент 2.2.3: Исследовать чувствительность алгоритмов к интенсивности искажений связи между объемами выпуска и технико-экономическими показателями (влияние неточности в исходных данных). Для этого необходимо:

-  Оценить применимость градиентных методов при изменении процента искажения отчетных данных о стоимости основных фондов предприятия sK от 0 до 25% с шагом 5%.

-  Оценить применимость градиентных методов при изменении процента искажения отчетных данных о стоимости основных фондов предприятия sL от 0 до 10% с шагом 1%.

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

-  Ответить на вопрос применимости алгоритмов при 5 и 10 процентном искажении отчетных данных об обоих показателях.

Исследование провести для обоих вариантов реализации: для прямого применения градиентных алгоритмов и для градиентных методов с использованием масштабирования.

Сделать выводы по полученным результатам.

Требования к содержанию отчета

Отчет может быть представлен на файле или в форме документа.

Обязательные элементы отчета:

1)  Результаты работы градиентных методов для обоих вариантов решения задачи.

2)  Анализ работоспособности каждого алгоритма.

3)  Сравнение качества работы градиентных методов.

4)  Выводы о применимости градиентных методов для решения задачи идентификации.

5)  Результаты экспериментов с соответствующими выводами (данный пункт выполняется для получения максимальной оценки)

Контрольные вопросы

1)  Что такое «производственная функция», какие аргументы она имеет?

2)  Какие параметры имеет производственная функция Кобба-Дугласа? Как трактуются эти параметры? Какие ограничения накладываются на параметры функции Кобба-Дугласа

3)  Что такое идентификация? Как формулируются задачи структурной и параметрической идентификации?

4)  Как ставится задача идентификации производственной функции Кобба-Дугласа, к какому классу задач идентификации она относится, почему?

5)  Какой критерий имеется у задачи идентификации производственной функции Кобба-Дугласа? Какие параметры подлежат определению?

6)  Что такое «выпуклая функция», зачем вводится требование выпуклости при использовании градиентных алгоритмов минимизации?

7)  Что такое «локальный экстремум», «глобальный экстремум»?

8)  Применимы ли градиентные алгоритмы для поиска глобального экстремума?

9)  Что такое «градиент» и «антиградиент»?

10)  Что такое «начальное приближение», при каких условиях градиентные алгоритмы сходятся к экстремуму независимо от выбора начального приближения?

11)  Что такое «овраг», имеет ли он место в рассматриваемой прикладной задаче?

12)  Почему поиск экстремума затрудняется при наличии оврага?

13)  Что такое «шаг единичной длины», для чего введено это понятие, как оно определяется и как используется в градиентных алгоритмах?

14)  Какие преимущества и недостатки имеются у алгоритма поиска экстремума с постоянным шагом?

15)  Какие преимущества и недостатки имеются у алгоритма поиска экстремума с переменным шагом, уменьшающимся в ходе итераций независимо от формы минимизируемой функции?

16)  Какие преимущества и недостатки имеются у алгоритма поиска экстремума методом наискорейшего спуска?

17)  Какие преимущества и недостатки имеются у алгоритма поиска экстремума методом Ньютона?

18)  Почему алгоритм Ньютона преодолевает овраги лучше, чем другие алгоритмы (с постоянным шагом, с переменным шагом, наискорейшего спуска)?

19)  Почему алгоритм Ньютона оказался неприменимым для решения задачи идентификации производственной функции Кобба-Дугласа без дополнительного преобразования этой задачи?

20)  Что такое «масштабирование», к каким эффектам привело использование масштабирования при решении задачи идентификации производственной функции Кобба-Дугласа?

21)  Что такое «сходимость алгоритма», каким образом она определяется?

22)  Почему при наличии оврага скорость сходимости к величине критерия идентификации превышает скорость сходимости к значениям идентифицируемых параметров?

Список литературы

1)  , Алейникова указания к лабораторной работе по дисциплине «Методы оптимизации». Использование градиентных методов оптимизации для решения задач оценки параметров математических моделей. Часть 1. / ВолгГТУ, Волгоград, 2010. – 42 с.

2)  , Об особенностях преподавания дисциплин математического цикла в рядовых технических вузах (на примере дисциплины «Методы оптимизации»).– Открытое образование. – 2008. - №5. – с. 8-15.

3)  Малыхин моделирование экономики: Учебно-практическое пособие. — М.: Изд-во УРАО, 1998. — с. 28-39.

4)  , , Зарубин оптимизации. – Учебник для студентов высших технических учебных заведений.– М.: Изд-во МГТУ им. , 200с.

5)  , , Федоров методов оптимизации. Режим доступа: http://www. *****.

6)  Введение в методы оптимизации. Основы и приложения нелинейного программирования. – М.: «Наука», 1977. – 343 с.

7)  , Панфилов Mathcad (первокурсникам, заочникам и не только…): Учеб. пособие / ВолгГТУ, Волгоград, 2006. – 179 с.

8)  Крушель поддержка учебной дисциплины «Методы оптимизации»: опыт обучения методам решения реальных оптимизационных задач.– Математика Компьютер Образование: сборник научных трудов, МОО "Женщины в науке и образовании". – М.– Ижевск, 2002, ч. 1. – с. 132-139.

ПРИЛОЖЕНИЕ

Описание программы поддержки скриптов для элементов управления вычислениями

П. 1 Элемент управления «Текстовое окно»

Имя элемента: TextBox. Осуществляет ввод информации текстовом виде. Для преобразования числовой формат можно использовать встроенную функцию str2num().Пример использования TextBox в лабораторной работе на этапе ввода исходных данных:

Параметры производственной функции Кобба-Дугласа:

Перевод из символьных значений в числовую форму:

В результате получаем:

П. 2 Элемент управления «Список»

Имя элемента: ListBox. Позволяет присвоить переменной значение, выбранное из списка. По умолчанию возвращает номер позиции выбранной из списка.

Пример использования ListBox в лабораторной работе для градиентного метода с переменным шагом, при задании закона уменьшения шага в зависимости от номера итерации:

Определим закон уменьшения шага:

Обработка результатов выбора:

Значение равное номеру выбранного пункта списка:

Значения параметров функций в зависимости от выбранного в списке вида функции:

Задание функции по выбранному закона убывания шага:

1 – Описание основных процедур списка для выбора закона убывания шага

Коды процедур	Комментарии и пояснения
ListBox. ResetContent()	Инициализация списка.
If ListBox. Count = 0 Then ListBox. AddString(«Закон убывания шага – гипербола») ListBox. AddString(«Закон убывания шага – экспонента») End If	Добавление в список необходимых строк, в нашем случае добавляются 2 строки определяющие вид закона убывания шага.
ListBox. CurSel = 0	Определение текущей позиции при запуске.
Sub ListBoxEvent_Exec(Inputs, Outputs)	Процедура, выполняемая после активного воздействия пользователя на окно списка.
Outputs(0).Value = ListBox. CurSel + 1	Позиция в списке после активного воздействия пользователя, возвращаемая переменная на единицу больше, так как нумерация позиций в списке начинается с нуля.
End Sub	Конец процедуры.
Sub ListBox_SelChanged()	Процедура, выполняемая после активного воздействия пользователя на окно списка.
ListBox. Recalculate()	Пересчет листа Mathcad после изменения объекта.
End Sub	Конец процедуры.
Sub ListBox_DblClick()	Процедура, выполняемая после двойного нажатия пользователем на окно списка.
ListBox. Recalculate()	Пересчет листа Mathcad после изменения объекта.
End Sub	Конец процедуры.

П. 3 Элемент управления «Полоса прокрутки»

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

2 – Описание процедур полосы прокрутки для изменения длинны шага в алгоритме поиска минимума с постоянным шагом

Коды процедур	Комментарии и пояснения
Dim MaxValue, MinValue	Объявляются локальные переменные MaxValue, MinValue.
Rem	Область объявления переменных, общих для всех процедур.
Sub Slider_Start()	Процедура выполняется при запуске файла.
Slider. MaxRange=MaxValue	Свойство объекта Slider. MaxRange получило максимальное значение как MaxValue.
Slider. MinRange=MinValue	Свойство объекта Slider. MinRange получило минимальное значение как MinValue.
Slider. Position=MinValue	Позиция объекта Slider получило минимальное значение как MinValue в результате определило начальное положение.
End Sub	Конец процедуры.
Sub SliderEvent_Start()	Процедура выполняется при начальном запуске.
MaxValue =WorkSheet. GetValue(“Lambda_c_max”)	К объекту WorkSheet(лист Mathcad) применить один из допустимых методов GetValue (чтение в скрипт с листа Mathcad) с параметром Lambda_c_max. Т. е. axValue приобретет значение, записанное на листе Mathcad Lambda_c_max.
MinValue =WorkSheet. GetValue(“Lambda_c_min”)	К объекту WorkSheet(лист Mathcad) применить один из допустимых методов GetValue (чтение в скрипт с листа Mathcad)с параметром Lambda_c_ min. Т. е. MaxValue приобретет значение, записанное на листе Mathcad Lambda_c min.
Slider. MaxRange=MaxValue	Свойство объекта Slider-MaxRange получило максимальное значение как MaxValue в результате определило положение крайней павой позиции Slider.
Slider. MinRange=MinValue	Свойство объекта Slider-MaxRange получило минимальное значение как MinValue в результате определило положение крайней левой позиции Slider.
Slider. Recalculate()	Пересчет листа Mathcad после выполнения объекта.
End Sub	Конец процедуры.
Sub SliderEvent_Exec(Inputs, Outputs)	Процедура, выполняемая после активного воздействия пользователя на слайдер. В результате ее выполнения переменной Outputs присваивается значение – соответствующее позиции слайдера.
Outputs(0).Value= Slider. Position	Объекту с присваивается значение Value, которое соответствует свойству позиции элемента Slider.

Продолжение таблицы П.2

Коды процедур	Комментарии и пояснения
Slider. Recalculate()	Пересчет листа Mathcad после выполнения объекта.
End Sub	Конец процедуры.
Sub Slider_ValueChanged()	Процедура, выполняемая после изменения пользователем значения объекта Slider.
Slider. Recalculate()	Пересчет листа Mathcad.
End Sub	Конец процедуры.

Рис. П.1. Элемент управления: «полоса прокрутки» и его сценарий

Составители:

Елена Георгиевна Крушель

Елена Анатольевна Алейникова

Использование градиентных методов оптимизации

для решения задач оценки параметров

математических моделей

Часть 2

Методические указания к лабораторной работе по дисциплине

«Методы оптимизации»

Под редакцией авторов

Темплан 2011 г., поз. № 56К

Подписано в печать 21.06.2011 г. Формат 60×84 1/16.

Бумага листовая. Печать офсетная.

Усл. печ. л. 2,09. Уч.-изд. л. 2,24.

Тираж 50 экз. Заказ №

Волгоградский государственный технический университет

г. Волгоград, пр. Ленина, 28, корп. 1.

Отпечатано в КТИ

, каб. 4.5