e:\family\Oleg\TexDoc\sb10_1\sb10

Как действительно устроены сложные информационно-управляющие системы?

О. Н. Граничин, д. ф.-м. н

Санкт-Петербургский государственный университет, Институт проблем машиноведения РАН

o.granichin@spbu.ru

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

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

Ключевые слова: кластеризация, самоорганизация, адаптивные системы, мультиагентные системы, пространство состояний переменной структуры, самолет с “перьями”.

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

[1] Жигулев В.Н. Динамика неустойчивостей. М.: МУГИ. 1991. 152 с.

[2] Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука. 2003. 293 с.

[3] Граничин О.H., Хантулева Т.А. Гибридные системы и рандомизированные измерения в неравновесных процессах // Дифференциальные уравнения и процессы управления. №3. 2004. С. 35–43.

[4] Граничин О.Н., Кияв В.И. Информационные технологии и системы в современном менеджменте. СПб: ВВМ. 2014. 897 с.

[5] Amelin K., Amelina N., Granichin O., Khantuleva T. Adaptations of airplane’s “feathers” in a turbulence flow // Proc. CDC2016 (submitted).

[6] Nicolis G., Prigogine I. Self-Organization in Nonequilibrium Systems. From Dissipative Structure to Order Through Fluctuations. N.Y.: Wiley. 1977.

[7] Khantuleva T., Abdullaev K. Internal control in nonequilibrium physical processes // Cybernetics and Physics. Vol. 3. No. 1. 2014.

PP. 21–27.

[8] Amelina N., Fradkov A., Jiang Y., Vergados D. Approximate consensus in stochastic networks with application to load balancing // IEEE Transactions on Information Theory. Vol. 61. No. 4. 2015.

PP. 1739–1752.

[9] Granichin O., Volkovich Z. V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. Springer. 2015.

[10] Ljung L. System Identification: Theory for the User. Englewood Cliffs. NJ, Prentice Hall. 1999.

[11] Поляк Б.Т., Хлебников М.В., Щербаков П.С. Управление линейными системами при внешних возмущениях: Техника линейных матричных неравенств. М.:ЛЕВАНД. 2014.

[12] Amelin K., Granichin O. Randomized control strategies under arbitrary external noise // IEEE Transactions on Automatic Control. 2016. Vol. 61. No. 5. PP. 1328–1333.

[13] Campi M. C., Sangho K., Weyer E. Non-asymptotic confidence regions for model parameters in the presence of unmodelled dynamics // Automatica. 2009. Vol. 45. No. 10. PP. 2175–2186.

[14] Campi M. C., Weyer E. Non-asymptotic confidence sets for the parameters of linear transfer functions // IEEE Transactions on Automatic Control. 2010. Vol. 55. No. 12. PP. 2708–2720.

Реализация и анализ work-stealing планировщика задач

Р. И. Кучумов, студент

Петрозаводский государственный университет

kuchumovri@gmail.com

Параллельные планировщики задач, работающие по стратегии work-stealing, дают распределение задач близкое к оптимальному и при этом об-ладают низкими накладными расходами по времени, используемой памяти и межпроцессорным синхронизациям. Основная идея этой стратегии в том, что, когда у процессора заканчиваются задачи для выполнения, то он их забира-ет (крадет) у другого процессора. Один из недостатков этой стратегии это большое количество краж, возникающих при выполнении относительно ма-леньких задач. В этой статье приводится реализация планировщика задач, в которой можно изменять количество задач, извлекаемых за одну кражу. Такая модификация при правильном выборе размера кражи позволяет зна-чительно уменьшить общее количество краж.

Ключевые слова: планировщик задач, work-stealing, деки, параллельные вычисления.

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

[1] Yu-Kwong Kwok, Ishfaq Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors // ACM. 1999.

[2] Beaumont O., Carter L., Ferrante J., Legrand A., Marchal L., Robert Y. Centralized versus distributed schedulers for multiple bag-of-task applications // 20th IEEE International Parallel & Distributed Processing Symposium. 2006.

