《極大代數上的雙邊線性系統的最佳化》是依託清華大學，由李平科擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：極大代數上的雙邊線性系統的最佳化
- 依託單位：清華大學
- 項目負責人：李平科
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
極大代數上的線性系統理論是離散事件系統分析和控制以及模糊控制系統設計的重要工具。極大代數上的線性系統的最佳化問題是最近的一個研究熱點，目前，一些基本問題，特別是雙邊線性方程的求解與最佳化，仍未完全解決。對於這些問題的研究有助於加深理解一些可由離散事件系統和模糊控制系統建模的非線性系統的本質。本項目著眼於具有通常意義下的線性和二次型目標函式的雙邊線性方程約束的最佳化問題，根據其結構特點引入新的變數體系進行分解和重構，將原問題轉化成線性或非線性的混合整數規劃模型從而設計相應的算法求得全局最優解或者近似最優解。另一方面，本項目還將探索雙邊線性方程約束的最佳化問題與單邊線性方程求近似解之間的聯繫，進而設計單邊線性方程近似求解的算法。此外，還將探討當目標函式具有格線性形式的時候，相應的最佳化問題是否存在多項式時間算法。
結題摘要
極大代數上的線性系統理論為分析一些複雜非線性系統提供了一種線性描述形式；是離散事件系統分析以及模糊控制系統設計的重要工具。極大代數上的線性系統理論仍有不少尚未解決的問題，特別是具有雙邊線性形式的線性系統的分析與最佳化，是近二十年來相關領域的研究熱點問題。 本項目關注極大代數上的一些具有特殊形式的線性方程，通過引入混合整數規劃、計算複雜度分析、算法設計等技術手段，對這些方程的解集結構、求解難度以及相應的最佳化問題進行了探索。研究表明： （1）極小-蘊涵型模糊關係方程（[0，1]區間極大代數上的一類特殊形式的線性方程組）可以在多項式時間內轉化為同等輸入維度的0-1整數線性方程組；其解集可以結合一些高效的枚舉算法重構；相應的最佳化問題可以利用整數規劃或者混合整數規劃的技術求解。 （2）雙向模糊關係方程可以在多項式時間內轉化成等價的一組0-1混合整數不等式； 其可解性判定問題可以描述成SAT問題，從而在一般情況下是NP完備的；相應的最佳化問題仍可以結合整數規劃或者混合整數規劃的技術求解。 （3）模糊矩陣的近似逆矩陣可以表達為雙邊線性方程約束的範數最佳化問題；當採用1-範數和無窮範數的線性組合作為目標函式時，其最優近似逆矩陣可以在多項式時間內求解；其所有最優近似逆矩陣可以由相應的模糊關係方程組的解集刻畫。 本項目研究取得的這些結果加深了對極大代數上的線性系統特別是模糊關係方程的理解，解決了關於模糊關係方程研究中的一些爭論問題；所採用的研究方法也豐富了研究這類問題的處理手法。
