Исследование методов решения задач условной минимизации

Цель работы

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

Варианты

1. .

; ; ;

2. ; .

; .

3. ; .

; ; .

4. ; .

; ; .

5. ;

; ; .

6. ; .

; ; .

7. ; .

; ;

8. ;

; ; .

9. ; .

;

10. ; .

; ;

11. ; .

; ;

12. ; .

; ; ;

13. , ,

, , , , .

14. , ,

, , , , .

15. , ,

, , , , , .

16. , ,

, , , , .

17. , ,

, ,

, .

18. , ,

, ,

, .

19. , ,

, ,

, .

Задание

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

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

2. Сравнить эффективность алгоритмов при использовании численного и аналитического расчета градиента целевой функции.

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

4. Определить характер поведения алгоритма при нахождении решения.

Методические указания к выполнению работы

Для проведения условной минимизации может быть использована следующая стандартная функция Matlab – fmincon.

Синтаксис вызова функции:

[x, fval, exitflag, output, lambda]=fmincon(@fun, x0, A, b, Aeq, beq, lb, ub, @fcon, options)

где x – финальное значение аргумента функции, fval – значение функции в точке х, exitflag – указатель состояния алгоритма для решаемой задачи в точке х, output – суммарная информация о работе алгоритма, lambda – множители Лагранжа, fun – целевая функция, x0 – точка начального приближения, b и beq – векторы правой части линейного неравенства и равенства, lb и ub – верхняя и нижняя граница поиска решений, AиAeq– матрицы левой части линейного неравенства, fcon – функция нелинейных равенств и неравенств, options – параметры алгоритма. Отсутствующие параметры заменяются на символ пустого множества [].

Функция формируется в отдельном m-файле, структура которого должна иметь следующий вид:

function [f] = fun(x)

%тело функции

end

При этом имя m-файла должно совпадать с названием функции, в данном случае fun.

Функция нелинейных равенств и неравенств записывается в отдельном m-файле и имеет следующую структуру:

function [c, ceq]=fcon(x)

c=%вектор-столбец неравенств, причем c< 0

ceq=%вектор-столбец равенств

end

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

options = optimset('Algorithm', 'trust-region-reflective', 'GradObj', 'on', 'Display', 'iter', 'TolX', 1e-6, 'TolFun', 1e-12, 'TolCon', 1e-6);

где Algorithm – указатель на используемый алгоритм, GradObj – флаг использования аналитически рассчитанного градиента, Display – параметр, отвечающий за вывод на экран информации об итерациях; iter – флаг о необходимости вывода на экран информации обо всех итерациях; TolX – предельный шаг изменения аргумента функции (в приведенном выше примере параметру 'TolX' присвоено значение 1e-6); TolFun – предельный шаг приращения функции; 'TolCon' – Конечное допустимое отклонение по нарушению условий ограничения.

Параметр Algorithm может принимать четыре различных значения:

· trust-region-reflective (Метод доверительных областей)

· active-set (Активный набор)

· sqp (метод квадратичного программирования)

· interior-point (метод с использованием барьерной функций)

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

function [f g] = fun(x)

%целевая функция

if nargout> 1

% запись градиента в виде:

%g(1) =...;

%g(2) =...;

%...

end

end

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

global xiter;

xiter = [];

и в отдельном m-файле с именем outfun поместить следующий код:

function stop=outfun(x, optimValues, state)

global xiter;

xiter = [xiter x];

stop = false;

end

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

Рекомендуемая литература