广义仿射分式规划的全局优化算法及其在计算机视觉中的应用

The project intends to propose out space algorithm, branch-and-bound algorithm, polynomial time approximation algorithm and other global optimization theory and algorithms for globally solving generalized affine fractional programming problems, which comes down from many practical problems; and apply the above algorithms to solve multiple-view geometry, three-dimensional image reconstruction of computer vision and other practical problems. The main contents are given as follows: for special form of generalized affine fractional programming problem, construct and utilize out space equivalent problem, establish out space algorithm; for generalized affine fractional programming with the objective function of generalized polynomial function form, utilize linear approximation technique and so on, construct relaxation programming problems, establish branch-and-bound algorithm; in order to improve the computational efficiency of the proposed algorithm, utilize the characteristics of the investigated problem and the structure of the proposed algorithm, design new regional deleting principle; for the general form and special form of the generalized affine fractional programming problem, by constructing the equivalent problem of the original problem, and establish the polynomial time approximation algorithm by utilizing the characteristics of the corresponding problem, finally the convergence and the complexity of the algorithm are analyzed; apply the above algorithms and techniques to solve the generalized affine fractional programming problems, which appear in multiple-view geometry, triangulation of computer vision, and so forth. This project will not only provide new ideas for globally solving generalized affine fractional programming problem, but also there are very important significance for promoting the development and application of global optimization theory and algorithms.

本项目拟对众多实际问题中归结出的广义仿射分式规划问题，提出外空间算法、分支定界算法、多项式时间近似算法等全局优化理论与算法，并将其应用于计算机视觉中的多视图几何、三维图像重构等实际问题中。具体内容如下：针对特殊形式的广义仿射分式规划问题，构造并利用外空间等价问题，建立外空间算法；针对目标函数为广义多项式函数形式的广义仿射分式规划问题，利用线性逼近等技巧，构造松弛问题，建立分支定界算法；为提高算法的计算效率，利用问题的特征和算法结构，构造区域删除原则；针对广义仿射分式规划问题的一般形式及特殊形式，通过构造原问题的等价问题，建立求解相应问题的多项式时间近似算法，分析算法的收敛性和复杂度；应用上述算法求解计算机视觉中的多视图几何、三维图像重构等实际问题中的广义仿射分式规划问题。本项目不仅为广义仿射分式规划提供新的求解思路，而且也对促进分式规划全局优化理论与算法的发展和应用具有重要的意义。

大量的科学、经济与工程计算问题均可归结为求解广义仿射分式规划问题一般形式及特殊形式的全局最优解，由于该问题是非凸的，它可能存在多个不是全局极小的局部极小点，这使得已有的局部优化方法难于求得该问题的全局最优解，需要提出新的求解算法。本项目研究了带指数的仿射多乘积规划问题，利用等价转化和对数函数的特性构造松弛问题，基于像空间剖分搜索，分别构建了分支缩减定界算法、参数线性松弛算法、分段线性松弛算法。研究了广义仿射多乘积规划问题，通过对目标函数进行适当的变形，利用松弛问题的可分解性等，分别构建了外空间分支定界算法、变量维空间分支定界算法等。研究了仿射分式和问题，利用等价转化等技巧构建等价问题，并构造线性松弛、凸松弛、二阶锥松弛、对偶松弛、区域缩减技巧等，提出了几种分支定界算法。研究了极小极大仿射分式规划问题，构造新的线性化技巧，设计了高效的外空间分支定界算法。研究了广义多项式分式和问题，利用单调优化等技巧，将其等价转化为正项式几何规划问题，提出了一个迭代算法。研究了目标为仿射分式和或多乘积形式的仿射分式规划问题，提出了一个基于范围分裂和线性化技巧的多项式时间近似算法。研究了线性约束的广义仿射分式规划问题，构造了一个两层线性松弛方法，基于分支定界框架和线性规划松弛问题，提出了一种分支定界算法。针对目标和约束均为广义多项式形式的广义仿射分式规划问题，利用对数和指数函数的凸包、凹包逼近，提出了一个两阶段线性松弛算法。研究了计算机视觉中的广义仿射分式规划问题，利用代数变换进行等价转化，利用直接松弛技巧构造松弛问题，利用松弛问题的可分解性，提出了一个分解算法。本项目分析证明了上述算法的全局收敛性，估计了上述算法的计算复杂度，数值实验验证了上述算法的可行性和高效性。上述研究成果对加强和促进我国在全局优化理论与算法方面的研究和发展，促进国民经济的建设和发展，具有重要的科学意义和应用价值。