MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Математика\Optimization Toolbox

Список функций Optimization Toolbox

  В оглавление \ К следующему разделу \ К предыдущему разделу

FMINCON

Поиск минимума нелинейной задачи с ограничениями
при условии, что
где x, b, beq, lb и ub - векторы, A и Aeq - матрицы, и c(x) и ceq(x) есть функции, f(x) - функция, которая возвращает скаляр. f(x), c(x) и ceq(x) могут быть нелинейными функциями.

Синтаксис:

x = fmincon(fun,x0,A,b)
x = fmincon(fun,x0,A,b,Aeq,beq)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, ...)
[x,fval] = fmincon(...)
[x,fval,exitflag] = fmincon(...)
[x,fval,exitflag,output] = fmincon(...)
[x,fval,exitflag,output,lambda] = fmincon(...)
[x,fval,exitflag,output,lambda,grad] = fmincon(...)
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...)

Описание:

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

  • x = fmincon(fun,x0,A,b) начинает с точки x0 и находит минимум от х для функции представленной как fun при условии выполнения линейных неравенств A*x <= b. x0 может быть скаляром, вектором или матрицей.
  • x = fmincon(fun,x0,A,b,Aeq,beq) минимизирует fun при условии выполнения линейных равенств Aeq*x = beq, а так же A*x <= b. Устанавливается A=[] и b=[] в случае отсутствия неравенств.
  • x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних ограничений на конструируемые переменные х так, что решение всегда находится в диапазоне lb <= x <= ub. Устанавливается Aeq=[] and beq=[] в случае отсутствия равенств.
  • x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) подчиняет минимизацию определенных в nonlcon fmincon нелинейных неравенств c(x) или равенств ceq(x) такому оптимуму, что c(x) <= 0 и ceq(x) = 0. Устанавливается lb=[] и/илиr ub=[] в случае отсутствия ограничений.
  • x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) проводит минимизацию с оптимизационными параметрами, определенными в структурной опции.
  • x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,...) передает зависящие от типа задачи параметры непосредственно в функции fun и nonlcon. Передает пустые матрицы заменители для A, b, Aeq, beq, lb, ub, nonlcon и options в случае, если эти аргументы не являются необходимыми.
  • [x,fval] = fmincon(...) возвращает значение целевой функции fun как решение от х.
  • [x,fval,exitflag] = fmincon(...) возвращает значение exitflag, которое содержит описание выходных условий fmincon.
  • [x,fval,exitflag,output] = fmincon(...) возвращает структурный выход с информацией об оптимизации.
  • [x,fval,exitflag,output,lambda] = fmincon(...) возвращает структурную lambda с полями, содержащими множители Лагранжа в виде решения от х.
  • [x,fval,exitflag,output,lambda,grad] = fmincon(...) возвращает значение градиента от fun в виде решения от х.
  • [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(...) возвращает значения матрицы Гессе от fun в виде решения от х.

Аргументы:

Входные аргументы.
Таблица 4-1, Входные аргументы, содержит общее описание аргументов, передаваемых в fmincon. Данные подраздел "Аргументы" приводит функционально-специфические детали для fun, nonlcon и options:

fun
Подлежащая минимизации функция.

fun есть такая функция, которая принимает скаляр х и возвращает скаляр f, т.е. целевая функция от х. Функция fun может задаваться с помощью описателя функций
x = fmincon(@myfun,x0,A,b)
где myfun есть такая функция MATLAB, что
function f = myfun(x)
f = ...        % Вычисление функции в точке х

fun так же может быть и внутренним объектом
x = fmincon(inline('norm(x)^2'),x0,A,b);

Если градиент от fun может быть вычислен и опция options.GradObj равна 'on' посредством установки
options = optimset('GradObj','on')
то функция fun должна во втором выходном аргументе возвращать значение аргумента g, как вектора от х. Отметим, что посредством проверки значения nargout данная функция может обойти расчет g в случае когда fun вызывается только с одним выходным аргументом (случай, когда для оптимизационного алгоритма необходимо только значение f, а не g).

function [f,g] = myfun(x)
f = ...              % Вычисление функции в точке х
if nargout > 1   % fun вызывается с двумя выходными аргументами
    g = ...          % Расчет градиента как функции от х
end

Градиент состоит из частных производных от f в точке x. Т.е. i-ая компонента g есть частная производная от f по i-ой компоненте от х.

Если матрица Гессе к тому же может быть рассчитана и опция options.Hessian есть 'on', т.е. options = optimset('Hessian','on'), то функция fun должна возвращать значения матрицы Гессе Н в виде симметричной матрицы от х на месте третьего аргумента. Отметим, что посредством контроля значения nargout можно обойти расчет Н, тогда fun вызывается только с одним или двумя выходными аргументами (случай, когда для оптимизационного алгоритма необходимо только значение f и g, а не Н).

function [f,g,H] = myfun(x)
f = ...               % Расчет значения целевой функции от х
if nargout > 1    % fun вызывается с двумя выходными аргументами
g = ...               % Расчет градиента как функции от х
if nargout > 2
H = ...              % расчет матрицы Гессе от х
end

Матрица Гессе являются матрицей вторых частных производных от f в точке x. Т.е. (i,j)-ая компонента Н есть вторая частная производная от f по и .

по определению матрица Гессе является симметричной.

nonlcon
Функция, которая вычисляет нелинейные ограничения виде неравенств c(x) <= 0 и нелинейные ограничения виде равенств ceq(x) = 0.

Функция nonlcon принимает вектор х и возвращает два вектора c и ceq. Вектор с содержит нелинейные неравенства при расчете от х и ceq содержит нелинейные равенства при расчете от х. Функция nonlcon может быть определена как описатель функции.

x = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)
где mycon есть функция MATLAB, определенная как
function [c,ceq] = mycon(x)
c = ...      % вычисляет нелинейные ограничения в виде неравенств от х.
ceq = ...   % вычисляет нелинейные ограничения в виде равенств от х.

