Содержание
Агиевич
В.Н. (МФТИ), Щербаков П.С. (ИПУ РАН) Об эффектах
всплеска в линейных дискретных системах управления 3
Калмук А.И.
(СПбГУ) Рандомизированная стратегия управления в
условиях неопределенностей на основе прогнозирующих 22
Сенов А. А.
(СПбГУ) О методах последовательной
подпространственной оптимизации 40
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ
Издается с 2005 года
ТОМ 14
Выпуск 2
Издательство С.-Петербургского университета
2 0 1 8
УДК 519.712
БКК 32.811.7
С82
Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин
Редакционная коллегия: Б. Т. Поляк (ИПУ РАН),
А. В. Соколов (ИПМИ КарНЦ РАН),
П. С. Щербаков (ИПУ РАН)
С82 Стохастическая оптимизация в информатике. Том 14 (Вып. 2) / Под ред. О. Н. Граничина — СПб.:
Издательство С.-Петербургского университета, 2018. — 65 с. ISSN 1992–2922
Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2–14 — в 2006–18 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск двенадцатого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2018 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №16-07-00890-а.
Издание предназначено для специалистов в области информатики, студентов старших курсов и аспирантов, обучающихся на специальностях, связанных с обработкой информации.
ББК 32.811.7
© Авторы статей, 2018
Об эффектах всплеска в линейных дискретных системах управления
В. Н. Агиевич, аспирант
Московский физико-технический институт
П. С. Щербаков, д. ф.-м. н.
Институт проблем управления РАН,
Институт системного анализа РАН
Хорошо известно, что в
устойчивой линейной системе с нулевым входом и с ненулевыми начальными
условиями, траектория может сильно отклониться от начальной точки, прежде чем
сойтись к нулю. В этой работе представлен анализ переходных процессов в
линейных системах дискретного времени. Приводятся простые оценки отклонений
сверху, основанные на технике линейных матричных неравенств (LMI). Таким же
образом решена задача синтеза стабилизирующего регулятора, дающего минимальный
всплеск в замкнутой системе. Для систем с матрицей во фробениусовой форме предлагаются
оценки снизу для некоторых типов начальных условий. Также рассматриваются
эффекты всплеска нормы устойчивых по Шуру матриц.
Ключевые слова: линейные
дискретные системы, всплеск, нормы матриц, линейные матричные неравенства.
Работа
выполнена при финансовой поддержке Российского фонда фундаментальных
исследований (грант 18-08-00140).
Список литературы
[1]
Kuo
B.C., Golnaraghi F. Automatic Control Systems, 8th ed. — NY: Wiley. 2003.
[2]
Polyak
B.T., Smirnov G. Large deviations for non-zero initial conditions in linear
systems // Automatica. 2016. Vol. 74. P. 297-307.
[3]
Polyak
B.T., Tremba A.A, Khlebnikov M.V., Shcherbakov P.S., Smirnov G.V. Large
deviations in linear control systems with nonzero initial conditions, // Autom.
Remote Control. 2015. Vol. 76. No. 6. P. 957-976.
[4]
Whidborne
J.F., Amar N. Computing the maximum transient energy growth // BIT Numerical
Math. 2011. Vol. 51. No. 2. P. 447-557.
[5]
Smirnov
G.V., Bushenkov V., Miranda F. Advances on the transient growth quanti cation
in linear control systems // Int. J. Appl. Math. Statist. 2009. Vol. 14. P.
82-92.
[6]
Hinrichsen
D., Plischke E., Wurth E. State feedback stabilization with guaranteed
transient bounds // Proc. 15th Int. Symp. Math. Theory Networks Syst.
(MTNS-2002). South Bend, IN, USA. 2002.
[7]
Vladimirov
A.A., Izmailov R.N. Transients in adaptive control of a deterministic
autoregression process // Autom. Remote Control. 1992. Vol. 53. No. 6. P.
800-803.
[8]
Delyon
B., Izmailov R. The projection algorithm and delay of peaking in adaptive
control // IEEE Trans. Autom. Control. 1993. Vol. 38. No. 4. P. 581-584.
[9]
Kozyakin
V., Pokrovskii A. Estimates of amplitudes of transient regimes in
quasi-controllable discrete systems // arXiv:0908.4138v1 [math.DS]. Aug. 2009.
[10]
Kogan
M.M., Krivdina L.N. Synthesis of multipurpose linear control laws of discrete
objects under integral and phase constraints // Autom. Remote Control. 2011.
Vol. 72. No. 7. P. 1427-1439.
[11]
Horn
R.A., Johnson C.R. Matrix Analysis, 23rd printing. — NY: Cambridge University
Press. 2010.
[12]
Trefethen
L.N., Embree M. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices
and Operators — Princeton, NJ: Princeton University Press. 2005.
[13]
Dowler
D.A. Bounding the Norm of Matrix Powers. M.S. thesis. Math. Dept., Brigham
Young University, USA. 2013.
https://books.google.ru/books/about/Bounding_the_Norm_of_Matrix_Powers.html?id=ICLtoQEACAAJ&redir_esc=y.
[14]
Kreiss
H.O. Uber die stabilitatsdefinition fur differenzengleichungen die partielle
differentialgleichungen approximieren // BIT. 1962. Vol. 2. P. 153-181.
[15]
Boyd
S., Ghaoui L.El, Feron E., Balakrishnan V. Linear Matrix Inequalities in
Systems and Control Theory — Princeton, Philadelphia: SIAM. 1962.
[16]
Grant
M., Boyd S. CVX: Matlab software for disciplined convex programming (web page
and software). http://stanford.edu/∼boyd/cvx.
[17]
Shcherbakov P., Dabbene S. On the generation
of random stable polynomials, // Eur. J. Control. 2011. Vol. 77. No. 2. P.
145-159.
[18]
Durbin J. The fitting of time series models,
// Rev. Inst. Int. Stat. 1960. Vol.28. P. 233-243.
[19]
Andrieu
C., Doucet A. An improved method for uniform simulation of stable minimum phase
real ARMA (p, q) processes, // IEEE Signal Process. Lett. 1999. Vol. 6. No. 6.
P. 142-144
Рандомизированная стратегия управления в условиях неопределенностей на основе прогнозирующих моделей и алгоритма “исключения областей знакодоминирующих корреляций”
А. И. Калмук, аспирант
Санкт-Петербургский государственный университет,
В
этой работе рассматривается рандомизированный алгоритм управления с
прогнозирующими моделями в условиях неопределенностей. Задача состоит в том,
чтобы построить робастное, в вероятностном смысле, управление для всех возможных
значений неопределенностей из заранее заданного множества. Основная идея
состоит в том, что множество неопределенностей можно сужать с течением времени,
и строить новое управление на скорректированном множестве. Предлагаемый
алгоритм основан на модификации алгоритма ‘исключения областей
знакодоминирующих корреляций”. В этой работе будет также рассмотрен вопрос
сходимости алгоритма. Для проведения симуляции в качестве тестовой системы была
выбрана система с двумя неизвестными параметрами, и на ее примере
продемонстрирована работа и сходимость алгоритма.
Ключевые
слова: рандомизация, стратегия управления, прогнозирующие модели, алгоритм
“исключения областей знакодоминирующих корреляций”.
Список литературы
[1]
C.
Garcia, D. Prett, M. Morari Model predictive control – theory and practice – a
survey // Automatica. 1989. Vol. 25, No. 3. P. 335–348
[2]
D.
Q. Mayne, J. B. Rawlings, C. V. Rao, P. Scokaert Constrained model predictive
control: Stability and optimality // Automatica. 2000. Vol. 36, No. 6. P.
789–814.
[3]
G.
C. Calafiore, L. Fagiano Robust model predictive control via scenario
optimization // IEEE Transactions on Automatic Control. 2013. Vol. 58, No. 1.
P. 742–753.
[4]
D.
M. de la Pena, A. Bemporad, C. Filippi Robust explicit MPC based on approximate
multiparametric convex programming // IEEE Transactions on Automatic Control.
2006. Vol. 51, No. 8. P. 1399–1403.
[5]
M.
Kothare, V. Balakhrisna, M. Morari Robust constrained model predictive control
using linear matrix inequalities // Automatica. 1996. Vol. 32, No. 10. P.
136–2378.
[6]
D. Bernardini, A. Bemporad Scenario-based
model predictive control of stochastic constrained linear systems // In Proc.
of 2009 IEEE Conference on Decision and Control. 2009. P. 6333–6338.
[7]
G.
Calafiore, M. Campi The scenario approach to robust control design // IEEE
Transactions on Automatic Control. 2006. Vol. 51, No. 5. P. 742–753.
[8]
A.
Kalmuk, K. Tyushev, O. Granichin Online parameter estimation for MPS model
uncertainties based on LSCR approach // In Proc. of 2017 IEEE Conference on
Control Technology and Applications (CCTA). 2017. P. 1256–1261.
[9]
K.
Amelin, O. Granichin Randomized control strategies under arbitrary external
noise // IEEE Transactions on Automatic Control. 2016. Vol. 61, No. 5. P.
1328–1333.
[10]
M.
C. Campi, K. Sangho, E. Weyer Non-asymptotic confidence regions for model
parameters in the presence of unmodelled dynamics // Automatica. 2009. Vol. 45,
No. 10. P. 2175–2186.
[11]
M.
C. Campi, E. Weyer Non-asymptotic confidence sets for the parameters of linear
transfer functions // IEEE Transactions on Automatic Control. 2010. Vol. 55,
No. 12. P. 2708–2720.
[12]
K.
Amelin, O. Granichin Randomized controls for linear plants and confidence
regions for parameters under external arbitrary noise // In Proc. of 2012 American
Control Conference (ACC). 2012. P. 851–856.
[13]
O. N. Granichin The nonasymptotic confidence
set for parameters of a linear control object under an arbitrary external
disturbance // Automation and Remote Control. 2012. Vol. 73, No. 1. P. 20–30.
[14]
A.
N. Shiryaev Probability. New York, USA: Springer-Verlag, 1995
О методах последовательной подпространственной оптимизации
А. А. Сенов, аспирант
Санкт-Петербургский Государственный Университет
В
следствии роста сложности размерности задач оптимизации активное развитие
получили методы подпространственной оптимизации, где на каждом шаге алгоритма
строится подпространство, а затем в этом подпространстве
находится
оптимальный шаг. В работе рассмотрены основные направления подпространственной
оптимизации, в том числе проведена параллель с методами на основе
проекции-аппроксимации-восстановления. Сформулирована методика оценки скорости
сходимости методов последовательной подпространственной оптимизации в
зависимости от выбираемых подпространств и оптимальности поиска шага в них.
Приведены два метода аппроксимации
Гессиана
в пространстве меньшей размерности, их свойства и варианты вычисления.
Ключевые
слова: оптимизация, рекуррентные методы, понижение размерности,
подпространственные методы, проективные методы.
Работа
выполнена при поддержке РФФИ, проект №17-51-53053.
Список литературы
[1]
Akaike
H. On a successive transformation of probability distribution and its
application to the analysis of the optimum gradient method // Annals of the
Institute of Statistical Mathematics. Springer. 1959. Vol. 11, № 1., P. 1–16.
[2]
Narkiss.
G, Zibulevsky M. Sequential subspace optimization method for large-scale
unconstrained optimization // Technical report, Technion-IIT, Department of
Electrical Engineering, 2005.
[3]
Fletcher
R., Reeves C. Function minimization by conjugate gradients // The Computer
Journal. 1964. Vol. 7, №. 2, P. 149–154.
[4]
Nocedal
J., Wright S. Numerical Optimization (2nd edition) // Springer, 2006.
[5]
Yuan
Y.-X. Subspace techniques for nonlinear optimization // In: Some Topics in
Industrial and Applied Mathematics. World Scientific, 2007. P. 206–218.
[6]
Wang
Z.-H., Yuan Y.-X. A subspace implementation of quasi-Newton trust region
methods for unconstrained optimization // Numerische Mathematik. 2006. Vol.
104, № 2, P. 241–269.
[7]
Yuan
Y.-X. Subspace methods for large scale nonlinear equations and nonlinear least
squares // Optimization and Engineering. 2009. Vol. 10, №. 2. P. 207–218.
[8]
Yuan
Y.-X. A review on subspace methods for nonlinear optimization // Technical
report. 2014.
[9]
Senov A., Granichin O. Projective
approximation based gradient descent modification // IFAC-PapersOnLine. 2017.
Vol. 50, №. 1. P. 3899–3904.
[10]
Senov
A. Projective approximation based quasi-Newton methods // In International
Workshop on Machine Learning, Optimization, and Big Data. Springer. 2017. P.
29–40.
[11]
Fletcher
R. A limited memory steepest descent method // Mathematical programming. 2012.
Vol. 135, №.1–2, P. 413–436.
[12]
Barzilai
.J, Borwein J. Two-point step size gradient methods // IMA Journal of Numerical
Analysis. 1988. Vol. 8. № 1. P. 141–148.
[13]
Senov
A. Accelerating gradient descent with projective response surface methodology
// International Conference on Learning and Intelligent Optimization. Springer,
Cham. 2017. P. 376–382.
[14]
Don.
F.J.H On the symmetric solutions of a linear matrix equation // Linear Algebra
and its Applications. 1987. Vol. 93, P. 1–7.
[15]
Vetter
W. Vector structures and solutions of linear matrix equations // Linear Algebra
and Its Applications. 1975. Vol. 10, №. 2. P. 181–188.
[16]
Magnus
J., Neudecker H. The elimination matrix: some lemmas and applications // SIAM
Journal on Algebraic Discrete Methods. 1980. Vol. 1. №. 4. P. 422–449.
[17] Сенов .А Глубокое обучение в задаче реконструкции суперразрешения изображений // Стохастическая оптимизация в информатике. 2017. Т. 13. № 2. С 38–57.