[3] Yinglong X., Prasanna V., Li James. Hierarchical Scheduling of DAG Structured Computations on Manycore Processors with Dynamic Thread Grouping. Springer. 2010.

[4] Hendler D., Shavit N. Work dealing (extended abstract) // SPAA’02. 2002.

[5] Acar U. A., Chargueraud A., Rainey M. Scheduling parallel programs by work stealing with private deques // ACM. 2013.

[6] Arora N. S. , Blumofe R. D. , Plaxton C. G. Thread scheduling for multiprogrammed multiprocessors // SPAA’98. 1998.

[7] Hendler D., Shavit N. Non-blocking steal-half queues // ACM. 2002.

[8] Guo Yi, Barik Rajkishore, Raghavan Raman, Sarkar Vivek. Work-First and Help-First Scheduling Policies for Async-Finish Task Parallelism. 2009.

[9] Hendler D., Lev Y., Moir M., Shavit N. A Dynamic-Sized Nonblocking Work Stealing Deque. Springer. 2005.

[10] Chase D., Lev Y. Dynamic circular work-stealing deque // SPAA’05. 2005.

[11] Nhat Minh Le, Pop A., Cohen A., Nardelli F. Z. Correct and eﬃcient work-stealing for weak memory model // ACM. 2013.

[12] Paoloni G. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures. 2010.

[13] Барковский Е.А. Математические модели и методы оптимально-го управления Work-stealing деками в общей памяти // Стохастическая оптимизация в информатике. 2015. Т. 11. №1. С. 55–64.

[14] Sokolov A.V., Barkovsky E.A. The mathematical model and the problem of optimal partitioning of shared memory for work-stealing deques // Springer International Publishing, Proceedings of The International Conference of Parallel Computing Technologies, 2015. Lecture Notes in Computer Science. Vol. 9251, P. 102–106.

Стохастические сетевые потоковые процессы

Н. В. Мальковский, аспирант

Санкт-Петербургский государственный университет

malkovskynv@gmail.com

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

Ключевые слова: сетевые потоки, стохастические системы, ограниченные пропускные способности.

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

[1] Teodorovic D., Vukadinovic K. Traffic Control and Transport Planning:: A Fuzzy Sets and Neural Networks Approach. – Springer Science & Business Media. 2012.

[2] Handbook of Transportation Science / Под ред. Hall R.. Springer Science & Business Media. 2012.

[3] Cascetta E. Transportation Systems Engineering: Theory and Methods, Springer Science & Business Media. 2013.

[4] Введение в математическое моделирование транспортных потоков / Под ред. Гасникова А. В. – Московский центр непрерывного математического образования. 2015.

[5] Ford L. R. Jr, Fulkerson D. R. Constructing maximal dynamic flows from static flows // Operations research. 1958. Vol. 6. No. 3. PP. 419– 433.

[6] Skutella M. An introduction to network flows over time // In: Research Trends in Combinatorial Optimization. 1958. Springer. PP. 451–482.

[7] K¨ohler E., M¨ohring R. H., Skutella M. Traffic networks and flows over time // In: Algorithmics of Large and Complex Networks. 2009. Springer. PP. 166–196.

[8] Ford L., Fulkerson D. R. Flows in networks. – Princeton Princeton University Press. 1962.

[9] Glockner G. D., Nemhauser G. L. A dynamic network flow problem with uncertain arc capacities: formulation and problem structure // Operations Research. 2000. Vol. 48. No. 2. PP. 233–242.

[10] Han S., Peng Z., Wang S. The maximum flow problem of uncertain network // Information Sciences. 2014. Vol. 265. PP. 167–175.

[11] Sheng Y., Gao J. Chance distribution of the maximum flow of uncertain random network // Journal of Uncertainty Analysis and Applications. 2014. Vol. 2. No. 1. PP. 1–14.