Если к тому же градиенты ограничений могут быть рассчитаны и опция options.GradConstr равна 'on' посредством
options = optimset('GradConstr','on')
то функция nonlcon так же должна возвращаться как третий и четвертый выходные аргументы, GC - как градиент от c(x) и GCeq как как градиент от ceq(x). Отметим, что посредством контроля значения nargout данная функция может обойти расчет GC и GCeq при этом nonlcon вызывается только с двумя выходными аргументами (в данном случае алгоритм оптимизации нуждается только в значениях c и ceq а не GC и GCeq).

function [c,ceq,GC,GCeq] = mycon(x)
c = ...            % Нелинейные неравенства от х
ceq = ...        % Нелинейные равенства от х
if nargout > 2 % Nonlcon вызываентся с 4 выходнымизначениями
GC = ...         % Градиенты неравенств
GCeq = ...     % Градиенты равенств
end

Если nonlcon возвращает вектор с с m компонентами и х имеет длину n, где n есть длина x0, то градиент GC c(x) есть матрица n х m, где GC(i,j) будут частные производные от c(j) по x(i) (т.е. j-ая колонка GC есть градиент j-го ограничения виде неравенств c(j)). Аналогично, если ceq имеет p компонент, то градиент GCeq ceq(x) есть матрица n х p, где GCeq(i,j) будут частные производные от ceq(j) по x(i) (т.е. j-ая колонка GCeq есть градиент j-го ограничения виде равенств ceq(j)).

options

Опции обеспечивают учет специфических деталей функции виде параметров options.

Выходные аргументы.
Таблица 4-2. "Выходные аргументы", содержат общее описание возвращаемых fmincon аргументов. В этом разделе приводятся общие специфические детали для величин exitflag, lambda и output:

exitflag

Описывает выходные условия.

  • > 0 Данная функция сходится к решению по х.
  • 0 Максимальное число оценки функции или итерации было превышено.
  • < 0 Функция не сходится к некому решению.
