Takayuki Okuno

We study properties of the central path underlying a nonlinear semidefinite optimization problem, called an NSDP for short. The latest radical work on this topic was contributed by Yamashita and Yabe [Yamashita H, Yabe H (2012) Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Mathematical Programming 132(1-2):1–30]: they proved that the Jacobian of a certain equation system derived from the Karush–Kuhn–Tucker (KKT) conditions of the NSDP is nonsingular at a KKT point under the second-order sufficient condition (SOSC), the strict complementarity condition (SC), and the nondegeneracy condition (NC). This yields uniqueness and existence of the central path through the implicit function theorem. In this paper, we consider the following three assumptions on a KKT point: the strong SOSC, the SC, and the Mangasarian–Fromovitz constraint qualification. Under the absence of the NC, the Lagrange multiplier set is not necessarily a singleton, and the nonsingularity of the above-mentioned Jacobian is no longer valid. Nonetheless, we establish that the central path exists uniquely, and moreover prove that the dual component of the path converges to the so-called analytic center of the Lagrange multiplier set. As another notable result, we clarify a region around the central path where Newton’s equations relevant to primal-dual interior-point methods are uniquely solvable. Funding: This work was supported by the Japan Society for the Promotion of Science [Grant-in-Aid for Young Scientists 20K19748 and Grant-in-Aid for Scientific Research (C) 20H04145]. The Japan Society for the Promotion of Science [Grant-in-Aid for Scientific Research (C) 25K15008].

Abstract Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg–Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a Hölderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.