[12] Bellman R. E., Dreyfus S. E. Applied Dynamic Programming. – 1962.

[13] Понтрягин Л. С. Математическая теория оптимальных процессов. – Гос. изд-во Физико-математической литры. 1961.

[14] Nesterov Y., Nemirovskii A., Ye Y. Interior-point polynomial algorithms in convex programming // SIAM. Vol. 13. 1994.

[15] Boyd S., Vandenberghe L. Convex optimization. – Cambridge university press. 2009.

[16] Мальковский Н. В. Модель балансировки загрузки в вычислительной сети с использованием задачи параметрического потока // Стохастическая оптимизация в информатике. 2014. Т. 10. № 1. С. 39–62.

[17] Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications // SIAM Journal on Computing. 1989. Vol. 18. No. 1. PP. 30–55.

[18] Goldberg A. V., Tarjan R. E. A new approach to the maximum-flow problem // Journal of the ACM (JACM). 1988. Vol. 35. No. 4. PP. 921–940.

[19] Garg N., Koenemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems // SIAM Journal on Computing. 2007. Vol. 37. No. 2. PP. 630–652.

[20] Herty M., Kirchner C., Moutari S., Rascle M. et al. Multicommodity flows on road networks // Communications in Mathematical Sciences. 2008. Vol. 6, No. 1, PP. 171–187.

[21] Батюков А. М. Анализ цифровых изображений, основанный на построении стационарного потока на графе // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2015. № 2. С. 115–122.

[22] Ампилова Н. Б., Романовский И. В., Петренко Е. И. О максимизации энтропии при линейных ограничениях // Труды Междунар. науч. конференции «Космос, астрономия и программирование (Лавровские чтения)». СПб.: Математико-механический факультет С.-Петерб. ун-та. 2008. C. 181–185.

[23] Madry A. Navigating central path with electrical flows: From flows to matchings, and back // Foundations of Computer Science (FOCS). 2013. IEEE 54th Annual Symposium on, 2013. pp. 253–262.

[24] Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian journal of Mathematics, 1956, vol. 8, no. 3, pp. 399–404.

[25] Goldberg A. V., Tarjan R. E. Efficient maximum flow algorithms // Communications of the ACM. 2014. Vol. 57. No. 8. PP. 82–89.

[26] Карзанов А. В. Нахождение максимального потока в сети методом предпотоков // ДАН СССР. 1974. Т. 215. № 1. С. 49–52.

[27] Orlin J. B. Max flows in O(nm) time, or better // Proc. the forty-fifth annual ACM symposium on Theory of computing. 2103. PP. 765–774, ACM.

[28] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of state calculations by fast computing machines // The Journal of Chemical Physics. 1953. Vol. 21. No. 6. PP. 1087– 1092.

[29] Wiener N. Extrapolation, interpolation, and smoothing of stationary time series. – MIT press Cambridge. Vol. 2. 1949.

[30] Kalman R. E. A new approach to linear filtering and prediction problems // Journal of basic Engineering. 1960. Vol. 82. No. 1. PP. 35– 45.

[31] Robbins H., Monro S. A stochastic approximation method // The Annals of Mathematical Statistics. 1951. PP. 400–407.

[32] Kiefer J., Wolfowitz J. et al. Stochastic estimation of the maximum of a regression function // The Annals of Mathematical Statistics. 1952. Vol. 23. No. 3. PP. 462–466.

[33] Blum J. R. Multidimensional stochastic approximation methods // The Annals of Mathematical Statistics. 1954. PP. 737–744.

[34] Поляк Б. Т. Новый метод типа стохастической аппроксимации //Автоматика и телемеханика. - 1990. - №7. - С. 98–107.

[35] Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Transactions on Automatic Control. - 1992. - Vol. 37. - No. 3. PP. 332–341.

[35] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе //Автоматика и телемеханика. - 1992. - №. 2. С. 97-104.

