Проекционный алгоритм линейного программирования на основе поиска пересечения прямой и зонотопа Максим Деменков Институт проблем управления им. В.А. Трапезникова Профсоюзная 65, 117997 Москва, Россия max.demenkov@gmail.com Аннотация. В работе рассматривается проекционный алгоритм решения задачи линейного программирования при наличии интервальных ограни- чений на все переменные. Ограничения задачи преобразуются в много- гранник специального вида – зонотоп, а ее решение соответствует мини- мальной по некоторой координате точке пересечения зонотопа с прямой. Предложена параллелизация алгоритма на основе метода типа бисекции. Ключевые слова: линейное программирование, параллельные вычисле- ния, выпуклые многогранники, зонотопы, проекция. 1 Введение Российские исследователи неоднократно рассматривали решение задач ли- нейного программирования (ЛП) проекционными методами (см. напр. [1-8]). В основном такие подходы связаны с развивавшимися в рамках научной школы акад. И.И. Еремина методами фейеровского типа (см. напр. [8-10]), в основе которых лежит операция проектирования на простейшие выпуклые множества. Преимущества подобных методов многие авторы видят в параллелизации ре- шения задач ЛП большой размерности. Так, в работе [1] отмечается, что боль- шая каноническая система линейных уравнений и неравенств может быть раз- бита на малые подсистемы, в случае чего для выполнения проекции нужно бу- дет обращать матрицы небольших размеров. Обычно в задачах ЛП распаралле- ливание ведется в процессе самого решения сверхбольших систем линейных уравнений, например возникающих в результате применения метода Ньютона [11]. Однако с увеличением размера матриц подходы, связанные с решением полной системы уравнений, становятся малоэффективными – так, в выступле- нии Иона Никоары на конф. ECC 2013 (см. также [12]) утверждалось, что для размерности матрицы 108 у современного персонального компьютера с часто- той 2 ГГц уйдет примерно 107 лет на завершение всего лишь одной итерации метода Ньютона. В то же время в случае использования градиентного метода в аналогичной задаче квадратичной оптимизации на итерацию уйдет 1 день при той же размерности матрицы, на решение с приемлемой точностью - 100 дней. Copyright © by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org 186 Максим Деменков В настоящей работе задача ЛП рассматривается в контексте т.н. встроенной оптимизации (embedded optimization) – направления, развивающегося с начала этого столетия, по-видимому, исключительно за рубежом (см. напр. недавние англоязычные работы по автоматическому управлению только за один 2014 г. [13-17]) – автору неизвестны отечественные работы на эту тему. Встроенная оптимизация предполагает решение оптимизационных задач небольшого разме- ра, но в режиме реального времени на базе маломощного (по сравнению с пер- сональным, или, тем более, кластерным компьютером) встроенного микропро- цессора для задач управления или обработки сигналов. В работах по встроенной оптимизации принимают участие такие известные зарубежные специалисты, как Стивен Бойд [18], Ю.Е. Нестеров, созданы системы генерации оптимизаци- онных кодов для встроенных процессоров, такие как ACADO [19], FORCES [20], Multi-Parametric Toolbox [21]. При решении задач встроенной оптимизации возникают технические огра- ничения, которые могут показаться необычными исследователям, занимающим- ся задачами оптимизации применительно к персональным или тем более кла- стерным компьютерам. Так, например, во многих работах по встроенной опти- мизации считается преимуществом полное отсутствие необходимости решения систем линейных уравнений, обращения матриц. Причиной является как отсут- ствие необходимых стандартных библиотек функций для целевого процессора с операционной системой реального времени или без нее, так и повышенного за счет этих операций времени выполнения программы. Гораздо более важной, чем в традиционных задачах математической оптимизации, становится незавы- шенная оценка сверху времени выполнения программы для всех исходных дан- ных из некоего заданного диапазона, так как по окончании вычислений проис- ходит выдача команд управления или обработка информации для технического объекта, которая регулярно повторяется с заданным периодом в диапазоне мик- ро- и миллисекунд. Немаловажной является и простота реализации алгоритма с точки зрения инженера-специалиста в конкретной прикладной области, зачас- тую не являющегося экспертом в теории оптимизации. Отметим, что в задачах управления реального времени весьма популярен вариант метода «быстрого градиента» Ю.Е. Нестерова [22], основанный на проекции на гиперкуб (которая выполняется покомпонентно путем выбора ми- нимального из двух чисел). В работах [23,24] метод используется для решения задачи минимизации квадратичной положительно определенной функции с интервальными ограничениями на переменные, получены оценки сверху време- ни выполнения метода для заданной точности решения. В работе [25] метод используется в качестве вспомогательного для решения задачи квадратичного программирования с линейными ограничениями общего вида. Предложенные в этих работах подходы, безусловно, относятся к методам проекционного типа и представляют интерес и за пределами задач встроенной оптимизации. Так, на- пример, отсутствие в алгоритме поиска решения системы линейных уравнений может оказаться выигрышным и для задач «гигабайтной» оптимизации [5] – как известно, квадратичное программирование широко используется в задачах ма- шинного обучения, в частности в методе SVM (support vector machines) [26], Проекционный алгоритм линейного программирования 187 возникновение которого связано с работами В.Н. Вапника и М.А. Айзермана, выполненными в советское время в ИАТ АН СССР. Мотивацией для настоящей работы послужили исследования в области ис- пользования полиэдральных (т.е. основанных на минимизации l1- и l∞-норм) критериев качества в задачах управления на основе предсказательного модели- рования (model predictive control) [27-29] и другие подходы к управлению на основе ЛП в реальном времени (см. напр. [30-32]), а также весьма популярная в последнее время задача восстановления сильно разреженных сигналов на осно- ве l1-нормы (compressed sensing) [33-37]. Все эти задачи сводятся к задаче ЛП, а их выполнение в большинстве случаев подразумевается на встроенных микро- процессорах. Исторически первой задачей управления, решенной с помощью ЛП, яви- лась задача оптимального по быстродействию управления для дискретных ли- нейных систем c ограничениями на управление [38]. Интересно отметить, что первая попытка использовать конечномерную оптимизацию в задачах управле- ния с обратной связью связана также с линейным программированием и являет- ся международно признанным приоритетом отечественных ученых в лице А.И. Пропоя [39]. В настоящей работе предпринята попытка с одной стороны, использовать многоядерность встроенного процессора (так, например, в современных архи- тектурах ARM и Intel Atom доступны по крайней мере 4-8 ядер) в процессе ре- шения задачи ЛП, и с другой – построить алгоритм таким образом, чтобы мож- но было легко вычислить нужное число итераций для заданной точности реше- ния. При этом в настоящей работе предприняты пока только лишь начальные шаги в выбранном направлении. Предложен параллельный алгоритм решения задачи, но пока не выполнены необходимые для оценки его работоспособности вычисления, не выполнено сравнение с другими возможными подходами к ре- шению задач ЛП на встроенных микропроцессорах (например, ADMM [17,40]). 2 Линейное программирование как поиск пересечения прямой и зонотопа Зонотопы  выпуклые многогранники, являющиеся аффинными проекция- ми многомерного куба [41]: Z  {z  R n : z  z0  Hx, || x ||  1}, x  R m , n  m,|| x ||  max | xi |. (1) i 1,..., n Здесь матрица H  [h1 | h2 | ...| hm ]  R nm содержит столбцы- генераторы. В задаче линейного программирования (ЛП) с минимизируемой целевой функцией pT z и ограничением z  Z решение легко определяется в замкнутом виде: 188 Максим Деменков m x*  arg min pT (z0  Hx)  z0   hi sign ( pT hi ) , (2) || x|| 1 i 1 если i, p hi  0 . В случае i, p hi  0 решение представляет собой вы- T T пуклую оболочку некоторых граничных точек Z . Эта формула может быть использована в методе условного градиента (название предложено Б.Т. Поля- ком [42], в англоязычной литературе метод больше известен как Frank-Wolfe algorithm по именам его изобретателей Маргарет Франк и Филипа Вульфа), где на каждом шаге метода ищется линейное приближение выпуклой функции и затем его минимум на Z . В последнее время метод условного градиента при- влек внимание исследователей в области машинного обучения, где он дает пре- имущества при решении больших задач квадратичной оптимизации – см. напр. работы [43-45]. В [46] был предложен подход к решению задачи ЛП вида min cT x, Ax  b, || x ||  1, (3) с помощью выпуклой оптимизации на зонотопе. Задачу можно переформулиро- вать с учетом данного выше определения как b   A min  , l ( )     Z, H   T  , z 0  0. (4)   c  Теперь мы ищем минимальную по  точку пересечения прямой l() и зонотопа. Заметим, что путем добавления дополнительных переменных и ограничения их некоторыми конечными интервалами в подобном виде можно, по сути, сформу- лировать любую практическую задачу ЛП. Для иллюстрации подхода на рис. 1 изображены зонотоп и прямая l ( ) , по- строенные для простейшей задачи ЛП: max x1 , x1  x2  0, x1  x2  1, || x ||  2. (5) Для преобразования неравенства задачи в равенство вводится дополнительная переменная x3 [0,5] (здесь x3 =5 соответствует x1,2  2 ). Интервал [-2,2] для значений    x1 определяется ограничениями на x1 . Для преобразования в форму (1) столбцы H в (4) необходимо поделить на ширину интервалов. Тогда Проекционный алгоритм линейного программирования 189 0  1/ 4 1/ 4 0  l ( )  1 , H   1/ 4 1/ 4 1/ 5 .   (6)      1/ 4 0 0  В данном случае (как и в формуле (5)) зонотоп несимметричен (смещен) отно- сительно начала координат, это соответствует ненулевому z0 в (4). Рис. 1. Зонотоп (зеленый) и прямая l() (красная), построенные для примера. Минимальное значение вертикальной координаты =-0.5 в точке пересечения соответствует максимуму переменной x1 =0.5 в задаче ЛП. Описанный подход позволяет решать задачу проекционными методами. Метод LP-Newton, предложенный в [46], решает задачу за конечное число ша- гов (весьма похожий метод предложен позднее также в [47] для другой задачи, а в [48] метод [46] был распространен на общий случай ЛП с проекцией на ко- нус). Поясним суть метода. Вначале выполняется проекция произвольной точ- ки, принадлежащей прямой, на зонотоп, для чего задача сводится к поиску точ- ки многогранника, ближайшей к началу координат (перенесенного в точку на прямой). Эта задача в работе [46] решается методом из [49] (заметим, что в оте- чественной литературе по негладкой оптимизации для аналогичной задачи предложен известный метод МДМ [50]). Затем строится плоскость, касательная к поверхности уровня квадратичной функции евклидова расстояния в точке 190 Максим Деменков проекции на зонотопе и находится точка пересечения этой плоскости с прямой (автор работы [46] проводит аналогии с методом Ньютона для гладких функ- ций, где также ищется пересечение с касательной плоскостью, отсюда название метода). Затем уже эта точка берется в качестве начальной и все операции по- вторяются. Отметим, что в отечественной литературе конечношаговый метод решения задачи ЛП на другой основе был впервые предложен, по видимому, в [51] (раз- вит далее в [52]), в последнее время конечношаговый метод ЛП был предложен также в работах под рук. акад. Ю.Г. Евтушенко [53,54]. В настоящей работе рассматривается возможность распараллеливания ме- тода пересечения зонотопа и прямой на других принципах. Предлагается стро- ить алгоритм на основе деления отрезка прямой l() на несколько интервалов (пропорционально количеству параллельных ветвей программы) и одновремен- ного поиска проекций границ этих интервалов на зонотоп (одним из доступных методов – например, методом МДМ, методом Вульфа [49], методом условного или «быстрого» градиента). Необходимым условием для начала работы такого алгоритма является поиск начальной внутренней точки зонотопа, для чего теми же методами решается задача b   A  min yT y, y      T  x, || x ||  1,  min     max . (7)   c  Предлагаемый мультисекционный (имеется в виду аналог бисекции в случае нескольких интервалов деления отрезка) алгоритм состоит из следующих ша- гов: n n  Шаг 1. Вычислить  min   cisign(ci ),  max   cisign(ci ), i 1 i 1 что соответствует оптимизации с x на ограичениях || x ||  1 . T  Шаг 2. Вычислить по (7) внутреннюю точку l ( ) и присвоить  max   . * *  Шаг 3. Исходя из числа N паралельных процессов, разбить интервал [ min ,  max ] на N равных подинтервалов. Для их граничных точек одновре- менно вычислить их проекции на зонотоп. Пометить точки, проекция кото- рых не равна самим этим точкам, как внешние.  Шаг 4. Присвоить границам интервала новые значения – максимальное среди внешних точек и минимальное среди внутренних, если разница между соот- ветствующими точками мала – выйти, иначе перейти на Шаг 3. Проекционный алгоритм линейного программирования 191 3 Заключение Целью работы является предложить для дальнейшего исследования и обсуж- дения новый подход к решению задач ЛП на основе на основе параллельного мультисекционного деления отрезка и проекций на многогранник специального вида. Автор не утверждает, что рассматриваемый в работе метод ЛП имеет ка- кие-либо преимущества перед предлагавшимися ранее в контексте задач ЛП большой размерности, в то же время, поскольку в методе отсутствует как тако- вая операция решения системы уравнений, представляют интерес дальнейшие исследования также и в этом направлении. Заметим, что в работе описан лишь один из множества возможных методов, использующих общую идею поиска пересечения прямой и зонотопа. Очевидно, что решение может быть получено и классическим методом альтернирующих проекций [7,55,56], в котором поочередно находятся проекции текущей точки прямой l() на зонотоп и полученной точки на зонотопе обратно на прямую. В контексте рассматриваемых в работе подходов представляет интерес также ра- бота [57], где проекционными методами решается задача смешанного целочис- ленного программирования без использования стандартного в таких случаях метода ветвей и границ. Автор благодарен анонимному рецензенту, обратившему его внимание на работы отечественных авторов по конечношаговым методам ЛП, а также участ- никам конференций SIAM Conference on Parallel Processing for Scientific Compu- ting (Париж, апрель 2016 г.) и International Congress on Mathematical Software (Берлин, июль 2016 г.), где проходило обсуждение вариантов метода. Список литературы 1. Бердникова Е. А., Ерeмин И. И., Попов Л. Д.: Распределенные фейеровские процес- сы для систем линейных неравенств и задач линейного программирования. Автома- тика и телемеханика, № 2, с. 16–32 (2004) 2. Еремин И.И.: Линейная оптимизация и системы линейных неравенств. М. : Изда- тельский центр «Академия» (2007) 3. Голиков А.И., Евтушенко Ю.Г.: Нахождение проекции заданной точки на множество решений задач линейного программирования. Тр. ИММ УрО РАН, № 2, с. 33–47 (2008) 4. Нурминский Е.А.: Проекция на внешне заданные полиэдры. Ж. вычисл. матем. и ма- тем. физ., № 3, 387–396 (2008) 5. Нурминский Е.А., Шамрай Н.Б.: Полиэдры, независимые множества и гигабайтное линейное программирование. Материалы V Всерос. конф. «Проблемы оптимизации и экономические приложения», Омск: Изд-во Омск. гос. ун-та, c. 52-56 (2012) 6. Nurminski, E.A.: Single-projection Procedure for Linear Optimization. J. of Global Opti- mization, Online First Articles (2015) 7. Гурин Л.Г., Поляк Б.Т., Райк Э.В.: Методы проекций для отыскания общей точки выпуклых множеств. Ж. вычисл. матем. и матем. физ., № 6, с. 1211–1228 (1967) 192 Максим Деменков 8. Ерeмин И. И., Попов Л. Д.: Фейеровские процессы в теории и практике: обзор по- следних результатов. Изв. вузов. Матем., № 1, с.44–65 (2009) 9. Нурминский Е.А.: Фейеровские алгоритмы с адаптивным шагом. Ж. вычисл. матем. и матем. физ., № 5, c. 791–801 (2011) 10. Шамрай Н.Б.: Поиск потокового равновесия проективными методами с использова- нием декомпозиции и генерации маршрутов. Автоматика и телемеханика, № 3, 150– 165 (2012) 11. Гаранжа В.А, Голиков А.И., Евтушенко Ю.Г, Нгуен М.Х.: Параллельная реализация метода Ньютона для решения больших задач линейного программирования. Ж. вы- числ. матем. и матем. физ., № 8, с. 1369–1384 (2009) 12. Necoara I., Nesterov Y., Glineur F.: A Random Coordinate Descent Method on Large Op- timization Problems with Linear Constraints. Technical Report, University Politehnica Bucharest (2011) 13. Guiggiani A., Patrinos P., Bemporad A.: Fixed-point Implementation of a Proximal New- ton Method for Embedded Model Predictive Control. In Proc. of the 19th IFAC World Congress, Cape Town, South Africa (2014) 14. Rubagotti M., Patrinos P., Bemporad A.: Stabilizing Linear Model Predictive Control un- der Inexact Numerical Optimization. IEEE Trans. on Automatic Control 59, 1660-1666 (2014) 15. Korda M., Jones C. N.: Certification of Fixed Computation Time First-order Optimization- based Controllers for a Class of Nonlinear Dynamical Systems. In Proc. of the American Control Conference, Portland, Oregon (2014) 16. Zeilinger M. N., Raimondo D. M., Domahidi A., Morari M., Jones C.N.: On Real-time Robust Model Predictive Control. Automatica 50, 683-694 (2014) 17. Jerez J.L., Goulart P.J., Richter S., Constantinides G.A., Kerrigan E.C., Morari M.: Em- bedded Online Optimization for Model Predictive Control at Megahertz Rates. IEEE Trans. on Automatic Control 59, 3238 – 3251 (2014) 18. Wang Y., Boyd S.: Fast Model Predictive Control using Online Optimization. IEEE Trans. on Control Systems Technology 18, 267 –278 (2010) 19. Houska B., Ferreau H. J., Diehl M.: An Auto-generated Real-time Iteration Algorithm for Nonlinear MPC in the Microsecond Range. Automatica 47, 2279-2285 (2011) 20. Domahidi A., Zgraggen A., Zeilinger M.N., Morari M., Jones C.N.: Efficient Interior Point Methods for Multistage Problems Arising in Receding Horizon Control. In: Proc. of the CDC, 668-674, Maui, USA (2012) 21. Herceg M., Kvasnica M., Jones C.N., and Morari M.: Multi-Parametric Toolbox 3.0. In: Proc. of the European Control Conference, 502–510, Zurich, Switzerland (2013) [Элек- тронный ресурс]: URL: http://control.ee.ethz.ch/~mpt (Дата обращения: 10.07.16). 22. Нестеров, Ю.Е.: Метод решения задачи выпуклого программирования со скоростью сходимости O(1/k 2 ). Докл. АН СССР, т. 269, № 3, с. 543-548 (1983) 23. Richter S., Jones C. N., Morari M.: Real-time Input-constrained MPC using Fast Gradient Method. In: Proc. IEEE CDC (2009) 24. Richter S., Jones C., Morari M.: Computational Complexity Certification for Real-time MPC with Input Constraints Based on the Fast Gradient Method. IEEE Trans. on Automat- ic Control 57, 1391-1403 (2012) 25. Patrinos P., Bemporad A.: An Accelerated Dual Gradient-Projection Algorithm for Em- bedded Linear Model Predictive Control. IEEE Trans. on Automatic Control 59, 18-33 (2013) Проекционный алгоритм линейного программирования 193 26. Vapnik, V.: The Support Vector Method of Function Estimation. In: Suykens, J.A.K., Vandewalle, J. (eds) Nonlinear Modeling : Advanced Black-Box Techniques. chap. 3, 55– 85. Kluwer Academic Publishers, Boston (1998) 27. Bemporad A., Borrelli F., Morari M.: Model Predictive Control based on Linear Pro- gramming - the Explicit Solution. IEEE Trans. on Automatic Control 47, 1974-1985 (2002) 28. Borrelli F., Bemporad A., Morari M.: Predictive Control for Linear and Hybrid Systems. [Электронный ресурс]: URL: http://www.mpc.berkeley.edu/mpc-course-material (Дата обращения: 10.07.16) 29. Филимонов Н.Б.: Методы полиэдрального программирования в дискретных задачах управления и наблюдения. Методы классической и современной теории автоматиче- ского управления. Учебник в 5-и тт. Т. 5. Методы современной теории автоматиче- ского управления. Гл. 7. М.: Изд-во МГТУ им. Н.Э. Баумана, c. 647-720 (2004) 30. Lazar M., Jokic A.: Synthesis of Trajectory-dependent Control Lyapunov Functions by a Single Linear Program. In: Tabuada P., Majumdar R. (Eds.). Proceedings HSCC 2009, 237-251, LNCS No. 5469. Berlin: Springer (2009) 31. Нгуен Х.Н., Гутман П.О., Олару С., Ховд М.: Управление с ограничениями для ли- нейных стационарных систем: интерполяционный подход. Автоматика и телемеха- ника, № 1, c. 68-89 (2014) 32. Filimonov N.B.: Barrier Regulator Design using Polyhedral Predictive Control. In: Proc. of the IEEE International Conference “Stability and Control Processes” in memory of V.I. Zubov (SCP), 48-51, St. Petersburg (2015) 33. Акимов П.А., Деревянкин А.В., Матасов А.И.: Гарантирующий подход и l1- аппроксимация в задачах оценивания параметров БИНС при стендовых испытаниях. М.: Изд-во Московского университета (2012) 34. Bartels R.H., Conn A.R., Sinclair J.W.: Minimization Techniques for Piecewise Differen- tiable Functions: the l1-solution to an Overdetermined Linear System. SIAM J. Numer. Anal. 15, 224-241 (1978) 35. Donoho D.L. For Most Large Underdetermined Systems of Equations, the Minimal l1- norm Solution is Also the Sparsest Solution. Communications on pure and applied mathe- matics, 59, 797-829 (2006) 36. Pudlewski S., Melodia T., Prasanna A., Compressed-sensing-enabled Video Streaming for Wireless Multimedia Sensor Networks. IEEE Trans. Mobile Computing 11, 1060–1062 (2012) 37. Li S., Xu L.D., Wang X. Compressed Sensing Signal and Data Acquisition in Wireless Sensor Networks and Internet of Things. IEEE Trans. on Industrial Informatics 9, 2177- 2185 (2013) 38. Zadeh L., Whalen B.: On Optimal Control and Linear Programming. IRE Trans. on Auto- matic Control 7(4), 45-46 (1962) 39. Пропой А.И.: Применение методов линейного программирования для синтеза им- пульсных автоматических систем. Автоматика и телемеханика, № 7, c. 912-920 (1963) 40. Boley D.: Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs. SIAM J. Optim. 23, 2183–2207 (2013) 41. Циглер, Г.М.: Теория многогранников. М: МЦНМО (2014) 42. Левитин Е.С., Поляк Б.Т.: Методы минимизации при наличии ограничений. Ж. вы- числ. матем. и матем. физ., № 5, с. 787–823 (1966) 43. Beck, A., Teboulle, M.: A Conditional Gradient Method with Linear Rate of Convergence for Solving Convex Linear Systems. Math. Methods of Op. Res. 59, 235-247 (2004) 194 Максим Деменков 44. Jaggi, M.: Revisiting Frank-Wolfe: Projection-free Sparse Convex Optimization. In: JMLR Proceedings 28, 427–435. ICML, Atlanta (2013) 45. Lacoste-Julien, S., Jaggi, M.: On the Global Linear Convergence of Frank-Wolfe Optimi- zation Variants. In: Advances in Neural Information Processing Systems 28. NIPS, Mon- treal (2015) 46. Fujishige, S., Hayashi, T., Yamashita, K., Zimmermann, U.: Zonotopes and the LP- Newton Method. Optimization and Engineering 10, 193–205 (2009) 47. Helmling, M., Ruzika, S.: Towards Combinatorial LP Turbo Decoding. In: IEEE Interna- tional Symposium on Information Theory, pp. 1491-1495. IEEE Press, Istanbul (2013) 48. Kitahara, T., Mizunoa, S., Shi, J.: The LP-Newton method for standard form linear pro- gramming problems. Operations Research Letters 41, 426-429 (2013) 49. Wolfe P.: Finding the Nearest Point in a Polytope. Mathematical Programming 11, 128– 149 (1976) 50. Митчелл Б. Ф., Демьянов В. Ф., Малоземов В. Н.: Нахождение ближайшей к началу координат точки многогранника. Вестник ЛГУ., № 19, c. 38–45 (1971) 51. Лебедев В.Ю.: Приближенный алгоритм решения задачи линейного программиро- вания. Ж. вычисл. матем. и матем. физ., № 4, с. 1052–1058 (1974) 52. Лебедев В.Ю.: Декомпозиционный метод решения блочных задач линейного про- граммирования со связывающими переменными. Ж. вычисл. матем. и матем. физ.,, № 4, c. 881-886 (1981) 53. Голиков А.И., Евтушенко Ю.Г. Метод решения задач линейного программирования большой размерности. ДАН, № 6, 727-732 (2004) 54. Evtushenko Y., Golikov A.: Linear Programming Projection Algorithms. Wiley Encyclo- pedia of Operations Research and Management Science (2010) 55. Bauschke, H.H., Borwein, J.M.: Dykstra's Alternating Projection Algorithm for Two Sets. J. Approx. Theory 79, 418-443 (1994) 56. Escalante, R., Raydan, M.: Alternating Projection Methods. SIAM, Philadelphia (2011) 57. Nowak I.: Column Generation-based Alternating Direction Methods for Solving MINLPs. [Электронный ресурс]: URL: http://www.optimization-online.org/DB_HTML/2015/12/ 5233.pdf (Дата обращения: 10.07.16) Проекционный алгоритм линейного программирования 195 A Projection-type Algorithm for Linear Programming Using Line and Zonotope Intersection Maxim Demenkov Institute of Control Sciences Profsoyuznaya 65, 117997 Moscow, Russia max.demenkov@gmail.com Abstract. We study linear programming with box constraints on all variables (in addition to other linear constraints). Following research of Fujishige et al., we consider this problem as finding an intersection between a line and a spe- cially constructed zonotope. This approach allows us to explore a variety of projection-type optimization algorithms, where we do not need to rely on the solution of linear equations. Keywords: linear programming, polytopes, zonotopes, projection.