### Abstract

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. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107-1129, 2015.

[3] Krivulin, N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl., vol. 468, pp. 211-232, 2015.

Original language | English |
---|---|

Pages | 10-10 |

Publication status | Published - Aug 2015 |

Event | 4th International Conference on Matrix Methods in Mathematics and Applications - Skolkovo Institute of Science and Technology, Moscow Duration: 24 Aug 2015 → 28 Aug 2015 http://matrix.inm.ras.ru/program_and_abstracts.pdf |

### Conference

Conference | 4th International Conference on Matrix Methods in Mathematics and Applications |
---|---|

Abbreviated title | MMMA-2015 |

Country | Russian Federation |

City | Moscow |

Period | 24/08/15 → 28/08/15 |

Internet address |

### Fingerprint

### Scopus subject areas

- Algebra and Number Theory

### Cite this

*Solution of a tropical optimization problem using matrix sparsification*. 10-10. Abstract from 4th International Conference on Matrix Methods in Mathematics and Applications, Moscow, .

}

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

Research output

TY - CONF

T1 - Solution of a tropical optimization problem using matrix sparsification

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

N1 - 4th International Conference on Matrix Methods in Mathematics and Applications (MMMA-2015). Program and Abstracts

PY - 2015/8

Y1 - 2015/8

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-3]. 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 in a compact vector form.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. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107-1129, 2015.[3] Krivulin, N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl., vol. 468, pp. 211-232, 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-3]. 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 in a compact vector form.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. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization, vol. 64, no. 5, pp. 1107-1129, 2015.[3] Krivulin, N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl., vol. 468, pp. 211-232, 2015.

M3 - Abstract

SP - 10

EP - 10

ER -