[36] Граничин О. Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. - 2002. - №2. - C. 44–55.

[37] Граничин О. Н. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. - 2002. - №1. - C. 30–41.

[38] Bertsekas D. P. Dynamic Programming and Stochastic Control. – 1976.

[39] Calafiore G. C., Campi M. C. et al. The scenario approach to robust control design // IEEE Transactions on Automatic Control. 2006. Vol. 51. No. 5. PP. 742–753.

[40] Амелин К. С., Граничин О. Н., Кияев В. И., Иевлев Н. В. Мобильность и супервычисления на охране природы // Компьютер-Информ. 2011. № 05–06, С. 24–25.

[42] Amelin K., Amelina N., Granichin O., Granichina O., Andrievsky B. R. Randomized algorithm for uavs group flight optimization // Proc. 11th IFAC International Workshop on Adaptation and Learning in Control and Signal Processing. 2013. PP. 205–208.

[43] Амелин К. С. Рандомизация в контуре управления легкого БПЛА при полете в условиях неизвестных изменений направления ветра // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2013. № 2. С. 86–102.

[44] Амелин К. С. Технология программирования легкого БПЛА для мобильной автономной группы // Стохастическая оптимизация в информатике. 2011. Т. 7. № 1. С. 93–115.

[45] Letchford A. N., Salazar-Gonzalez, J. J. Stronger multi-commodity flow formulations of the Capacitated Vehicle Routing Problem // European Journal of Operational Research. 2015. Vol. 244. No. 3. PP. 730–738.

[46] Kameda H., Li J., Kim C., Zhang Y. Optimal Load Balancing in Distributed Computer Systems. – Springer Publishing Company Incorporated. 2011.

[47] Alakeel A. M. A guide to dynamic load balancing in distributed computer systems // International Journal of Computer Science and Information Security. 2010. Vol. 10. No. 6. PP. 153–160.

[48] Doddini Probhuling L. Load balancing algorithms in cloud computing // International Journal of Advanced Computer and Mathematical Sciences. 2013. Vol. 2. PP. 2230–9624.

[49] https://github.com/Malkovsky/load-balancing

[50] http://research.microsoft.com/en-us/downloads/d3adb5f7-49ea-4170-abde-ea0206b25de2/default.aspx

[51] Babenko M., Goldberg A. V. Experimental evaluation of a parametric flow algorithm. — Technical report, Microsoft Research, 2006. MSR-TR-2006-77, 2006.

Рандомизированный алгоритм при обработке данных ультразвуковых исследований

И. И. Сенин, студент

Санкт-Петербургский государственный университет

i.senin@2012.spbu.ru

Ультразвуковая томография нашла широкое применение в медицинской практике. По мере развития технологий стало возможным использование большего количества датчиков для получения более качественного изображения, что привело к большому объему обрабатываемой информации. Однако характер получаемых при томографии изображений имеет разреженный профиль, из чего следует, что необходимое для восстановления количество информации очень мало. Значительная избыточность данных оставляет возможность для разработки более оптимальной технологии сбора и анализа в процессе томографического исследования. В этой работе рассмотрена возможность применения техники “Compressive Sensing” для улучшения алгоритма реконструкции. Метод показал свою эффективность, позволив снизить объем используемых данных без потери в качестве.

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

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

[1] Lustig, Michael and Donoho, David and Pauly, John M Sparse MRI: The application of compressed sensing for rapid MR imaging // Magnetic Resonance in Medicine. 2007. P. 1182–1195.

[2] Lustig, Michael and Donoho, David L and Santos, Juan M and Pauly, John M Compressed sensing MRI // Signal Processing Magazine, IEEE. 2008. P. 72-82.

[3] Schreiman, JS and Gisvold, JJ and Greenleaf, James F and Bahn, RC Ultrasound transmission computed tomography of the breast // Radiology. 1984. P. 512–530.