lambda

Структура, которая содержит множители Лагранжа при решении по х (разделенном по типам условий). Поле структуры:

  • lower Нижние границы lb
  • upper Верхние границы ub
  • ineqlin Линейные неравенства
  • eqlin Линейные равенства
  • ineqnonlin Нелинейные неравенства
  • eqnonlin Нелинейные равенства
output

Структура, которая содержит информацию об оптимизации. Поле структуры:

  • iterations Число выполненных итераций
  • funcCount Число оценок функции
  • algorithm Используемый алгоритм
  • cgiterations Число PCG итераций (только для крупно-масштабного (большой размерности) алгоритма)
  • stepsize Окончательно принятый размер шага (только для средне-масштабного алгоритма)
  • firstorderopt Измерение оптимальности первого порядка (только для крупно-масштабного алгоритма).

Для крупно-масштабных (большой размерности) задач с краевыми ограничениями оптимальностью первого порядка будет бесконечная норма v.*g, где v определяется как Ограничения Бокса и g -градиент. Для крупно масштабных задач с только линейными ограничениями оптимальностью первого порядка будет бесконечная норма проекции градиента (т.е. градиент проецируется на нуль-пространство Aeq).

Options

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

Для детальной информации смотри Таблицу 4-3, Параметры Опций Оптимизации

Мы начнем с описания опции LargeScale, поскольку она устанавливает преимущественное право какой алгоритм использовать. Это только преимущественное право, поскольку должны быть выполнены определенные условия для того, что бы можно было использовать крупно-масштабный алгоритм. Для fmincon необходимо задавать градиент (смотри выше описание fun) или иначе будет использоваться средне-масштабный алгоритм.

LargeScale В случае установки 'on' используется, если это возможно, крупно-масштабный (большой размерности) алгоритм. Для использования средне-масштабного алгоритма устанавливается 'off'.

Medium-Scale и Large-Scale Algorithms. Эти параметры используются как для средне-масштабного, так и крупно-масштабного алгоритмов:

Diagnostics Проводится печать диагностической информации о минимизируемой функции.
Display Уровень отображения. 'off' отображение не производится, 'iter' отображение проводится на каждой итерации, 'final' (принимается по умолчанию) отображение только конечной информации.
GradObj Градиент определенный пользователем целевой функции. Смотри выше описание функции fun как в ней определить градиент. Для того, что бы использовать крупно-масштабный метод необходимо задавать указанный градиент. Это необязательно для средне-масштабного метода.
MaxFunEvals Максимально число допустимых расчетов функции.
MaxIter Максимально число допустимых итераций.
TolFun Конечное допустимое отклонение по значению функции.
TolCon Конечное допустимое отклонение по нарушению условий ограничения.
TolX Конечное допустимое отклонение по значению х.

Large-Scale Algorithm Only. Эти параметры используются только для крупно-масштабного алгоритма.

Hessian В случае установки 'on' в fmincon используется заданная пользователем матрица Гессе (задается в fun) или информация о матрице Гессе (при использовании HessMult) для целевой функции. В случае установки 'off' в fmincon используется матрице Гессе с расчетом с помощью конечных разностей.
HessMult Указатель функции для умножения на матрицу Гессе. Для типа крупно-масштабных задач, эта функция рассчитывает произведение матрицы Гессе H*Y без реального формирования Н. Эта функция имеет форму
W = hmfun(Hinfo,Y,p1,p2,...)
где Hinfo и дополнительные параметры p1,p2,...включают в себя матрицы для расчета H*Y. Первый аргумент должен быть тот же самый, как и третий аргумент, возвращаемый целевой функцией fun.
[f,g,Hinfo] = fun(x,p1,p2,...)
параметры p1,p2,... являются теми же самыми параметрами, что передаются в fmincon (и в fun).
fmincon(fun,...,options,p1,p2,...)
Y есть матрица с тем же самым числом строк как и размерности данной задачи. W = H*Y, хотя H явно не формируется. fmincon использует Hinfo для расчета предварительных условий.

