二阶锥优化的低阶罚函数算法研究

Second-order cone optimization (second-order cone programming and second-order cone complementarity problems) have been paid close attention duo to their extensive applied range and the fusion of other disciplines branch in mathematical programming under their theory..At present, there are many methods for solving second-order cone optimization, such as interior-point algorithm, smoothing algorithm and merit function algorithm etc. But strictly feasible solution is required in general for interior-point algorithm, and some smoothing algorithm might be inefficient when the dimension of the problem gets large..The penalty function algorithms are important method to solve constrained optimization problems. The exact lower-order penalty function algorithms have been paid much attention duo to their good convergence performance. By combine the second-order cone and the ideas of lower-order penalty function algorithms, the objective of this project is to extend the lower-order penalty function algorithms to solve second-order cone optimization. Carry out the theoretical analysis and numerical experiment. We first extent the power penalty function algorithm, which is a special case of lower-order penalty function algorithms, to solve second-order cone complementarity problems. Prove an exponential convergence rate under mild assumptions; Then consider the general lower-order penalty function algorithms to solve second-order cone optimization. Construct the algorithms and discuss the property of convergence and exact penalty; Finally, by smoothing the lower-order penalty equations, we consider the smoothing technique of lower-order penalty function algorithms to solve second-order cone optimization..The theory and algorithm of this project can promote the further development for solving second-order cone optimization. This project has important scientific significance and broad application prospect since the research content of this project has wide application itself.

二阶锥优化(二阶锥规划及二阶锥互补问题)因其广泛的应用范围及在其理论下其它学科分支在数学规划中的融合而备受人们关注.求解二阶锥优化的内点算法一般要求严格可行解,光滑算法在问题维数很大时可能并不十分有效.罚函数算法是求解约束优化问题的重要方法,低阶罚函数算法因其良好的收敛性及精确罚性而得到人们广泛关注.本项目的目标是结合二阶锥与低阶罚函数算法的相关思想,将低阶罚函数算法推广到求解二阶锥优化,进行理论分析并构造算法和数值实验.首先将幂罚函数这类特殊的低阶罚函数算法从求解一般互补问题扩展到求解二阶锥互补问题,证明在一定条件下指数收敛速度的良好性能;然后考虑一般的低阶罚函数算法,讨论其收敛性及精确罚性,构造算法并进行数值实验;最后结合光滑化技巧,将低阶罚函数方程光滑化,考虑二阶锥优化的低阶罚函数光滑化算法.本项目可以促进二阶锥优化的算法研究,研究内容本身具有广泛应用,因而具有重要的科学意义.

锥规划是线性空间中凸锥上的数学规划,是线性规划与非线性规划的推广.相关研究带动了数学规划学科的深入发展,以及优化理论与技术的广泛应用.线性规划、二阶锥规划和半定规划均隶属于锥规划,欧几里得约当代数将它们联系起来,并为一般优化问题的理论和算法提供了坚实的理论基础.二阶锥规划是锥规划的重要研究内容,应用非常广泛,二阶锥互补问题是一类比二阶锥规划更广的均衡优化问题,两者统称为二阶锥优化.求解二阶锥优化主要有内点算法类、光滑算法类、价值函数算法类和其他一些算法.低阶罚函数算法在求解约束优化问题时因其精确性而备受人们关注,但鲜有将低阶罚函数算法应用于二阶锥优化的文献.本项目主要研究二阶锥规划及二阶锥互补问题的低阶罚函数理论与算法,以及算法的光滑化.在前期幂罚函数算法求解二阶锥互补问题的基础上,将算法成功地扩展到一般低阶罚函数算法,用于求解二阶锥线性、非线性两种互补问题,给出了一定条件下指数收敛速度的证明及相应数值结果,但在二阶锥线性互补问题时矩阵条件的弱化,及二阶锥非线性互补问题时一般低阶罚函数的精确性两方面的工作还不成熟;将一般低阶罚函数算法成功用于求解二阶锥混合互补问题,证明了一定条件下指数收敛速度的特性及条件弱化时的收敛性,给出了相应数值结果,二阶锥混合互补问题无需将函数和变量表达式转化,本身隶属于非对称锥互补问题,因而其算法为一般二阶锥规划尤其是凸二阶锥规划的求解提供了计算方法;将光滑化技巧成功应用于低阶罚函数算法,已经将光滑化技巧应用于低阶罚函数算法用于求解二阶锥线性互补问题, 用于求解二阶锥非线性互补问题的工作基本完成,用于求解二阶锥混合互补问题的工作还有待完善.这些研究进展及结果扩充了求解二阶锥优化的理论与算法,并在一定条件下具有更好的数值性能.扩展问题将线性次序关系上升到偏序关系,体现了数学上从特殊到一般的研究思路,其结果在交通运输、经济、工程等领域具有重要应用.