极大代数上的双边线性系统的优化

The theory of linear systems over max algebra provides important tools for the analysis and control of discrete event systems and the design of fuzzy control systems. The optimization of linear systems over max algebra has attracted much attention in recent years, where some basic problems, particularly those constrained by two-sided linear equations, have not been completely solved. The study of these problems would advance our understanding of the nature of some nonlinear systems that can be modeled by discrete event systems or fuzzy control systems. In this research project, we will focus on solving two-sided linear equation constrained optimization problems with linear or quadratic objective functions in usual sense. By introducing new variables to characterize the structure of a system of two-sided linear equations via decomposition and reconstruction, the original optimization problems may be transformed into linear or nonlinear mixed integer programming problems and then solved or approximately solved by specifically designed algorithms. We will also explore the connection between the two-sided linear equation constrained optimization problems and the problem of obtaining approximate solutions of one-sided linear equations, and subsequently solve this problem in the framework of two-sided linear equation constrained optimization. Besides, we will deal with the two-sided linear equation constrained optimization problem with a latticized linear objective function and check whether such a problem can be solved in polynomial time.

极大代数上的线性系统理论是离散事件系统分析和控制以及模糊控制系统设计的重要工具。极大代数上的线性系统的优化问题是最近的一个研究热点，目前，一些基本问题，特别是双边线性方程的求解与优化，仍未完全解决。对于这些问题的研究有助于加深理解一些可由离散事件系统和模糊控制系统建模的非线性系统的本质。本项目着眼于具有通常意义下的线性和二次型目标函数的双边线性方程约束的优化问题，根据其结构特点引入新的变量体系进行分解和重构，将原问题转化成线性或非线性的混合整数规划模型从而设计相应的算法求得全局最优解或者近似最优解。另一方面，本项目还将探索双边线性方程约束的优化问题与单边线性方程求近似解之间的联系，进而设计单边线性方程近似求解的算法。此外，还将探讨当目标函数具有"格线性"形式的时候，相应的优化问题是否存在多项式时间算法。

极大代数上的线性系统理论为分析一些复杂非线性系统提供了一种线性描述形式；是离散事件系统分析以及模糊控制系统设计的重要工具。极大代数上的线性系统理论仍有不少尚未解决的问题，特别是具有双边线性形式的线性系统的分析与优化，是近二十年来相关领域的研究热点问题。..本项目关注极大代数上的一些具有特殊形式的线性方程，通过引入混合整数规划、计算复杂度分析、算法设计等技术手段，对这些方程的解集结构、求解难度以及相应的优化问题进行了探索。研究表明：.（1）极小-蕴涵型模糊关系方程（[0，1]区间极大代数上的一类特殊形式的线性方程组）可以在多项式时间内转化为同等输入维度的0-1整数线性方程组；其解集可以结合一些高效的枚举算法重构；相应的优化问题可以利用整数规划或者混合整数规划的技术求解。.（2）双向模糊关系方程可以在多项式时间内转化成等价的一组0-1混合整数不等式； 其可解性判定问题可以描述成SAT问题，从而在一般情况下是NP完备的；相应的优化问题仍可以结合整数规划或者混合整数规划的技术求解。.（3）模糊矩阵的近似逆矩阵可以表达为双边线性方程约束的范数优化问题；当采用1-范数和无穷范数的线性组合作为目标函数时，其最优近似逆矩阵可以在多项式时间内求解；其所有最优近似逆矩阵可以由相应的模糊关系方程组的解集刻画。..本项目研究取得的这些结果加深了对极大代数上的线性系统特别是模糊关系方程的理解，解决了关于模糊关系方程研究中的一些争论问题；所采用的研究方法也丰富了研究这类问题的处理手法。