论文标题
热带多项式优化问题的代数解
Algebraic solution of tropical polynomial optimization problems
论文作者
论文摘要
我们考虑在热带代数设置中定义的约束优化问题，在线性有序的，代数完整的（可放射）的diDempotent semifield（具有diDempotent添加和可逆乘法的半静态）中。问题是最大程度地减少由多元PUISEUX多项式的热带类似物给出的目标函数，但要受到变量的框限制。提出了一种用于可变消除的技术，将原始优化问题转换为一个新变量，其中一个变量被删除，并修改了该变量的框约束。新型方法可能被认为是在有序的热带半场中多项式优化问题的线性不平等系统中傅立叶 - 摩托金消除方法的扩展。我们使用此技术来开发一种程序来解决有限数量的迭代中的问题。该过程包括两个阶段：向后消除和前向变量的替代。我们描述了该过程的主要步骤，讨论其计算复杂性并提供了数值示例。
We consider constrained optimization problems defined in the tropical algebra setting on a linearly ordered, algebraically complete (radicable) idempotent semifield (a semiring with idempotent addition and invertible multiplication). The problems are to minimize the objective functions given by tropical analogues of multivariate Puiseux polynomials, subject to box constraints on the variables. A technique for variable elimination is presented that converts the original optimization problem to a new one in which one variable is removed and the box constraint for this variable is modified. The novel approach may be thought of as an extension of the Fourier-Motzkin elimination method for systems of linear inequalities in ordered fields to the issue of polynomial optimization in ordered tropical semifields. We use this technique to develop a procedure to solve the problem in a finite number of iterations. The procedure includes two phases: backward elimination and forward substitution of variables. We describe the main steps of the procedure, discuss its computational complexity and present numerical examples.
