A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms

• 成果类型: Article
• 署名作者: Tsuchiya, Takashi; Lourenco, Bruno F.; Muramatsu, Masakazu; Okuno, Takayuki
• 署名单位: National Graduate Institute for Policy Studies; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Electro-Communications - Japan; Seikei University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01891-8
• 发表日期: 2023
• 页码: 531-568
• 关键词: facial reduction algorithm; error-bounds; Strong Duality; semidefinite; paths

摘要

We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices, I-p and I-d, say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space by eta I-p and epsilon I-d, respectively, to recover interior feasibility of both problems, where epsilon and eta are positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio between eta and epsilon constant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes monotonically from the primal optimal value to the dual optimal value as a function of theta, if we parametrize (epsilon, eta) as (epsilon, eta) = t(cos theta, sin theta) and let t -> 0. Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems.