Solving multidimensional optimization problems over tropical semifields

Research output

Abstract

We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.
Original languageEnglish
Pages2
Publication statusPublished - 2015
EventSIAM Conference on Applied Algebraic Geometry - National Institute for Mathematical Sciences, Daejeon
Duration: 3 Aug 20157 Aug 2015
https://camp.nims.re.kr/activities/eventpages/?id=200&action=overview

Conference

ConferenceSIAM Conference on Applied Algebraic Geometry
Abbreviated titleSIAM AG15
CountryKorea, Republic of
CityDaejeon
Period3/08/157/08/15
Internet address

Fingerprint

Semifield
Optimization Problem
Chebyshev Approximation
Objective function
Spectral Radius
Semimodule
Project Scheduling
Seminorm
Transposition
Sharp Bound
Particular Solution
Approximation Problem
Equality Constraints
Inequality Constraints
Nonlinear Function
Idempotent
Multiplicative

Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory

Cite this

Кривулин, Н. К. (2015). Solving multidimensional optimization problems over tropical semifields. 2. Abstract from SIAM Conference on Applied Algebraic Geometry, Daejeon, .
@conference{17bf2f97672d45ad96ab242eea982fdf,
title = "Solving multidimensional optimization problems over tropical semifields",
abstract = "We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.",
author = "Кривулин, {Николай Кимович}",
year = "2015",
language = "English",
pages = "2",
note = "SIAM Conference on Applied Algebraic Geometry, SIAM AG15 ; Conference date: 03-08-2015 Through 07-08-2015",
url = "https://camp.nims.re.kr/activities/eventpages/?id=200&action=overview",

}

Solving multidimensional optimization problems over tropical semifields. / Кривулин, Николай Кимович.

2015. 2 Abstract from SIAM Conference on Applied Algebraic Geometry, Daejeon, .

Research output

TY - CONF

T1 - Solving multidimensional optimization problems over tropical semifields

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

PY - 2015

Y1 - 2015

N2 - We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.

AB - We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.

M3 - Abstract

SP - 2

ER -

Кривулин НК. Solving multidimensional optimization problems over tropical semifields. 2015. Abstract from SIAM Conference on Applied Algebraic Geometry, Daejeon, .