[4] Leonid Kunyansky Fast reconstruction algorithms for the

thermoacoustic tomography in certain domains with cylindrical or spherical symmetries // Inverse Problems and Imaging. 2012. P.111–131.

[5] Shannon C. E Communication in the presence of noise // Proc. Institute of Radio Engineers. 1949. P. 10–21.

[6] Quinsac, C., Basarab, A., Kouame, D., Gregoire, J.-M. 3D Compressed sensing ultrasound imaging // IEEE International Ultrasonics Symposium. 2010. P. 363–366.

[7] Li, Cuiping and Huang, Lianjie and Duric, Nebojsa and Zhang, Haijiang and Rowe, Charlotte An improved automatic time-of-flight picker for medical ultrasound tomography // Ultrasonics. 2009. P. 61– 72.

[8] Граничин О.Н., Павленко Д.В. Pандомизация получения данных и ℓ₁-оптимизация (опознание со сжатием) (Обзор) // Автоматика и телемеханика, 2010, є 11. С. 3-28.

[9] Granichin, Oleg Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // Automatic Control, IEEE Transactions on. 2004. P. 1830–1837.

[10] Donoho, David L Compressed sensing // IEEE Transactions on Information Theory. 2006. P. 1289–1306.

[11] Candes, Emmanuel and Romberg, Justin Sparsity and incoherence in compressive sampling // Inverse Problems. 2007. P. 969.

[12] Cand`e, Emmanuel J. and Wakin, Michael B. An introduction to compressive sampling // IEEE Signal Processing Magazine. 2008. P. 21–30

[13] Cand`es, Emmanuel J. and Romberg, Justin and Tao, Terence Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information // IEEE Transactions on Information Theory. 2006. P. 489–509.

[14] Natarajan, Balas Kausik Sparse approximate solutions to linear systems // SIAM Journal on Computing. 1995. P. 227–234.

[15] Mallat, Stephane G and Zhang, Zhifeng Matching pursuits with time-frequency dictionaries // IEEE Transactions on Signal Processing. 1993. P. 3397–3415.

[16] Donoho, David L. For most large underdetermined systems of linear equations the minimal L1-norm solution is also the sparsest solution // Communications on Pure and Applied Mathematics. 2006. P. 797– 829

[17] Chen, Scott Shaobing and Donoho, David L and Saunders, Michael A Atomic decomposition by basis pursuit // SIAM Review. 2001. P. 129–159

[18] Dines, Kris A and Lytle, R Jeffrey Computerized geophysical tomography // Proceedings of the IEEE. 1979. P. 1065–1073.

[19] Duric, Nebojsa and Littrup, Peter and Poulo, Lou and Babkin, Alex and Pevzner, Roman and Holsapple, Earle and Rama, Olsi and Glide, Carri Detection of breast cancer with ultrasound tomography: First results with the Computed Ultrasound Risk Evaluation (CURE) prototype // Medical Physics. 2007. P. 773–785.

[20] Treeby, Bradley E and Cox, Benjamin T k-Wave: MATLAB toolbox for the simulation and reconstruction of photoacoustic wave fields // Journal of Biomedical Optics. 2010. P. 021314.

[21] Baraniuk, Richard and Davenport, Mark and DeVore, Ronald and Wakin, Michael A simple proof of the restricted isometry property for random matrices // Constructive Approximation. 2008. P. 253– 263.

[22] Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. – Наука, М. 2003. 293 c.

[23] Schuster, Arthur An introduction to the Theory of Optics. – E. Arnold. 1904.

[24] Ozmen, N. Ultrasound Imaging Methods for Breast Cancer Detection. – TU Delft, Delft University of Technology. 2014.

[25] Hormati, Ali and Jovanovic, Ivana and Roy, Olivier and Vetterli, Martin Robust ultrasound travel-time tomography using the bent ray model // Proc. SPIE. 2010. P. 76290I.

