Optimization problems over tropical semifields: Algebraic solutions and application examples

Research output

Abstract

We consider multidimensional optimization problems, formulated in the framework of tropical (idempotent) mathematics to minimize or maximize functions defined on vectors over idempotent semifields. The objective functions can be linear or nonlinear in the tropical mathematics sense; the problems can have constraints in the form of tropical linear vector equalities and inequalities. We start with a brief overview of known optimization problems and existing solution methods. Some of the problems are solved directly in an explicit form under fairly general assumptions, whereas other problems have only algorithmic solutions in the form of iterative computational procedures, which produce a particular solution, or indicate that no solution exist. Furthermore, we examine new unconstrained and constrained problems with nonlinear objective functions, which are defined using multiplicative conjugate transposition of vectors. Examples include problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the tropical spectral radius of a matrix. To solve the problems, we propose new techniques based on the reduction of the problem to parametrized systems of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. By using these techniques, we offer direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. For some problems, the solutions obtained are complete solutions. Finally, applications of the results to problems in Chebyshev approximation, project scheduling, location analysis and decision making are discussed.
Original languageEnglish
Pages616
Publication statusPublished - Jul 2016
Event7th European Congress of Mathematics - Technische Universität Berlin, Berlin
Duration: 18 Jul 201622 Jul 2016
http://7ecm.de/

Conference

Conference7th European Congress of Mathematics
Abbreviated title7ECM
CountryGermany
CityBerlin
Period18/07/1622/07/16
Internet address

Fingerprint

Semifield
Optimization Problem
Chebyshev Approximation
Objective function
Spectral Radius
Idempotent
Project Scheduling
Seminorm
Transposition
Sharp Bound
Particular Solution
Approximation Problem
Nonlinear Function
Multiplicative
Equality
Exact Solution
Decision Making
Maximise

Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory
  • Management Science and Operations Research

Cite this

@conference{0e058ccfe07f41adaea86b32d792df1a,
title = "Optimization problems over tropical semifields: Algebraic solutions and application examples",
abstract = "We consider multidimensional optimization problems, formulated in the framework of tropical (idempotent) mathematics to minimize or maximize functions defined on vectors over idempotent semifields. The objective functions can be linear or nonlinear in the tropical mathematics sense; the problems can have constraints in the form of tropical linear vector equalities and inequalities. We start with a brief overview of known optimization problems and existing solution methods. Some of the problems are solved directly in an explicit form under fairly general assumptions, whereas other problems have only algorithmic solutions in the form of iterative computational procedures, which produce a particular solution, or indicate that no solution exist. Furthermore, we examine new unconstrained and constrained problems with nonlinear objective functions, which are defined using multiplicative conjugate transposition of vectors. Examples include problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the tropical spectral radius of a matrix. To solve the problems, we propose new techniques based on the reduction of the problem to parametrized systems of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. By using these techniques, we offer direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. For some problems, the solutions obtained are complete solutions. Finally, applications of the results to problems in Chebyshev approximation, project scheduling, location analysis and decision making are discussed.",
author = "Кривулин, {Николай Кимович}",
note = "7th European Congress of Mathematics, July 18-22, 2016, Technische Universit{\"a}t Berlin. Book of Abstracts; 7th European Congress of Mathematics, 7ECM ; Conference date: 18-07-2016 Through 22-07-2016",
year = "2016",
month = "7",
language = "English",
pages = "616",
url = "http://7ecm.de/",

}

TY - CONF

T1 - Optimization problems over tropical semifields: Algebraic solutions and application examples

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

N1 - 7th European Congress of Mathematics, July 18-22, 2016, Technische Universität Berlin. Book of Abstracts

PY - 2016/7

Y1 - 2016/7

N2 - We consider multidimensional optimization problems, formulated in the framework of tropical (idempotent) mathematics to minimize or maximize functions defined on vectors over idempotent semifields. The objective functions can be linear or nonlinear in the tropical mathematics sense; the problems can have constraints in the form of tropical linear vector equalities and inequalities. We start with a brief overview of known optimization problems and existing solution methods. Some of the problems are solved directly in an explicit form under fairly general assumptions, whereas other problems have only algorithmic solutions in the form of iterative computational procedures, which produce a particular solution, or indicate that no solution exist. Furthermore, we examine new unconstrained and constrained problems with nonlinear objective functions, which are defined using multiplicative conjugate transposition of vectors. Examples include problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the tropical spectral radius of a matrix. To solve the problems, we propose new techniques based on the reduction of the problem to parametrized systems of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. By using these techniques, we offer direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. For some problems, the solutions obtained are complete solutions. Finally, applications of the results to problems in Chebyshev approximation, project scheduling, location analysis and decision making are discussed.

AB - We consider multidimensional optimization problems, formulated in the framework of tropical (idempotent) mathematics to minimize or maximize functions defined on vectors over idempotent semifields. The objective functions can be linear or nonlinear in the tropical mathematics sense; the problems can have constraints in the form of tropical linear vector equalities and inequalities. We start with a brief overview of known optimization problems and existing solution methods. Some of the problems are solved directly in an explicit form under fairly general assumptions, whereas other problems have only algorithmic solutions in the form of iterative computational procedures, which produce a particular solution, or indicate that no solution exist. Furthermore, we examine new unconstrained and constrained problems with nonlinear objective functions, which are defined using multiplicative conjugate transposition of vectors. Examples include problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the tropical spectral radius of a matrix. To solve the problems, we propose new techniques based on the reduction of the problem to parametrized systems of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. By using these techniques, we offer direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. For some problems, the solutions obtained are complete solutions. Finally, applications of the results to problems in Chebyshev approximation, project scheduling, location analysis and decision making are discussed.

M3 - Abstract

SP - 616

ER -