基于三角分解的参数多项式优化

In the world of industry and engineering, there is an increasing demand on the accuracy of optimal control. For this reason, nonlinear model predictive control (NMPC) has been playing more and more important role in the design of product prototype. The implementation of such control strategy requires solving many real-time on-line optimization problems. The efficiency of NMPC can be improved by reducing many on-line problems of the same structure to one parametric off-line optimization problem and many light-weighted on-line problems. Among many off-line optimization problems, parametric polynomial optimization is a very important class. Such parametric optimization problems are usually difficult to handle by traditional numeric approach. In this project, we will study how to use triangular decomposition, a symbolic computation tool, to obtain expression formulas of such problems during the off-line stage, which in turn enables us to obtain the control strategies in an exact and efficient manner during on-line stage. More precisely, we would like to make progress on the following fronts: (1) develop the general theory and algorithms for solving parametric polynomial optimization based on triangular decomposition; (2) design special triangular decomposition algorithms by exploiting the particular structures of specific application problems in NMPC; (3) implement our algorithm by taking advantage of the latest computer architectures. This symbolic approach for solving optimization problems is expected to improve both the efficiency and accuracy of the on-line optimization computations of NMPC.

随着工业生产中对最优控制精度的要求越来越高，非线性模型预测控制（NMPC）在产品原型设计阶段扮演着越来越重要的作用。 这种控制策略需要很多实时的在线优化。研究发现可以通过将众多同构的在线优化转变为一个含参数的离线优化和很多轻量级的在线优化提高这种算法的效率。而含参数离线优化问题的重要一类是含参数的多项式优化问题。基于数值计算的传统优化方法很难处理参数问题。在本项目中，我们将研究如何用三角分解这一符号计算工具离线得到这一优化结果的表达公式,从而可在线、高效、准确地得到控制策略。具体地说，我们希望在以下几个方面取得突破：（1）发展用三角分解方法解决含参数多项式优化问题的一般理论和算法；（2）针对NMPC中出现的具体应用问题设计专门的三角分解方法；（3）利用最新的计算机体系结构，高效实现我们的算法。这一符号求解优化问题的方法有望提高NMPC在线求解的精度和效率。

随着很多工业生产中对过程控制精度要求的提高，非线性模型预测控制受到越来越多的重视。参数多项式优化通过把大部分计算转移到离线阶段，可以有效增强模型预测控制的实时性。三角分解方法是研究参数多项式系统精确解的基本方法之一。如何将三角分解应用于参数多项式优化是我们研究的出发点。..我们首先发展了用三角分解方法求解参数多项式优化问题的一般理论和算法。主要思想如下：基于子结式和正则最大公因子的理论以及渐进求解的思想，我们把复空间的三角分解精化为一个柱形分解树，然后通过正则列的实根隔离将其提升为一个实空间的柱形代数分解。利用Thom引理和冲突对的思想，产生一个投影因子可定义的分解，从而得到第一个基于三角分解的完备的柱形分解和量词消去算法。参数多项式优化问题则转化为特定序下的柱形代数分解问题或量词消去问题。这一系列的工作先后发表在Computer Mathematics,符号计算顶级会议ISSAC 2014及权威杂志Journal of Symbolic Computation上，并在MACIS 2013以及国际工业与应用数学大会ICIAM 2015上作了报告。..我们随后提出了利用含参多项式优化问题的具体结构设计专门的三角分解算法。主要思想是：通过KKT条件把带参数的最优化问题转化为求解一个含有等式约束的参数半代数系统，然后利用等式和不等式约束对柱形代数分解树预判剪枝，从而大大提高了分解的效率。相关成果发表在国际会议ICMS 2014,CASC 2014及CICM 2014上。..我们改进了相关算法的效率。这包括两方面的工作：一是用C++及其并行扩展CilkPlus开发了并行多项式基本运算库，高效并行实现了自适应多项式乘法、泰勒移位、正则列的实根隔离等。相关成果发表在ICMS 2014以及ACM Communications in Computer Algebra上，并在ISSAC 2016上作了报告。第二项工作是我们率先提出运用关键点集，同伦方法和数值投影的思想求解参数多项式系统，进一步提高了算法的效率，相关成果发表在CASC 2016和SYNASC 2016上。..另外，我们还将相关算法应用到含参数程序自动并行化、参数动力系统的稳定性分析、单向量子导引中。相关成果发表在CASC 2015, CASCON 2015, SYNASC 2016,Scientific Report。