[26] Quan, Youli and Huang, Lianjie Sound-speed tomography using first-arrival transmission ultrasound for a ring array // Medical Imaging. 2007. P. 651306–651306.

[27] Hopp, Torsten and Sroba, Lukas and Zapf, Michael and Dapp, Robin and Kretzek, Ernst and Gemmeke, Hartmut and Ruiter, Nicole V Breast imaging with 3D ultrasound computer tomography: results of a first in-vivo study in comparison to MRI images // Breast Imaging. 2014. P. 72–73.

[28] Chen, Chen and Huang, Junzhou Compressive sensing MRI with wavelet tree sparsity // Advances in Neural Information Processing Systems. 2012. P. 1115–1123.

[29] Berinde, Radu and Indyk, Piotr and Ruˇzi´c, M Practical near-optimal sparse recovery in the l1 norm // 46th Annual Allerton Conference on Communication, Control, and Computing. 2008. P. 198–205.

[30] Roy, Olivier and Schmidt, Signe and Li, Cuiping and Allada, Veerendra and West, Erik and Kunz, Daniel and Duric, Neb Breast imaging using ultrasound tomography: From clinical requirements to system design // IEEE International Ultrasonics Symposium (IUS). 2013. P. 1174–1177.

[31] Quinsac, C´eline and Basarab, Adrian and Girault, Jean-Marc and Kouame, Denis Compressed sensing of ultrasound images: sampling of spatial and frequency domains // 2010 IEEE Workshop on Signal Processing Systems (SIPS). 2010. P. 231–236.

Внешняя оценка множества достижимости линейной динамической систем

М. В. Хлебников, д. ф.-м. н.

Институт проблем управления им. В. А. Трапезникова РАН

mkhlebnikov2008@yandex.ru

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

Ключевые слова: линейная динамическая система, множество достижимости, инвариантный эллипсоид, линейные матричные неравенства.

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

[1] Abedor J., Nagpal K., Poolla K. A linear matrix inequality approach to peak-to-peak gain minimization // Int. J. Robust and Nonlinear Control. 1996. No. 6. P. 899–927.

[2] Blanchini F., Miani S. Set-Theoretic Methods in Control. Boston: Birkh¨auser, 2008.

[3] Boyd S., El Ghaoui L., Feron E., et al. Linear Matrix Inequalities in System and Control Theory. Philadelphia: SIAM, 1994.

[4] Dahleh M.A., Diaz-Bobillo I.J. Control of Uncertain Systems. A Linear Programming Approach. NJ: Prentice Hall, 1995.

[5] Поляк Б.Т., Хлебников М.В., Щербаков П.С. Управление линей-ными системами при внешних возмущениях. Техника линейных матричных неравенств. М.: ЛЕНАНД, 2014.

[6] Vidyasagar M. Optimal rejection of persistent bounded disturbances // IEEE Trans. Autom. Control. 1986. V. 31. No. 6. P. 527–534.

[7] Schweppe F.C. Uncertain Dynamic Systems. N.J.: Prentice Hall, 1973.

[8] Kurzhanski A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. Boston: Birkhauser, 1997.

[9] Polyak B.T., Nazin A.V., Topunov M.V., Nazin S.A. Rejection of bounded disturbances via invariant ellipsoids technique // Proc. 45th IEEE Conference on Decision and Control. San Diego, USA, December 13–15, 2006. P. 1429–1434.

[10] Назин С.А., Поляк Б.Т., Топунов М.В. Подавление ограниченных внешних возмущений с помощью метода инвариантных эллипсоидов // Автоматика и телемеханика. 2007. №3. С. 106–125.

[11] Хлебников М.В., Поляк Б.Т., Кунцевич В.М. Оптимизация линейных систем при ограниченных внешних возмущениях (техника инвариантных эллипсоидов) // Автоматика и телемеханика. 2011. №11. С. 9–59.

