论文标题
信任区子问题的一阶扰动理论
First-order perturbation theory of trust-region subproblems
论文作者
论文摘要
信任区域子问题（TRS）是在许多应用中产生的重要问题，例如数值优化，提出问题不足问题的Tikhonov正则化以及限制了特征值问题。近几十年来，广泛的作品着重于如何有效地解决信任区子问题。据我们所知，对信任区域子问题的扰动分析几乎没有结果。为了填补这一空白，我们专注于信任区子问题的一阶扰动理论。本文的主要贡献是三倍。首先，假设TRS在\ emph {easy case}中，我们提供了足够的条件，在该条件下，扰动的TRS仍然在容易的情况下。其次，借助TRS的结构和经典的本本特征扰动理论，我们对Lagrange乘数和TRS解决方案进行了一阶扰动分析，并定义了其状况数。第三，我们指出，即使TRS在{\几乎是硬情况下}，解决方案和Lagrange乘数也可以很好地调节。既定的结果都是可计算的，有助于事先评估TRS问题的不良条件。数值实验表明了已建立的界限的清晰度以及所提出的策略的有效性。
Trust-region subproblem (TRS) is an important problem arising in many applications such as numerical optimization, Tikhonov regularization of ill-posed problems, and constrained eigenvalue problems. In recent decades, extensive works focus on how to solve the trust-region subproblem efficiently. To the best of our knowledge, there are few results on perturbation analysis of the trust-region subproblem. In order to fill in this gap, we focus on first-order perturbation theory of the trust-region subproblem. The main contributions of this paper are three-fold. First, suppose that the TRS is in \emph{easy case}, we give a sufficient condition under which the perturbed TRS is still in easy case. Second, with the help of the structure of the TRS and the classical eigenproblem perturbation theory, we perform first-order perturbation analysis on the Lagrange multiplier and the solution of the TRS, and define their condition numbers. Third, we point out that the solution and the Lagrange multiplier could be well-conditioned even if TRS is in {\it nearly hard case}. The established results are computable, and are helpful to evaluate ill-conditioning of the TRS problem beforehand. Numerical experiments show the sharpness of the established bounds and the effectiveness of the proposed strategies.
