  


A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interiorpoint Algorithms
Takashi Tsuchiya (tsuchiyagrips.ac.jp) Abstract: We consider primaldual pairs of semidefinite programs and assume that they are illposed, 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 makes the perturbed primaldual pair strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation is driven to zero. Specifically, we fix two positive definite matrices (typically the identity matrices), and shift the associated affine spaces of the primal and dual slightly in the direction of the two positive definite matrices possibly in a different proportion so that the perturbed problems have interior feasible solutions, and analyze the behavior of the optimal value of the perturbed problem when the perturbation is reduced to zero keeping the proportion. 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 problem. Finally, the analysis leads us to the relatively surprising consequence that the infeasible interiorpoint algorithms for SDP generates a sequence converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. We expect that this property might be particularly useful in solving mixed integer SDPs with infeasible interiorpoint methods. Keywords: Semidefinite programs, perturbation, regularization, infeasible interiorpoint algorithms Category 1: Linear, Cone and Semidefinite Programming Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 12/20/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  