半定规划的广义弱尖锐性及其应用

The notion of generalized weak sharp minima is an important tool in the analysis of the perturbation behavior of certain classes of optimization problems as well as in the convergence analysis of algorithms designed to solve these problems. In this project, it is mainly considered the generalized weak sharp minima in semidefinite programming (SDP in short) with applications in analyzing the sensitivity under perturbations of the right-hand side and the convergence of the augmented Lagrangian methods for solving SDP. Firstly, the notion of generalized weak sharp minima is introduced for SDP and the necessary and (or) sufficient conditions are derived; Geometric characterizations of generalized weak sharp minima are portrayed by utilizing the tools available in the books of Analysis on Symmetric Cones and Variational Analysis and Optimization, such as Jordan algebra, spectral factorization and variational analysis in semidefinite cones etc.; the links between the existence of augmented Lagrangian multipliers and the generalized weak sharp minima in SDP are established. Secondly, augmented Lagrangian methods are designed for solving SDP with the generalized weak sharp minima property, and the convergence of the algorithms is analyzed by employing the generalized weak sharp minima; numerical results for solving large scale SDP (problems with matrix variables of order n>200 and m>3000 constraints ) are presented . At last, the generalized weak sharp minima property is used for analyzing the sensitivity under perturbations of the right-hand side, and the designed algorithms and error bound results are employed for solving an ill-posed SDP with a small feasible region provided by Khachiyan.

广义弱尖锐性是用于分析算法的收敛性和扰动问题的灵敏度的重要工具，本项目研究半定规划的广义弱尖锐性及其在增广拉格朗日法的收敛性分析和问题的灵敏度分析中的应用。首先，为半定规划引入广义弱尖锐性的概念并探究问题具有广义弱尖锐性的一些充分和（且）必要条件；利用半正定锥的变分分析和对称锥优化中的约当代数及谱分解定理等工具研究半定规划具有广义弱尖锐性的一些几何特性；建立半定规划的广义弱尖锐性与强KKT条件和增广拉格朗日乘子的存在性之间的关系。然后，对具有广义弱尖锐性的半定规划设计增广拉格朗日算法并利用广义弱尖锐性分析算法的收敛性。最后，利用广义弱尖锐性考察扰动的半定规划的灵敏度分析，并利用Matlab编程对所设计的算法和误差界结果计算由Khachiyan给出的一个可行域极小的病态的半定规划实例。

广义弱尖锐性是用于分析算法的收敛性和扰动问题的灵敏度的重要工具，本项目研究半定规划的广义弱尖锐性及其在增广拉格朗日法的收敛性分析和问题的灵敏度分析中的应用。首先，为半定规划引入广义弱尖锐性的概念并探究问题具有广义弱尖锐性的一些充分和（且）必要条件；利用半正定锥的变分分析和对称锥优化中的约当代数及谱分解定理等工具研究半定规划具有广义弱尖锐性的一些几何特性；建立半定规划的广义弱尖锐性与强KKT条件和增广拉格朗日乘子的存在性之间的关系。然后，对具有广义弱尖锐性的半定规划设计增广拉格朗日算法并利用广义弱尖锐性分析算法的收敛性。最后，利用广义弱尖锐性考察扰动的半定规划的灵敏度分析，并利用Matlab编程对所设计的算法和误差界结果计算由Khachiyan给出的一个可行域极小的病态的半定规划实例。