Direct multiplicative methods for sparse matrices. Newton methods

 pdf (493K)  / Annotation

List of references:

  1. В. Л. Береснев. Дискретные задачи размещения и полиномы от булевых переменных. — Новосибирск: Изд-во ин-та математики, 2005. — 408 с.
    • V. L. Beresnev. Discrete location problems and polynomials of Boolean variables. — Novosibirsk: The publisher of the Institute of mathematics, 2005. — 408 p. — in Russian.
  2. В. Л. Береснев. Алгоритмы минимизации полиномов от булевых переменных // Проблемы кибернетики. — М: Наука, 1979. — № 36. — С. 225–246. — zbMATH: Zbl 0447.94028.
    • V. L. Beresnev. Algorithms for minimization of polynomials in Boolean variables // Problems of Cybernetics. — Moscow: Nauka, 1979. — V. 36. — P. 225–246. — in Russian. — MathSciNet: MR0568455. — zbMATH: Zbl 0447.94028.
  3. В. Л. Береснев, Э. Х. Гимади, В. Т. Дементьев. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978.
    • V. L. Beresnev, Je. H. Gimadi, V. T. Dement'ev. Extremal problems of standardization. — Novosibirsk: Nauka, 1978. — in Russian.
  4. Ф. Гилл, У. Мюррей. Численные методы условной оптимизации. — М: Мир, 1977.
    • F. Gill, U. Mjurrej. Chislennye metody uslovnoj optimizacii. — Moscow: Mir, 1977. — in Russian.
    • Ph. E. Gill, W. Murray. Numerical methods for constrained optimization. — National physical laboratory Teddington, Middlesex. — Academic Press, 1974. — MathSciNet: MR0395227.
  5. Ф. Гилл, У. Мюррей, М. Райт. Практическая оптимизация. — М: Мир, 1985.
    • F. Gill, U. Mjurrej, M. Rajt. Prakticheskaja optimizacija. — Moscow: Mir, 1985. — in Russian. — MathSciNet: MR0801546.
    • Ph. E. Gill, W. Murray, M. H. Wright. Practical optimization. — System Optimization Laboratory Department of Operations Research Stanford University California, USA. — Academic Press, 1981. — MathSciNet: MR0634376. — zbMATH: Zbl 0503.90062.
  6. О. Н. Григорьева, О. А. Дмитриева. Моделирование линейных динамических систем большой размерности с разреженными матрицами коэффициентов / Информатика и компьютерные технологии-2011. — Донецк: Донецкий национальный технический университет, 2011. — С. 199–203.
    • O. N. Grigor'eva, O. A. Dmitrieva. Modeling linear dynamical systems of high dimension with sparse matrices of coefficients / Informatics and computer technologies-2011. — Donetsk: Donetsk national technical University, 2011. — P. 199–203. — in Russian.
  7. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М: Мир, 1982.
    • M. Gjeri, D. Dzhonson. Computers and trudnoreshaemyh tasks. — Moscow: Mir, 1982. — in Russian. — MathSciNet: MR0701247.
  8. А. Джордж, Дж. Лю. Численное решение больших разреженных систем уравнений. — М: Мир, 1984.
    • A. George, J. W.-H. Liu. Computer solution of large sparse positive definite systems. — Englewood Cliffs, Ne Jersey: Prentice-Hall, Inc, 1981. — MathSciNet: MR0646786. — zbMATH: Zbl 0516.65010.
    • A. Dzhordzh, Dzh. Lju. Chislennoe reshenie bol'shih razrezhennyh sistem uravnenij. — Moscow: Mir, 1984. — in Russian. — MathSciNet: MR0741997.
  9. О. А. Дмитриева. Оптимизация выполнения матрично-векторных операций при параллельном моделировании динамических процессов // Науковi працi ДонНТУ. Сер. Обчислювальна технiка та автоматизацiя. — 2014. — № 1(26). — С. 94–100.
    • O. A. Dmitrieva. Optimization of performance of matrix and vector operations at parallel simulation of dynamic processes // Donetsk National Technical University. — 2014. — no. 1(26). — P. 94–100. — in Russian.
  10. Г. А. Зеленков, А. Б. Хакимова. Подход к разработке алгоритмов ньютоновских методов оптимизации, программная реализация и сравнение эффективности // Компьютерные исследования и моделирование. — 2013. — Т. 5, № 3. — С. 367–377. — DOI: 10.20537/2076-7633-2013-5-3-367-377
    • G. A. Zelenkov, A. B. Hakimova. Approach to development of algorithms of Newtonian methods of unconstrained optimization, their software implementation and benchmarking // Computer Research and Modeling. — 2013. — V. 5, no. 3. — P. 367–377. — in Russian. — С. 367–377. — DOI: 10.20537/2076-7633-2013-5-3-367-377
  11. И. Г. Казанцев. О конструктивном вычислении сечений многомерного куба // Интерэкспо Гео-Сибирь. — 2012. — Т. 1, № 4. — С. 168–171.
    • I. G. Kazancev. Оn a constructive computation of the section of hypercube // Interjekspo Geo-Sibir'. — 2012. — V. 1, no. 4. — P. 168–171.
  12. В. Г. Карманов. Математическое программирование. — М: Мир, 1975.
    • V. G. Karmanov. Mathematical programming. — Moscow: Mir, 1975. — in Russian. — MathSciNet: MR0411559.
  13. Ю. А. Кочетов, А. В. Плясунов. Локальный поиск в комбинаторной оптимизации. Нужна ли производная? / Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения», 2–8.07.2005. — Том 1: Иркутск – ИСЭМ СО РАН, 2005. — С. 65–76.
    • Yu. A. Kochetov, A. V. Pljasunov. Local search in combinatorial optimization. What about the derivative? // Mathematical programming: Proceedings of XIII Baikal International School-seminar “Optimization methods and their applications”, July, 2–8, Irkutsk, Baikal, 2005. — Irkutsk: Melentiev Energy Systems Institute SB RAS, 2005. — V. 1. — P. 65–76. — in Russian.
  14. И. С. Масич. Задачи оптимизации и их свойства в логических алгоритмах распознавания / Проблемы оптимизации и экономические приложения: материалы V Всероссийской конференции. — Омск: Изд-во Ом. гос. ун-та, 2012.
    • I. S. Masich. Optimization problems and their properties in logical recognition algorithms / Optimization problems and economic applications: proceedings of the V all-Russian conference. — Omsk: Publishing house of Om. state University, 2012. — in Russian.
  15. И. С. Масич. Комбинаторная оптимизация и логические алгоритмы классификации в задаче прогнозирования осложнений инфаркта миокарда / Инновационные тенденции развития российской науки: материалы III Международной научно-практической конференции. — Красноярск, 2010. — С. 276–280.
    • I. S. Masich. Combinatorial optimization and Boolean classification algorithms in the task of predicting complications of myocardial infarction / Innovative trends in the development of Russian science: materials of III International scientific-practical conference. — Krasnoyarsk, 2010. — P. 276–280. — in Russian.
  16. В. С. Михалевич, В. А. Трубин, Н. З. Шор. Оптимизационные задачи производственно-транспортного планирования. — М: Наука, 1986.
    • V. S. Mihalevich, V. A. Trubin, N. Z. Shor. Optimization problems of production-transportation planning. — Moscow: Nauka, 1986. — in Russian. — MathSciNet: MR0897753.
  17. Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. — М: Мир, 1985.
    • H. Papadimitriou Christos. Combinatorial optimization: Algorithms and Complexity. — Massachusetts Institute of Technology. National Technical University of Athens. — Englewood Cliffs — New Jersey: Prentice-Hall Inc, 1982. — MathSciNet: MR0663728. — zbMATH: Zbl 0503.90060.
    • H. Papadimitriu, K. Stajglic. Kombinatornaja optimizacija. Algoritmy i slozhnost'. — Moscow: Mir, 1985. — in Russian.
  18. Б. Парлетт. Симметричная проблема собственных значений. Численные методы. — М: Мир, 1983.
    • B. N. Parlett. The symmetric eigenvalue problem. — California: University of California Berkeley, 1980. — MathSciNet: MR1490034.
    • B. Parlett. Simmetrichnaja problema sobstvennyh znachenij. Chislennye metody. — Moscow: Mir, 1983. — in Russian. — MathSciNet: MR0702348.
  19. С. Писсанецки. Технология разреженных матриц: Пер. с англ. — М: Мир, 1988. — 410 с.
    • S. Pissanetzky. Sparse matrix technology. — Academic Press Inc, 1984. — MathSciNet: MR0751237. — zbMATH: Zbl 0536.65019.
    • S. Pissanecki. Tehnologija razrezhennyh matric. — Moscow: Mir, 1988. — in Russian. — MathSciNet: MR0954834.
  20. Э. Полак. Численные методы оптимизации. Единый подход. — М: Мир, 1974.
    • Polak E.. . Computation methods in optimization / Mathematics in Science and Engineering. — New York, London: Academic Press, 1971. — V. 77. — MathSciNet: MR0282511.
    • Je. Polak. Chislennye metody optimizacii. Edinyj podhod. — Moscow: Mir, 1974. — in Russian.
  21. Б. Т. Поляк. Метод Ньютона и его роль в оптимизации и вычислительной математике // Труды ИСА РАН. — 2006. — Т. 28. — С. 48–66.
    • B. T. Poljak. Newton's method and its role in optimization and computational mathematics // Proceedings of ISA RAS. — 2006. — V. 28. — P. 48–66. — in Russian.
  22. Б. Н. Пшеничный, Ю. М. Данилин. Численные методы в экстремальных задачах. — М: Наука, 1975.
    • B. N. Pshenichnyj, Yu. M. Danilin. Numerical methods in extremal problems. — Moscow: Nauka, 1975. — in Russian. — MathSciNet: MR0502886.
  23. Свириденко А. Б.. . Априорная поправка в ньютоновских методах оптимизации // Компьютерные исследования и моделирование. — 2015. — Т. 7, № 4. — С. 835–863. — DOI: 10.20537/2076-7633-2015-7-4-835-863
    • A. B. Sviridenko. The correction to Newton's methods of optimization // Computer Research and Modeling. — 2015. — V. 7, no. 4. — P. 835–863. — in Russian. — DOI: 10.20537/2076-7633-2015-7-4-835-863
  24. А. Б. Свириденко. Прямые мультипликативные методы для разреженных матриц. Несимметричные линейные системы // Компьютерные исследования и моделирование. — 2016. — Т. 8, № 6. — С. 833–860. — DOI: 10.20537/2076-7633-2016-8-6-833-860
    • A. B. Sviridenko. Direct multiplicative methods for sparse matrices. Unbalanced linear systems // Computer research and modeling. — 2016. — V. 8, no. 6. — P. 833–860. — in Russian. — DOI: 10.20537/2076-7633-2016-8-6-833-860
  25. А. Б. Свириденко. Прямые мультипликативные методы для разреженных матриц. Линейное программирование // Компьютерные исследования и моделирование. — 2017. — Т. 9, № 2. — С. 143–165. — DOI: 10.20537/2076-7633-2017-9-2-143-165
    • A. B. Sviridenko. Direct multiplicative methods for sparse matrices. Linear Programming // Computer research and modeling. — 2017. — V. 9, no. 2. — P. 143–165. — in Russian. — DOI: 10.20537/2076-7633-2017-9-2-143-165.
  26. А. Б. Свириденко, Г. А. Зеленков. Взаимосвязь и реализация квазиньютоновских и ньютоновских методов безусловной оптимизации // Компьютерные исследования и моделирование. — 2016. — Т. 8, № 1. — С. 55–78. — DOI: 10.20537/2076-7633-2016-8-1-55-78
    • A. B. Sviridenko, G. A. Zelenkov. Correlation and realization of quasi-Newton methods of absolute optimization // Computer Research and Modeling. — 2016. — V. 8, no. 1. — P. 55–78. — in Russian. — DOI: 10.20537/2076-7633-2016-8-1-55-78
  27. А. В. Селиверстов. О мономах квадратичных форм // Дискрет. анализ и исслед. операций. — 2013. — Т. 20, № 3. — С. 65–70.
    • A. V. Seliverstov. On monomials quadratic forms // Discrete analysis and operations research. — 2013. — V. 20, no. 3. — P. 65–70. — in Russian. — Math-Net: Mi eng/da732. — MathSciNet: MR3135744. — zbMATH: Zbl 1324.90183.
  28. Г. Стренг. Линейная алгебра и ее применения. — М: Мир, 1980.
    • G. Strang. Linear algebra and its applications. — New York, San Francisco, London: Academic Press, 1976. — MathSciNet: MR0384823. — zbMATH: Zbl 0338.15001.
    • G. Streng. Linejnaja algebra i ee primenenija. — Moscow: Mir, 1980. — MathSciNet: MR0596578.
  29. А. Б. Хакимова, В. В. Дикусар, Г. А. Зеленков. Увеличение эффективности ньютоновских методов оптимизации. Информодинамический подход // Труды ИСА РАН «Динамика неоднородных систем». — М: Книжный дом «ЛИБРОКОМ», 2010. — Т. 53, № 14-А. — С. 97–114.
    • A. B. Khakimova, V. V. Dikusar, G. A. Zelenkov. Increasing the efficiency of the Newtonian methods of optimization. Informationmicardis approach // The works of ISA Russian Academy of Sciences “Dynamics of heterogeneous systems”. — Moscow: Book house “LIBROKOM”, 2010. — V. 53, no. 14-A. — P. 97–114. — in Russian.
  30. А. Б. Хакимова, Г. А. Зеленков, И. Г. Рзун. Подход к увеличению эффективности мультипликативного алгоритма симплекс-метода // Труды ИСА РАН «Динамика неоднородных систем». — М: Книжный дом «ЛИБРОКОМ», 2010. — Т. 53(2), № 14. — С. 245–251.
    • A. B. Khakimova, G. A. Zelenkov, I. G. Rzun. Approach to increase the efficiency of the multiplicative algorithm of the simplex method // The works of ISA Russian Academy of Sciences “Dynamics of heterogeneous systems”. — 2010. — V. 53(2), no. 14. — P. 245–251. — in Russian.
  31. А. Б. Хакимова, Б. Б. Хакимов. Единый подход к решению задач математического программирования гуманитарной компьютерной клиники / Сборник статей I-й Международной конференции «Системные, информационные и технические средства и технологии в профессиональной деятельности, образовании, оздоровлении и профилактике». — Санкт-Петербург, 2003. — С. 88–92.
    • A. B. Khakimova, B. B. Khakimov. A unified approach to the solution of problems of mathematical programming Humanities computer clinic / A collection of articles I international conference “System, information and technical tools and technologies in their professional activities, education, rehabilitation and prevention”. — Saint-Petersburg, 2003. — P. 88–92. — in Russian.
  32. Г. М. Циглер. Теория многогранников. — М: Изд-во МЦНМО, 2014.
    • G. M. Ziegler. Lectures on Polytopes. — New York: Springer-Verlag Inc, 1995. — MathSciNet: MR1311028. — zbMATH: Zbl 0823.52002.
    • G. M. Cigler. Teorija mnogogrannikov. — Moscow: Izd-vo MCNMO, 2014.
  33. И. Г. Черноруцкий. Методы оптимизации. Компьютерные технологии. — СПб: БХВ-Петербург, 2011. — 384 с.
    • I. G. Chernoruckij. Methods of optimization. Computer technology. — St. Petersburg: BHV-Petersburg, 2011. — 384 p. — in Russian.
  34. И. Г. Черноруцкий. Практическая оптимизация и невыпуклые задачи // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. — СПб: Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский политехнический университет Петра Великого», 2013. — № 4(176). — С. 79–86.
    • I. G. Chernoruckij. Practical optimization and nonconvex problems // Nauchno-tekhnicheskie Vedomosti SPbGPU. Informatics. Telecommunications. Management. — St. Petersburg: Federal state Autonomous educational institution of higher professional education “Saint-Petersburg Polytechnic University Peter the Great”, 2013. — no. 4(176). — P. 79–86. — in Russian.
  35. Д. Б. Юдин, А. П. Горяшко, А. С. Немировский. Математические методы оптимизации устройств и алгоритмов АСУ. — М: Радио и связь, 1982. — 288 с.
    • D. B. Judin, A. P. Gorjashko, A. S. Nemirovskij. Mathematical methods for optimization of devices and algorithms ACS. — Moscow: Radio and communication, 1982. — in Russian. — MathSciNet: MR0690421.
  36. F. Barahona, M. Grotschel, M. Junger, G. Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design // Operation Research. — 1988. — no. 36. — P. 493–513. — DOI: 10.1287/opre.36.3.493. — MathSciNet: MR3114998. — zbMATH: Zbl 0646.90084.
  37. A. I. Barros, M. Labbe. A general model for the uncapacitated facility and depot location problem // Location Science. — 1994. — V. 2, no. 3. — P. 173–191. — MathSciNet: MR2695997. — zbMATH: Zbl 0919.90097.
  38. Y. Crama. Combinatorial Optimization Models for Production Scheduling in Automated Manufacturing Systems // European Journal of Operational Research. — 1997. — no. 99. — P. 136–153. — DOI: 10.1016/S0377-2217(96)00388-8. — zbMATH: Zbl 0923.90066.
  39. Y. Crama, P. L. Hammer. Bimatroidal independence systems // Mathematical Methods of Operations Research. — 1989. — V. 33, no. 3. — P. 149–165. — DOI: 10.1007/BF01423645. — MathSciNet: MR1000172. — zbMATH: Zbl 0681.05016.
  40. Y. Crama, P. L. Hammer. Boolean Functions: Theory, Algorithms, and Applications. — New York: Cambridge University Press, 2011. — 687 p. — MathSciNet: MR2742439. — zbMATH: Zbl 1237.06001.
  41. Ch. Ebenegger, P. L. Hammer, D. de Werra. Pseudo-Boolean Functions and Stability of Graphs // Annals of Discrete Mathematics. — 1984. — no. 19. — P. 83–97. — MathSciNet: MR0780014.
  42. A. S. Fraenkel, P. L. Hammer. Pseudo-Boolean functions and their graphs // Annals of Discrete Mathematics. — 1984. — no. 20. — P. 137–146. — MathSciNet: MR0791023. — zbMATH: Zbl 0557.94019.
  43. P. E. Gill, W. Murray. Newton-type methods for unconstrained and linearly constrained optimization // Math. Prog. — 1974. — V. 7. — P. 311–350. — DOI: 10.1007/BF01585529. — MathSciNet: MR0356503. — zbMATH: Zbl 0297.90082.
  44. P. L. Hammer. Pseudo-Boolean Remarks on Balanced Graphs // International Series of Numerical Mathematics. — 1977. — no. 36. — P. 69–78. — MathSciNet: MR0465947. — zbMATH: Zbl 0405.05054.
  45. P. L. Hammer, P. Hansen, B. Simeone. Upper planes of quadratic 0-1 functions and stability in graphs // Nonlinear Programming. — 1981. — no. 4. — P. 395–414. — MathSciNet: MR0663387. — zbMATH: Zbl 0534.90062.
  46. P. L. Hammer, S. Rudeanu. Boolean Methods in Operations Research and Related Areas. — Berlin: Springer-Verlag; New York: Heidelberg, 1968. — 310 p. — MathSciNet: MR0235830. — zbMATH: Zbl 0155.28001.
  47. P. L. Hammer, E. Shliffer. Applications of Pseudo-Boolean Methods to Economic Problems // Theory and decision. — 1971. — no. 1. — P. 296–308. — DOI: 10.1007/BF00139572. — zbMATH: Zbl 0217.26702.
  48. F. S. Hillier. The Evaluation of Risky Interrelated Investments. — Amsterdam: North-Holland Publishing, 1969.
  49. R. M. Karp, R. G. Miller, J. W. Thatcher. Reducibility Among Combinatorial Problems // Journal of Symbolic Logic. — 1975. — no. 40(4). — P. 618–619.
  50. D. J. Laughhunn. Quadratic Binary Programming with Applications to Capital Budgeting Problems // Operations Research. — 1970. — no. 18. — P. 454–461. — DOI: 10.1287/opre.18.3.454. — zbMATH: Zbl 0193.20209.
  51. D. J. Laughhunn, D. E. Peterson. Computational Experience with Capital Expenditure Programming Models under Risk // Business Finance. — 1971. — no. 3. — P. 43–48.
  52. J. Nieminen. A linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory // Zastosowania Matematyki. — 1974. — no. 14. — P. 365–369. — MathSciNet: MR0359825. — zbMATH: Zbl 0296.90049.
  53. R. H. Ranyard. An Algorithm for Maximum Likelihood Ranking and Slater’s i From Paired Comparisions // British Journal of Mathematical and Statistical Psychology. — 1976. — no. 29. — P. 242–248. — DOI: 10.1111/j.2044-8317.1976.tb00715.x. — zbMATH: Zbl 0351.62054.
  54. M. R. Rao. Cluster Analysis and Mathematical Programming // Journal of the American Statistical Association. — 1971. — V. 66. — P. 622–626. — DOI: 10.1080/01621459.1971.10482319. — zbMATH: Zbl 0238.90042.
  55. A. Schrijver. Theory of linear and integer programming. — Wiley-interscience series in discrete mathematics. Department of econometrics, Tilburg University and Centrum voor Wiskunde en informatica. — Amsterdam: A Wiley-interscience publication, 1986. — MathSciNet: MR0874114. — zbMATH: Zbl 0665.90063.
  56. H. M. Weingartner. Capital Budgeting of Interrelated Projects: Survey and Synthesis // Management Science. — 1966. — no. 12. — P. 485–516. — DOI: 10.1287/mnsc.12.7.485.
  57. D. J. A. Welsh. Matroid theory. — London: Academic Press, 1976.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"