Infeasible primal-dual interior point methods based on the kernel function for convex QCQPs

Abstract

In this paper, we study convex quadratically constrained quadratic programming (QCQP) problems through the primal--dual interior-point methods based on kernel functions. In contrast to standard feasible interior-point approaches, we develop an infeasible method whose iterates do not necessarily satisfy the primal or dual constraints throughout the iterations. When the problem admits a feasible solution, primal feasibility and optimality are achieved simultaneously at convergence. When the feasible set is empty, infeasibility is automatically detected and an approximate solution is obtained via penalized relaxation minimizing the constraint violation, weighted by the chosen kernel function. Under standard convexity assumptions and the existence of optimal solutions, the resulting convex QCQP enjoys strong duality, and its optimal solutions are fully characterized by the Karush--Kuhn--Tucker (KKT) conditions. We introduce a kernel-function-based barrier framework that replaces the classical logarithmic barrier, leading to a parametrized perturbed KKT system with explicit primal and dual residuals. This system defines an infeasible central path, whose neighborhood is followed using exact Newton directions derived from the chosen kernel function. We demonstrate that this approach provides a flexible and unified framework for designing and analyzing efficient Newton-based algorithms for QCQP, with potential extensions to broader classes of conic optimization problems.