Solution of a tropical optimization problem using matrix sparcification

Research output

1 Downloads (Pure)

Abstract

A multidimensional optimization problem, which arises in various applications in the form of minimization of span seminorm is considered in the framework of tropical (idempotent) mathematics. The problem is formulated to minimize a nonlinear function, which is defined on vectors over an idempotent semifield, given by a matrix, and calculated using multiplicative conjugate transposition. To solve the problem, we apply and develop methods of tropical optimization proposed and investigated in [1-5]. First, we find the minimum value of the objective function, and give a partial solution as a subset of vectors represented in an explicit form. We characterize all solutions to the problem by a system of simultaneous vector equation and inequality, and use this characterization to investigate properties of the solution set, which, in particular, turns out to be closed under vector addition and scalar multiplication. Furthermore, a matrix sparsification technique is developed to drop, without affecting the solution of the problem, those entries in the matrix which are below prescribed threshold values. By combining this technique with the above characterization, the previous partial solution is extended to a wider solution subset, and then to a complete solution described as a family of subsets. Finally, we offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are also presented.

References
[1] Krivulin, N. A constrained tropical optimization problem: Complete solution and application example. In G. L. Litvinov and S. N. Sergeev (eds.) Tropical and Idempotent Mathematics and Applications, Contemp. Math., vol. 616, Providence, RI: AMS, 2014, pp. 163–177.
[2] Krivulin, N. Complete solution of a constrained tropical optimization problem with application to location analysis. In P. H¨ofner, P. Jipsen, W. Kahl, M. E. M¨uller (eds.) Relational and Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 8428, Cham: Springer, 2014, pp. 362–378.
[3] Krivulin, N. Tropical optimization problems. In L. A. Petrosyan, J. V. Romanovsky, and D. W. K. Yeung (eds.) Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich, New York: Nova Sci. Publ., 2014, pp. 195–214.
[4] Krivulin, N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107–1129, 2015.
Original languageEnglish
Pages10
Publication statusPublished - 2015
Event4th International Conference on Matrix Methods in Mathematics and Applications - Skolkovo Institute of Science and Technology, Moscow
Duration: 24 Aug 201528 Aug 2015
http://matrix.inm.ras.ru/program_and_abstracts.pdf

Conference

Conference4th International Conference on Matrix Methods in Mathematics and Applications
Abbreviated titleMMMA-2015
CountryRussian Federation
CityMoscow
Period24/08/1528/08/15
Internet address

Fingerprint

Optimization Problem
Idempotent
Nonlinear Function
Subset
Optimization
Computer Science
Objective function
Vector addition
Semifield
Partial
Scalar multiplication
Seminorm
Transposition
Backtracking
Algebraic Methods
Linear Constraints
Threshold Value
Solution Set
Multiplicative
Economics

Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory

Cite this

Кривулин, Н. К. (2015). Solution of a tropical optimization problem using matrix sparcification. 10. Abstract from 4th International Conference on Matrix Methods in Mathematics and Applications, Moscow, .
Кривулин, Николай Кимович. / Solution of a tropical optimization problem using matrix sparcification. Abstract from 4th International Conference on Matrix Methods in Mathematics and Applications, Moscow, .
@conference{4c51712d882c433aadeade612178fe73,
title = "Solution of a tropical optimization problem using matrix sparcification",
abstract = "A multidimensional optimization problem, which arises in various applications in the form of minimization of span seminorm is considered in the framework of tropical (idempotent) mathematics. The problem is formulated to minimize a nonlinear function, which is defined on vectors over an idempotent semifield, given by a matrix, and calculated using multiplicative conjugate transposition. To solve the problem, we apply and develop methods of tropical optimization proposed and investigated in [1-5]. First, we find the minimum value of the objective function, and give a partial solution as a subset of vectors represented in an explicit form. We characterize all solutions to the problem by a system of simultaneous vector equation and inequality, and use this characterization to investigate properties of the solution set, which, in particular, turns out to be closed under vector addition and scalar multiplication. Furthermore, a matrix sparsification technique is developed to drop, without affecting the solution of the problem, those entries in the matrix which are below prescribed threshold values. By combining this technique with the above characterization, the previous partial solution is extended to a wider solution subset, and then to a complete solution described as a family of subsets. Finally, we offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are also presented.References[1] Krivulin, N. A constrained tropical optimization problem: Complete solution and application example. In G. L. Litvinov and S. N. Sergeev (eds.) Tropical and Idempotent Mathematics and Applications, Contemp. Math., vol. 616, Providence, RI: AMS, 2014, pp. 163–177.[2] Krivulin, N. Complete solution of a constrained tropical optimization problem with application to location analysis. In P. H¨ofner, P. Jipsen, W. Kahl, M. E. M¨uller (eds.) Relational and Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 8428, Cham: Springer, 2014, pp. 362–378.[3] Krivulin, N. Tropical optimization problems. In L. A. Petrosyan, J. V. Romanovsky, and D. W. K. Yeung (eds.) Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich, New York: Nova Sci. Publ., 2014, pp. 195–214.[4] Krivulin, N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107–1129, 2015.",
author = "Кривулин, {Николай Кимович}",
year = "2015",
language = "English",
pages = "10",
note = "4th International Conference on Matrix Methods in Mathematics and Applications, MMMA-2015 ; Conference date: 24-08-2015 Through 28-08-2015",
url = "http://matrix.inm.ras.ru/program_and_abstracts.pdf",

}