[12] Venkatesh S., Dahleh M. Does star norm capture l₁ Norm? // Proc. American Control Conference (ACC’95). Seattle, USA, June 21–23, 1995. P. 944–945.

Невыпуклый детектор матричной разреженности с применением к оптимальному управлению линейными системами

А. В. Быков, аспирант,

П. С. Щербаков, д. ф.-м. н. Институт Проблем Управления РАН

alexey.bykov.mipt@gmail.com

cavour118@mail.ru

В работе [8] предложен подход к синтезу разреженной обратной связи

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

Ключевые слова: линейные системы, разреженные регуляторы, линейные матричные неравенства, H_∞-оптимизация, DC-функции, CCCP.

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

[1] B. Polyak, M. Khlebnikov, and P. Shcherbakov. An LMI approach to structured sparse feedback design in linear control systems. In Proc. Eur. Control Conf., pages 833–838, Zurich, Switzerland, July 2013.

[2] F. Lin, M. Fardad, and M. R. Jovanovic. Augmented Lagrangian approach to design of structured optimal state feedback gains. IEEE Trans. Automat. Control, 56(12):2923–2929, 2011.

[3] D. Zelazo, S. Schuler, and F. Allgower. Performance and design of cycles in consensus networks. Syst. Control Lett., 62(1):85–96, 2013.

[4] U. M¨unz, M. Pfister, and P. Wolfrum. Sensor and actuator placement for linear systems based on H₂ and H_∞ optimization. IEEE Trans. Automat. Control, 59(11):2984–2989, 2014.

[5] A. M. Bruckstein, D. L. Donoho, and M. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Review, 51(1):34–81, 2009.

[6] M. Fazel, H. Hindi, and S. Boyd. Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In Proc. American Control Conf., pages 2156–2162, Denver, Colorado, June 2003.

[7] E. J. Candes, M. B. Wakin, and S. P. Boyd. Enhancing sparsity by reweighted ℓ₁ minimization. J. Fourier Anal. Appl., 14(5):877–905, 2008.

[8] F. Lin, M. Fardad, and M. R. Jovanovi´c. Design of optimal sparse feedback gains via the alternating direction method of multipliers. IEEE Trans. Automat. Control, 58(9):2426–2431, 2013.

[9] B. T. Polyak, M. V. Khlebnikov, and P. S. Shcherbakov. Sparse feedback in linear control systems. Autom. Remote Control, 75(12):2099–2111, 2013.

[10] N. K. Dhingra, M. R. Jovanovic, and Z. Q. Luo. An ADMM algorithm for optimal sensor and actuator selection. In Proc. Conf. Decision Control, pages 4039–4044, Los Angeles, CA, June 2014.

[11] B. T. Polyak, M. V. Khlebnikov, and P. S. Shcherbakov. Control of Linear Systems Subjected to Exogenous Disturbances: The Linear Matrix Inequality Technique. URSS, Moscow (in Russian), 2014.

[12] T. Iwasaki and R. E. Skelton. A complete solution to the general H_∞ control problem: LMI existence conditions and state space formulas. In Proc. American Control Conf., pages 605–609, San Francisco, USA, June 1993.

[13] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory. SIAM, Philadelphia, 1994.

[14] P. Hartman. On functions representable as a diﬀerence of convex functions. Pacific J. Math., 9(3):707–713, 1959.

[15] A. L. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 15:915–936, 2003.

[16] G. R. Lanckriet and B. K. Sriperumbudur. On the convergence of the concave-convex procedure. In Advances in Neural Information Processing Systems 22, pages 1759–1767, Vancouver, Canada, December 2009.

[17] F. Leibfritz and W. Lipinski. Description of the benchmark examples in COM P l_eib 1.0. www.complib.de, 2003.

[18] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, March 2014.

[19] K. C. Toh, M. J. Todd, and R. H. Tutuncu. SDPT3 — a Matlab software package for semidefinite programming. Optimization Methods and Software, 11:545–581, 1999.