Оптимизация в среде MATLAB
..pdfПример 33.
Найти решение задачи наименьших квадратов с ограничениями при следующих данных:
5 3 |
2 |
|
|
15 |
|
|||
|
|
|
|
|
|
|
|
|
C 6 |
9 |
1 |
, |
d |
9 |
|
, |
|
|
8 |
3 |
|
|
|
|
|
|
4 |
|
|
|
4 |
|
|
||
10 5 7 |
|
|
|
11 |
|
|||
x1 – 0,5x2 + 3x3 9, |
|
|
|
|||||
–2x1 + 6x2 + 2,3x3 5,5, |
|
|
||||||
–0,5 xj 2, |
j = 1, 2, 3. |
|
|
Для решения задачи записываем все входные аргументы и вызы-
ваем функцию lsqlin:
>> C=[5 -3 2;6 9 -1;4 8 3;10 5 -7];...
d=[15;9;4;11]; A=[1 0.5 3;-2 6 2.3];b=[9;5.5];...
lb=-0.5*ones(3,1);ub=2*ones(3.1);...
[x,resnorm,residual,exitflag,output,lambda] = lsqlin(C,d,A,b,[],[],lb,ub)
Optimization terminated.
x=
2.0000
-0.5000 0.8095 resnorm = 15.4643
residual = /остатки по четырем равенствам (Cx – d)
-1.8810 -2.3095 2.4286 0.8333
exitflag = 1
output =
iterations: 3 constrviolation: 0
algorithm: 'medium-scale: active-set' firstorderopt: []
171
cgiterations: []
message: 'Optimization terminated.' >> lambda.lower
0
8.4524
0
>> lambda.upper
5.2143
0
0
>> lambda.ineqlin
0
0
Как следует из полученного отчета, решение найдено за три основные итерации алгоритмом Medium Scale: active-set без использования PCG. Значения lambda показывают, что решение лежит на одной нижней и одной верхней границе и внутри области, задаваемой линейными неравенствами.
Лабораторная работа № 8 Решение уравнений и метод наименьших квадратов
Задания:
1. Ознакомиться с назначением и синтаксисом функций fsolve, lsqnonlin, lsqcurvefit, lsqnonneg и lsqlin.
2. Найти все корни и стационарные точки функции f (x) sin x 0,5 x 0,5 на интервале 0 x 3 .
3. Решить систему
5 |
2 |
|
X +0,5X×X – 0,1X×X×X= |
4 |
. |
1 |
|
4. Найти минимум функции
4
F(x) (x1t x2 x1x20,5t te x1x2 )2 .
t0
5.Пусть выход y некоторого объекта связан с входом x зависимостью
y x xe x x
172
в диапазоне 0 x 6. Задать ряд значений x (24 или 30 точек) и при значениях параметров α = –0,1, = –0,2, = 2 получить соответствующий ряд y. К этому ряду добавить помехи, используя случайную величину с равномерным распределением в диапазоне от –0,2 до 0,2 и нулевым математическим ожиданием, для чего использовать функцию rand. По данным выхода с помехами y и входа x восстановить значе-
ния параметров α, и двумя алгоритмами, сравнить результаты и представить их графически.
173
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
По MATLAB
1.Дьяконов В.П. MATLAB 7.*/R2006/R2007: самоучитель. – М.:
ДМК Пресс, 2008.
2.Дьяконов В.П. MATLAB 6.5 SP1/7+Simulink 5/6 в математике и моделировании. – М.: СОЛОН-Пресс, 2005.
По методам оптимизации
3.Аоки М. Введение в методы оптимизации: пер. с англ. – М.:
Наука, 1977.
4.Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации: учебник для вузов / под ред. В.С. Зарубина. – 2-е изд., стер. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2003.
5.Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы: пер. с англ. / под ред. Д.Б. Юдина. – М.: Мир, 1982.
6.Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учеб. пособие для вузов / под ред. В.М. Курейчика. – 2-е изд., испр. и доп. – М.: Физматлит, 2006.
7.Гольдштейн А.Л. Исследование операций: многокритериальные задачи: конспект лекций. – Пермь: Изд-во Перм. гос. техн. ун-та, 1995.
8.Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. – М.: Наука, 1991.
9.Карманов В.Г. Математическое программирование: учеб. пособие для вузов. – 6-е изд., испр. – М.: Физматлит, 2008.
10.Корнеенко В.П. Методы оптимизации: учебник. – М.: Высш.
шк., 2007.
11.Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука, 1982.
12.Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: в 2 кн.: пер. с англ. – М.: Мир, 1986.
13.Соболь Б.В., Месхи Б.Ч., Каныгин Г.И. Методы оптимизации: практикум. – Ростов-н/Д: Феникс, 2009.
14.Федунец Н.И., Черников Ю.Г. Методы оптимизации: учеб. пособие для вузов. – М.: Изд-во МГГУ, 2009.
174
ПРИЛОЖЕНИЕ 1
Параметры fminunc
Параметры, общие для Large Scale и Medium Scale
Параметр |
|
Описание |
|
|
Значение по |
|
|
|
умолчанию |
||
|
|
|
|
|
|
|
|
|
|||
Display |
Задает уровень выводимой информации: |
'final' |
|||
|
'off'– нет вывода, 'final' |
– только |
|
||
|
итоговый отчет, |
'iter'– по каждой ите- |
|
||
|
рации, 'iter-detailed' – детальный, |
|
|||
|
'notify' – вывод только о несходимости, |
|
|||
|
'notify-detailed', 'final-detailed' |
|
|||
|
|
|
|||
DerivativeCheck |
Сравнение аналитического градиента с ко- |
'off' |
|||
|
нечно-разностным: 'off', 'on' |
|
|
||
|
|
|
|
|
|
Diagnostics |
Диагностическая информация |
о |
целевой |
'off' |
|
|
функции: 'off', 'on' |
|
|
|
|
|
|
|
|
|
|
DiffMaxChange |
Максимальное |
приращение |
переменных |
0.1 |
|
|
при конечно-разностном вычислении гра- |
|
|||
|
диента |
|
|
|
|
|
|
|
|
|
|
DiffMinChange |
Минимальное |
приращение |
переменных |
1e-8 |
|
|
при конечно-разностном вычислении гра- |
|
|||
|
диента |
|
|
|
|
|
|
|
|
|
|
FunValCheck |
Контроль типа |
возвращаемого |
значения |
'off' |
|
|
целевой функции: 'off', 'on' |
|
|
||
|
|
|
|||
GradObj |
Использование аналитического градиента: |
'off' |
|||
|
'on', 'off' – конечно-разностный метод |
|
|||
|
|
|
|||
LargeScale |
Тип алгоритма: 'on' – Large Scale, |
'on' |
|||
|
'off' – Medium Scale |
|
|
|
|
|
|
|
|||
MaxFunEvals |
Максимальное число вычислений функции |
100 × число |
|||
|
|
|
|
|
переменных |
|
|
|
|
|
|
175
MaxIter |
|
Максимальное число итераций |
400 |
|
|
|
|
OutputFcn |
Имя пользовательской функции вывода, |
[] |
|
|
|
вызываемой на каждой итерации |
|
|
|
|
|
PlotFcns |
Имя функции вывода графики: |
[] |
|
|
|
@optimplotx, @optimplotfunccount, |
|
|
|
@optimplotfval, |
|
|
|
@optimplotstepsize, |
|
|
|
@optimplotfirstorderopt, |
|
|
|
функция пользователя |
|
|
|
|
|
, |
X |
Конечное допустимое значение функции и x |
1e-6 |
TolFun |
Tol |
|
|
TypicalX |
Вектор типовых значений x. Для масштаби- |
Все = 1 |
|
|
|
рования при конечно-разностном способе |
|
|
|
|
|
Параметры только для Medium Scale
Параметр |
|
Описание |
|
|
Значение по |
|
|
|
умолчанию |
||
|
|
|
|
|
|
|
|
|
|
|
|
FinDiffType |
Способ |
вычисления конечной |
разности |
'forward' |
|
для градиентов: 'forward' |
(сдвигом |
|
|||
|
|
||||
|
вперед), 'central' |
|
|
|
|
HessUpdate |
Метод выбора направления поиска в ква- |
'bfgs' |
|||
|
зиньютоновском алгоритме: 'bfgs', |
|
|||
|
'dfp', |
'steepdesc' |
|
|
|
|
|
|
|||
InitialHessMatrix |
Задание начальной матрицы (только при |
___ |
|||
|
установке InitialHessType в 'user- |
|
|||
|
supplied'): положительный скаляр (все |
|
|||
|
элементы), положительный вектор (диаго- |
|
|||
|
нальная матрица со значениями вектора) |
|
|||
|
|
|
|||
InitialHessType |
Тип начальной матрицы в квазиньюто- |
'scaled- |
|||
|
новском |
методе: |
'identity', |
identity' |
|
|
'scaled-identity', пользователя |
|
|||
|
|
|
|
|
|
176
Параметры только для Large Scale
Параметр |
Описание |
Значение по |
||
|
|
|
умолчанию |
|
|
|
|
||
Hessian |
Способ вычисления гессиана: 'on' – |
'off' |
||
|
аналитически, 'off' – конечными раз- |
|
||
|
ностями |
|
|
|
HessMult |
Задает функцию, вычисляющую произ- |
___ |
||
ведение матрицы Гессе на вектор (при |
|
|||
|
|
|||
|
установке Hessian -'on') |
|
||
HessPattern |
Образец разреженности гессиана, исполь- |
Плотная |
||
зуемый для аппроксимации матрицы раз- |
матрица |
|||
|
||||
|
реженными конечными разностями для |
|
||
|
большеразмерных задач. При неизвестной |
|
||
|
структуре HessPattern устанавливают |
|
||
|
на плотную матрицу с использованием |
|
||
|
полных конечных разностей |
|
||
MaxPCGIter |
Максимальное число |
итераций метода |
Число пере- |
|
предобусловленного |
сопряженного гра- |
менных/2 |
||
|
||||
|
диента (PCG) |
|
|
|
PrecondBandWidth |
Параметр PCG. При установке в Inf ско- |
Диагональная |
||
|
рее используется прямая факторизация, |
предобуслов- |
||
|
чем CG |
|
ленность |
|
TolPCG |
Конечная допустимая величина для ите- |
0.1 |
||
рации PCG (в критерии окончания) |
|
|||
|
|
|
|
|
|
ПРИЛОЖЕНИЕ 2 |
|
|
|
|
|
Параметры fmincon |
|
|
Параметры, общие для всех алгоритмов |
|
|||
|
|
|
|
|
|
Параметр |
|
Описание |
|
Значение по |
|
|
|
умолчанию |
|||
|
|
|
|
|
|
|
|
|
|
|
|
Algorithm |
|
Выбор алгоритма: |
|
|
'trust- |
|
|
'trust-region-reflective', 'active- |
region- |
||
|
|
, |
, |
'sqp' |
reflec- |
|
|
set' 'interior-point' |
|
tive' |
|
|
|
|
|
|
177
DerivativeCheck, |
То же, что для fminunc (прил. 1) |
|
Прил. 1 |
||
Diagnostics, |
|
|
|
|
|
DiffMaxChange, |
|
|
|
|
|
DiffMinChange, |
|
|
|
|
|
Display, |
FinDif- |
|
|
|
|
fType, |
FunVal- |
|
|
|
|
Check, |
GradObj, |
|
|
|
|
MaxFunEvals, |
|
|
|
|
|
MaxIter, Output- |
|
|
|
|
|
Fcn, |
TolFun, |
|
|
|
|
TolX, TypicalX |
|
|
|
|
|
GradConstr |
'on' – использовать аналитический гради- |
'off' |
|||
|
|
ент функций нелинейных ограничений, |
|
||
|
|
'off'– вычислениечерезконечныеразности |
|
||
PlotFcns |
|
Задает функцию графики: |
|
[] |
|
|
|
@optimplotx, @optimplotfunccount, |
|
||
|
|
@optimplotfval, |
@optim- |
|
|
|
|
@optimplotconstrviolation, |
|
||
|
|
plotstepsize, |
@optimplotfirst- |
|
|
|
|
orderopt |
|
|
|
TolCon |
|
Допустимое нарушение ограничения |
1e-6 |
||
UseParallel |
– вычисление градиентов в па- |
'never' |
|||
|
|
'always' |
|
|
|
|
|
раллель, 'never' – нет |
|
|
|
|
Параметры для Trust-Region-Reflective |
|
|||
|
|
|
|
|
|
Параметр |
|
Описание |
|
Значение по |
|
|
|
умолчанию |
|||
|
|
|
|
|
|
|
|
|
|
|
|
Hessian, |
HessMult |
То же, что для Large Scale |
fminunc |
Прил. 1 |
|
HessPattern, Max- |
(прил. 1) |
|
|
|
|
PCGIter,Precond- |
|
|
|
|
|
BandWidth, TolPCG |
|
|
|
|
|
|
|
Параметры для Active-Set |
|
|
|
|
|
|
|
|
|
Параметр |
|
Описание |
|
Значение по |
|
|
|
умолчанию |
|||
|
|
|
|
|
|
|
|
|
|||
MaxSQPIter |
Максимальное число SQP-итераций |
10×число |
|||
|
|
|
|
|
переменных |
178
RelLineSrchBnd |
Коэффициент в ограничении длины шага |
[] |
|
поиска, так что общее смещение по x ог- |
|
|
раничивается |
|
|
| x(i)| ≤relLineSrchBnd·max(|x(i)|.|typicalx(i)|) |
|
RelLineSrchBnd- |
Число итераций, на которых граница, оп- |
1 |
Duration |
ределяемая RelLineSrchBnd, будет ак- |
|
|
тивной |
|
TolConSQP |
Допустимое нарушение ограничений во |
1e-6 |
|
внутренних итерациях SQP |
|
Параметры для Interior-Point
Параметр |
|
|
Описание |
|
|
|
|
|
|||
AlwaysHonorConst- |
Установка 'bounds' |
обеспечива- |
|||
raints |
ет выполнение ограничений на ка- |
||||
|
ждой итерации, 'none' – требо- |
||||
|
вание снимается |
|
|||
HessFcn |
Задает функцию вычисления гес- |
||||
|
сиана, когда параметр Hessian ра- |
||||
|
вен 'user-supplied' |
||||
Hessian |
Способ |
|
вычисления |
гессиана: |
|
|
'bfgs', 'fin-diff-grads' (ко- |
||||
|
нечными |
разностями), |
'lbfgs', |
||
|
{'lbfgs',Positive |
Integer} |
|||
|
(оба |
bfgs |
с ограничением на |
||
|
число |
учитываемых |
прошедших |
||
|
итераций),'user-supplied' (по |
||||
|
функции пользователя) |
|
|||
HessMult |
Управляет |
функцией пользователя |
|||
|
при установке |
Hessian в 'user- |
|||
|
supplied' |
|
|
||
InitBarrierParam |
Начальное значение барьера |
||||
InitTrustRegion- |
Начальный радиус доверительной |
||||
Radius |
области |
|
|
|
|
MaxProjCGIter |
Допустимое число внутренних ите- |
||||
|
раций метода проектируемых со- |
||||
|
пряженных градиентов |
|
|||
|
|
|
|
|
|
Значение по умолчанию
'bounds'
____
'bfgs'
___
0.1
число переменных 2 × (число переменных минус число равенств)
179
ObjectiveLimit |
|
Если значение цлевой функции ста- |
|
-1e20 |
|||||
|
|
новится меньше ObjectiveLimit, |
|
|
|||||
|
|
итерации останавливаются – задача |
|
|
|||||
|
|
неограничена |
|
|
|
|
|
|
|
ScaleProblem |
|
Установка в 'obj-and-constr' |
'obj-and- |
||||||
|
|
приводит к нормализации всех ог- |
constr' |
||||||
|
|
раничений |
и |
целевой |
функции, |
|
|
||
|
|
в 'none' – |
нормализация отклю- |
|
|
||||
|
|
чена |
|
|
|
|
|
|
|
SubproblemAlgorit |
Вычисление |
шага |
итерации |
при |
|
'ldl- |
|||
hm |
|
'ldl-factorization' быстрее, |
factorization' |
||||||
|
|
чем при 'cg' |
(сопряженный гра- |
|
|
||||
|
|
диент), но 'cg' может быть быст- |
|
|
|||||
|
|
рее при больших задачах с плотным |
|
|
|||||
|
|
гессианом |
|
|
|
|
|
|
|
TolProjCG |
|
Относительная |
допустимость |
для |
0.01 |
||||
|
|
внутренних |
итераций |
алгоритма |
|
|
|||
|
|
проекции сопряженного градиента |
|
|
|||||
TolProjCGAbs |
|
Абсолютная |
|
допустимость |
для |
|
1e-10 |
||
|
|
внутренних итераций PCG |
|
|
|
|
|||
|
|
Параметры для SQP |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
Параметр |
|
|
|
Описание |
|
|
|
Значение по |
|
|
|
|
|
|
|
умолчанию |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
ObjectiveLimit |
Так же, как для Interior-Point |
|
|
– |
|||||
ScaleProblem |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ПРИЛОЖЕНИЕ 3 |
|
|
|
Параметры GlobalSearch и MultiStart |
|||||||
Параметры, общие для GlobalSearch и MultiStart |
|||||||||
|
|
|
|
|
|
|
|
|
|
Параметр |
|
|
|
Описание |
|
|
|
Значение по |
|
|
|
|
|
|
|
умолчанию |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Display |
Задает уровень |
выводимой информации |
'final' |
||||||
|
об итерациях: 'off' |
– нет вывода, |
'fi- |
|
|||||
|
nal' – только итоговый отчет, 'iter' – |
|
|||||||
|
по каждой глобальной итерации |
|
|
|
180