Solution of a tropical optimization problem using matrix sparcification. / Кривулин, Николай Кимович.

2015. 10 Abstract from 4th International Conference on Matrix Methods in Mathematics and Applications, Moscow, .

Research output

TY - CONF

T1 - Solution of a tropical optimization problem using matrix sparcification

AU - Кривулин, Николай Кимович

PY - 2015

Y1 - 2015

N2 - A multidimensional optimization problem, which arises in various applications in the form of minimization of span seminorm is considered in the framework of tropical (idempotent) mathematics. The problem is formulated to minimize a nonlinear function, which is defined on vectors over an idempotent semifield, given by a matrix, and calculated using multiplicative conjugate transposition. To solve the problem, we apply and develop methods of tropical optimization proposed and investigated in [1-5]. First, we find the minimum value of the objective function, and give a partial solution as a subset of vectors represented in an explicit form. We characterize all solutions to the problem by a system of simultaneous vector equation and inequality, and use this characterization to investigate properties of the solution set, which, in particular, turns out to be closed under vector addition and scalar multiplication. Furthermore, a matrix sparsification technique is developed to drop, without affecting the solution of the problem, those entries in the matrix which are below prescribed threshold values. By combining this technique with the above characterization, the previous partial solution is extended to a wider solution subset, and then to a complete solution described as a family of subsets. Finally, we offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are also presented.References[1] Krivulin, N. A constrained tropical optimization problem: Complete solution and application example. In G. L. Litvinov and S. N. Sergeev (eds.) Tropical and Idempotent Mathematics and Applications, Contemp. Math., vol. 616, Providence, RI: AMS, 2014, pp. 163–177.[2] Krivulin, N. Complete solution of a constrained tropical optimization problem with application to location analysis. In P. H¨ofner, P. Jipsen, W. Kahl, M. E. M¨uller (eds.) Relational and Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 8428, Cham: Springer, 2014, pp. 362–378.[3] Krivulin, N. Tropical optimization problems. In L. A. Petrosyan, J. V. Romanovsky, and D. W. K. Yeung (eds.) Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich, New York: Nova Sci. Publ., 2014, pp. 195–214.[4] Krivulin, N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107–1129, 2015.

AB - A multidimensional optimization problem, which arises in various applications in the form of minimization of span seminorm is considered in the framework of tropical (idempotent) mathematics. The problem is formulated to minimize a nonlinear function, which is defined on vectors over an idempotent semifield, given by a matrix, and calculated using multiplicative conjugate transposition. To solve the problem, we apply and develop methods of tropical optimization proposed and investigated in [1-5]. First, we find the minimum value of the objective function, and give a partial solution as a subset of vectors represented in an explicit form. We characterize all solutions to the problem by a system of simultaneous vector equation and inequality, and use this characterization to investigate properties of the solution set, which, in particular, turns out to be closed under vector addition and scalar multiplication. Furthermore, a matrix sparsification technique is developed to drop, without affecting the solution of the problem, those entries in the matrix which are below prescribed threshold values. By combining this technique with the above characterization, the previous partial solution is extended to a wider solution subset, and then to a complete solution described as a family of subsets. Finally, we offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. Numerical examples and graphical illustrations of the results are also presented.References[1] Krivulin, N. A constrained tropical optimization problem: Complete solution and application example. In G. L. Litvinov and S. N. Sergeev (eds.) Tropical and Idempotent Mathematics and Applications, Contemp. Math., vol. 616, Providence, RI: AMS, 2014, pp. 163–177.[2] Krivulin, N. Complete solution of a constrained tropical optimization problem with application to location analysis. In P. H¨ofner, P. Jipsen, W. Kahl, M. E. M¨uller (eds.) Relational and Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 8428, Cham: Springer, 2014, pp. 362–378.[3] Krivulin, N. Tropical optimization problems. In L. A. Petrosyan, J. V. Romanovsky, and D. W. K. Yeung (eds.) Advances in Economics and Optimization: Collected Scientific Studies Dedicated to the Memory of L. V. Kantorovich, New York: Nova Sci. Publ., 2014, pp. 195–214.[4] Krivulin, N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107–1129, 2015.

M3 - Abstract

SP - 10

ER -

Кривулин НК. Solution of a tropical optimization problem using matrix sparcification. 2015. Abstract from 4th International Conference on Matrix Methods in Mathematics and Applications, Moscow, .