Activities per year
First, we present problems that have linear objective functions and thus are idempotent analogues of those in conventional linear programming. Then, problems with nonlinear objective functions are examined, including Chebyshev and Chebyshev-like approximation problems, problems with minimization and maximization of span seminorm, and problems that involve the evaluation of the spectral radius of a matrix. Some of these problems admit complete direct solutions given in an explicit vector form. The known solutions to other problems are obtained in an indirect form of iterative algorithms that produce a particular solution if any or show that there is no solution.
Furthermore, we consider new optimization problems that extend certain known problems to take into account more general objective functions and more complicated systems of constraints. To obtain direct, explicit solutions to the new problems, we propose algebraic approaches, which offer the results in a compact vector form that is suitable for both further analysis and practical implementation, and guarantees low computational complexity of the solutions. For many problems, the approaches yield complete solutions to the problems of interest. The solution of certain problems without constraints involves obtaining sharp lower or upper bounds for the objective function. We use the bound in an equation for the function, which is solved to find all vectors that yield the bound. To extend the solution to problems with linear equation and inequality constraints, we first obtain a general solution to the equation or inequality, and then substitute it into the function to arrive at one of the unconstrained problems with known solution. To solve other problems, with and without constraints, we introduce an auxiliary variable to indicate the minimum value of the objective function. The problem is reduced to the solving of a linear inequality with a parameterized matrix, where the auxiliary variable plays the role of a parameter. We exploit the existence condition for solutions of the inequality to evaluate the parameter, and then take the general solution of the inequality as a complete solution to the initial optimization problem. We conclude with a brief discussion of application of the result to solve real-world problems in job scheduling, location analysis, decision making and other fields.
|State||Published - 2014|
|Event||The 19th International Linear Algebra Society (ILAS) Conference - Seoul, Korea, Republic of|
Duration: 6 Aug 2014 → 9 Aug 2014
|Conference||The 19th International Linear Algebra Society (ILAS) Conference|
|Country||Korea, Republic of|
|Period||6/08/14 → 9/08/14|
Scopus subject areas
- tropical algebra
- idempotent semifield
- optimization problem
- nonlinear objective function
- linear constraint
Николай Кимович Кривулин (Speaker)6 Aug 2014
Activity: Talk types › Oral presentation
Николай Кимович Кривулин (Participant)6 Aug 2014 → 9 Aug 2014
Activity: Attendance types › Participating in a conference, workshop, ...