Solving Quantified Algebraic Constraints

求解量化代数约束

• 批准号: 0097976
• 负责人: Hoon Hong
• 金额: $ 26.75万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2005-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0097976&HistoricalAwards=false
• 关键词: Solving; Quantified; Algebraic; Constraints

Proposal #0097976Hong, HoonNorth Carolina State UThe long term objective of this research is to develop mathematical theories, algorithms, and software libraries/packages for efficiently solving quantified algebraic constraints (quantified boolean expressions of polynomial equations/inequalities over real numbers), which can handle large real life problems. This particular project will focus on moderate size inputs (up to about 10 variables). There are still many interesting real life problems of moderate sizes.The potential impact is as follows. Many important and difficult problems in mathematics, scientific, engineering and industry can be reduced to that of solving quantified algebraic constraints. Thus the availability of efficient algorithms/softwares for solving quantified algebraic constraint will have a broad impact on science and industry.The specific approaches are as follows.- Allow approximate solutions.The subject of quantifier constraint solving arose originally as a problem in logic. Naturally, obtaining "exact" solution has been the goal of the previous research efforts. In order to obtain exact solutions, most calculations have been carried out symbolically, suffering from enormous intermediate computation swelling. Further, they had to deal with all the singular/degenerate cases, which are often very expensive computationally to analyze. However, in most real-life problems, approximate solutions are acceptable. In fact, often, there are many uncertain coefficients in constraints, and thus it is even meaningless to try to find exact solutions. Hence, we will allow approximate solutions. During this project period, we will pursue two particular ideas in this direction: "approximate quantification" and "box approximation" of solution sets. Our preliminary investigations suggest that these are very promising ideas/directions.- Utilize the structure of constraints.So far, the constraints have been treated as "flat" objects. For example, the polynomials arising in the constraints have been viewed as "atomic" objects. However, constraints in real life problems usually have intrinsic structures that arise naturally from the structures in the underlying laws/components or from the way how the those laws/components are combined. Thus, we will utilize the structures of given constraints. During this project period, we will study ways to utilize two particular structures: "convexity" of bounded quantifiers and "composition" structure of polynomials. Again, our preliminary investigations suggest that these are very promising ideas/directions.The results will be implemented in a software library and freely distributed on the web, in order to facilitate their application to moderate size real life problems by the scientific and engineering communities.

提案#0097976洪，HoonNorth卡罗莱纳州立大学本研究的长期目标是开发数学理论，算法和软件库/包，用于有效地解决量化的代数约束（真实的数上多项式方程/不等式的量化布尔表达式），可以处理大型真实的生活问题。这个特殊的项目将侧重于中等规模的投入（最多约10个变量）。还有许多有趣的真实的生活中的中等规模的问题。潜在的影响如下。 数学、科学、工程和工业中的许多重要和困难问题都可以归结为求解量化代数约束的问题。因此，解决量化代数约束的有效算法/软件的可用性将对科学和工业产生广泛的影响。具体方法如下。允许近似解。量词约束求解的主题最初是作为逻辑问题出现的。当然，获得“精确”的解决方案一直是以前的研究工作的目标。为了获得精确解，大多数计算都是象征性地进行的，中间计算量巨大。此外，他们必须处理所有奇异/退化的情况，这通常是非常昂贵的计算分析。然而，在大多数现实生活中的问题，近似的解决方案是可以接受的。实际上，约束条件中往往存在许多不确定系数，因此寻求精确解甚至是毫无意义的。因此，我们将允许近似解。在这个项目期间，我们将在这个方向上追求两个特别的想法：“近似量化”和“盒近似”的解决方案集。我们的初步调查表明，这些都是非常有前途的想法/方向。利用约束的结构。到目前为止，约束一直被视为“平面”对象。例如，在约束中出现的多项式被视为“原子”对象。然而，真实的生活问题中的约束通常具有内在结构，这些内在结构自然地产生于基础定律/组件中的结构或这些定律/组件如何组合的方式。因此，我们将利用给定约束的结构。在这个项目期间，我们将研究如何利用两种特殊的结构：有界量词的“凸性”和多项式的“合成”结构。同样，我们的初步调查表明，这些都是非常有前途的想法/directions.The结果将在一个软件库中实现，并在网络上免费分发，以促进其应用到中等规模的真实的生活问题的科学和工程界。