В качестве примера смотри Нелинейную Оптимизацию с Компактной, но Структурированной Матрицей Гессе и Ограничениями Типа Равенств.

HessPattern Разреженный образ матрицы Гессе для конечных разностей. Если не является разумным в fun рассчитывать разреженную матрицу Гессе Н, то в fmincon крупно-масштабный метод может аппроксимировать Н через разреженные конечные разности (для градиентов) при условии, что структура разреженности для Н, т.е. местоположения nonzeros, задаются как определенные значения для HessPattern. В наихудшем случае, когда такая структура неизвестна, можно задать HessPattern, что является плотной матрицей, а полная конечноразностная аппроксимация будет рассчитываться на каждой итерации (что принимается по умолчанию). Это может быть очень дорогостоящим для больших задач, поэтому стоит затратить усилия на определение структуры разреженности.
MaxPCGIter Максимальное число PCG (предварительно сопряженный градиент) итераций (Смотри ниже раздел Алгоритм).
PrecondBandWidth Верхняя полоса предварительной обработки для PCG. По умолчанию используется диагональная начальная подготовка (верхняя полоса из 0). Для некоторых задач увеличение полосы снижает число итераций PCG.
TolPCG Конечное допустимое число итераций PCG.
TypicalX Типичные значения х.

Только для средне-масштабного алгоритма. Эти параметры используются только для средне-масштабного алгоритма.

DerivativeCheck Сравнение вводимых пользователем производных (градиенты цели или ограничивающих условий) с конечноразностными производными.
DiffMaxChange Максимальное изменение в переменных для конечно-разностных градиентов.
DiffMinChange Минимальное изменение в переменных для конечно-разностных градиентов.

Примеры:

Найти значение х, которые минимизируют , начиная с точки x = [10; 10; 10] и с учетом ограничений

Прежде всего, запишем М-файл, который возвращает скалярное значение f как функции от х.

function f = myfun(x)
f = -x(1) * x(2) * x(3);

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

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

......

Далее зададим начальную точку и запустим программу оптимизации.

x0 = [10; 10; 10]; % начальное предположение о решении
[x,fval] = fmincon(@myfun,x0,A,b)

После 66 расчетов функции решение будет

x =
     24.0000
     12.0000
     12.0000

где значение функции будет

fval =
     -3.4560e+03

и оценка ограничений в виде линейных неравенств <= 0 дает

A*x-b=
     -72
     0

Примечания:

Крупно-масштабная оптимизация. Для того, что бы использовать крупно-масштабный метод в fun необходимо задать градиент (а в опции options.GradObj установить 'on'). Производится предупреждение (warning) при условии, что градиент не задан, а опция options.LargeScale не равна 'off'. Допускается, что в функции fmincon значение g(x) будет приближенным градиентом, но, однако, эта опция не рекомендуется, поскольку большинство оптимизационных кодов значительно более грубое, чем истинные значения используемых градиентов.

Крупно-масштабный метод для fmincon наиболее эффективен в том случае, когда также рассчитывается и матрица вторых производных, т.е. матрице Гессе H(x). Однако оценка истинных значений матрицы Гессе не требуется. Например, если можно ввести структуру разреженности матрицы Гессе (используя определенный параметр опции HessPattern), то тогда fmincon рассчитывает разреженную конечноразностную аппроксимацию для H(x).

Если х0 не является строго вычисляемым, то fmincon выбирает новую (центрированную) строго вычисляемую начальную точку.

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

Следует отметить несколько аспектов относительно линейной условной оптимизации.

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

Средне-масштабная оптимизация. По-видимому, если явно определить равенства с помощью Aeq и beq, то будут более лучшие численные результаты, по сравнению с случаем неявного определения с помощью lb и ub.

