非凸优化中若干子问题的凸表述与算法研究

Nonconvex optimization suffers from its hard solvability. Subproblems play an important role in nonconvex optimization algorithms. This proposal mainly considers two subproblems in optimization methods: the generalized trust region subproblem and the subproblem of cubiccally regularized Newton's method. Existing algorithms cannot be used to solve large scale subproblems and lack convergence analysis for both subproblems. We expect to use the hidden convexity of both subproblems to reformulate then into convex problems and use existing efficient algorithms for convex optimization to solve the reformulations. For the generalized trust region subproblem, we expect to reformulate it into a convex quadratic problem, and further reformulate it into an unconstrained minimax problem. We also expect to design an efficient algorithm to solve the minimax reformulation, analyze the convergence rate of the algorithm, and recover an optimal solution to the original subproblem from an optimal solution of the minimax reformulation. For cubic regularization subproblem, we study its convex reformulation and design an efficient algorithm to solve this reformulation. We would also like to analyze the approximate level of an approximate solution of our reformulation from the optimal of the original cubic regularization subproblem and analyze the global performace when the convex reformulation is solved inexactly. Finally, we also expect to extend our result to pth (p>2) order cubic regularization subproblem.

非凸优化的求解一直是优化理论的瓶颈。子问题在非凸优化算法中扮演着至关重要的作用。本项目将主要研究两个非凸优化算法的子问题：广义信赖域子问题和三次正则化子问题。已有的求解子问题的算法不适合大规模计算。现有的文献也缺乏对这些子问题算法的收敛性分析。本项目期望能够利用这两个子问题的隐含的凸性来找到它们的凸表述，然后利用现有的凸问题的解法来快速求解子问题，并且期望能够得到算法的收敛性质。对于广义信赖域子问题，研究二次凸优化等价表述，进一步找到极小极大化问题等价表述，设计快速算法求解等价表述问题，分析等价表述问题收敛性和如何从等价表述问题的最优值恢复原问题的最优值。对于三次正则化子问题，研究等价凸表述，设计快速算法解等价凸表述，分析凸表述的近似解和原三次正则化子问题的最优解近似程度，并且分析凸表述非精确时原问题的收敛速度。最后本项目期望将研究成果拓展到p(p>2)次正则化子问题上。

在很多优化算法框架下，每次迭代都需要求解一个子问题，其性质和求解速度对优化算法的整体速度起着关键影响。本项目主要研究两类重要的非凸优化的子问题，即广义信赖域子问题和三次正则化牛顿法的子问题。前者可作为带二次约束的二次规划的交替方向乘子法的子问题，后者可作为一般无约束优化的子问题。我们提出了广义信赖域子问题的一个等价极小极大的无约束凸刻画，并设计了一个最速下降法求解，同时给了收敛速度分析，数值实验显示我们的算法比当时最快的算法更高效。此外我们第一次从理论上证明了广义信赖域子问题是线性时间可解的。本项目还提出了一个三次正则化牛顿法子问题的等价无约束凸问题刻画，并利用它设计了一个求解一般无约束非凸优化问题的算法。证明了其收敛速度和当前最好的算法一样，并且数值实验证明该算法在公开数据集上和已有算法效果近似。