二次参数实整混合线性优化的量词消去法
Parametric Quadratic Mixed Real-Integer Optimization By Quantifier Elimination
-
摘要: 应用来自 Weispfenning的关于线性以及二次线性优化的量词消去方法和Shostak解Presburger公式的SUP-INF方法,研究了带有参数的二次目标函数的线性优化,给出了一种具有参数的二次目标函数的整线性优化的量词消去方法.分析表明,所用方法具有几乎最优的复杂性.Abstract: A new elimination method for mixed real-integer optimization with quadratic objective function and parametric coeffcients is presented. The method combines ideas from the one found by Weispfenning about real linear and quadratic optimization and the one by Shostak on the SUP-INF method of proving Presburger formulas. It is proved that the algorithm has an almost optimal complexity, and is implemented by some test examples using a preliminary MAPLE, the symbolic computational language.