Если имеются ограничения в виде равенств, а также определяются и удаляются зависимые равенства в квадратичной подзадаче, то печатается 'dependent' в заголовке Процедуры (когда запрашивается вывод опции options.Display = 'iter'). Зависимые равенства удаляются только тогда, когда эти равенства являются непротиворечивыми, при этом задача является недопустимой и в заголовке Процедуры печатается 'infeasible'.

Алгоритм:

Крупно-масштабная оптимизация. По умолчанию fmincon выберет крупно-масштабный алгоритм, если пользователь введет градиент в fun (и установит опцию GradObj как 'on') и если только существуют верхний и нижний ограничения, а также ограничения в виде линейных равенств. Данный алгоритм является реализацией метода доверительных подпространств и основан на методе внутренних отражений Ньютона, описанного в [1], [2]. Каждая итерация включает в себя приближенное решение крупной линейной системы с помощью метода предварительно сопряженных градиентов(PCG). Смотри описания доверительной области и метода предварительно сопряженных градиентов в разделе "Крупно-Масштабные Алгоритмы".

Средне-масштабная оптимизация. fmincon использует метод Последовательного Квадратичного Программирования (SQP). В данном методе на каждой итерации решается подзадача Квадратичного Программирования (QP). Вид матрицы Гессе для функции Лагранжа обновляется на каждой итерации с помощью формулы BFGS (смотри fminunc, литература [7], [8]).

Линейный поиск проводится с помощью функции полезности аналогично тому, как было предложено [4], [5], и [6].

Подзадача QP решается с помощью постоянной активной стратегии, аналогично тому, как было предложено в [3]. Полное описание алгоритма можно найти в разделе Условная Оптимизация в "Введении в Алгоритмы".

Более подробно об используемом алгоритме смотри Реализация SQP в "Введении в Алгоритмы".

Диагностика:

Крупно-масштабная оптимизация. Программа для крупно-масштабной задачи не допускает равенства верхней и нижней границ. Например, если

lb(2) = = ub(2), то fmincon выдает ошибку

Равенство верхней и нижней границ не допустимо для крупно-масштабного метода

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

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

Ограничения:

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

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

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

Крупно-масштабная оптимизация. Для того, что бы использовать крупно-масштабный алгоритм, пользователь должен в fun задать градиент (а также установить опцию GradObj как 'on'), а так же можно задавать только верхнюю и нижнюю границы, или только должны быть ограничения в виде линейных равенств, а в Aeq число строк не может быть больше числа колонок. Aeq является типичным примером разреженности. Относительно большей информации о постановке задачи, области применения и задания исходных данных смотри таблицу 1-4, Область Определения и Требования к Крупно-Масштабным Задачам.

В настоящее время, если в fun аналитически задан градиент, то для сравнения аналитического градиента с его конечно-разностным значением в крупно-масштабном методе нельзя использовать параметр опции DerivativeCheck. Вместо этого, для контроля производной следует использовать средне-масштабный метод с установкой опционного параметра MaxIter как 0 итераций. Затем запустить задачу с крупно-масштабным методом.

Сопутствующие функции: @ (function_handle), fminbnd, fminsearch, fminunc, optimset

Литература:

  1. Coleman, T.F. and Y. Li, "An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds" SIAM Journal on Optimization, Vol. 6, pp. 418-445, 1996.
  2. Coleman, T.F. and Y. Li, "On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds" Mathematical Programming, Vol. 67, Number 2, pp. 189-224, 1994.
  3. Gill, P.E., W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, 1981.
  4. Han, S.P., "A Globally Convergent Method for Nonlinear Programming" Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.
  5. Powell, M.J.D., "A Fast Algorithm for Nonlineary Constrained Optimization Calculations" Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.
  6. Powell, M.J.D., "The Convergence of Variable Metric Methods For Nonlinearly Constrained Optimization Calculations" Nonlinear Programming 3, (O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, eds.) Academic Press, 1978.

  В оглавление \ К следующему разделу \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика