A primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix obtained from a single-secant BFGS update of the primal barrier Hessian, which attains an iteration bound of $\mathcal{O}(\sqrt{\nu}\log(1/\varepsilon)$ and is competitive with QICS, a specialized solver for conic models arising in quantum information.
Abstract
We develop a primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix. The scaling is obtained from a single-secant BFGS update of the primal barrier Hessian. In contrast to multi-secant BFGS scalings, it does not require conjugate-barrier derivatives. This feature is important for high-dimensional nonsymmetric cones, where conjugate-barrier derivatives may be unavailable in closed form or expensive to compute. We embed the conjugate-free scaling in a homogeneous self-dual predictor--corrector framework. Using a split central-path neighborhood that separately controls the conic variables and the scalar homogeneous variables, we prove that the scaling matrix remains uniformly comparable to the primal barrier Hessian. This comparison bound is used to prove neighborhood preservation and to show that the complementarity measure and the linear residual decrease at a uniform rate. Consequently, the method attains an iteration bound of $\mathcal{O}(\sqrt{\nu}\log(1/\varepsilon))$, improving the $\mathcal{O}(\nu\log(1/\varepsilon))$ bound of Badenbroek and Dahl [Optim. Methods Softw., 37 (2022), pp. 1027--1064] and matching the best-known complexity order for interior-point methods. Numerical experiments on instances involving the operator perspective epigraph cone and the quantum relative entropy cone show that the method is competitive with QICS, a specialized solver for conic models arising in quantum information.
It is shown that strict complementarity, together with a quadratic facial-violation property of the associated complementary faces, implies uniform quadratic growth of both the primal and dual augmented Lagrangians near a strictly complementary solution, and the local equivalence of three regularity conditions is proved.
We present a generalization of the well-known homogeneous self-dual embedding model, which is widely used in conic optimization. The new embedding applies to a problem of minimizing the sum of two proper lower-semicontinuous convex functions and can be represented as a single inequality that uses perspectives of these functions and of their conjugates. A solution to the proposed embedding encodes a primal-dual solution to the original problem when available, or an infeasibility certificate otherwise. We then use the Douglas-Rachford algorithm to find a solution to the embedding and discuss its efficient implementation by exploiting the problem structure. The resulting algorithm recovers an existing method for solving quadratic cone programs as a special case. We demonstrate the generality and effectiveness of the algorithm on a class of convex optimization problems with non-smooth objective function and non-conic constraints.
Large-scale optimal transport (OT) problems involve a vast number of transport variables, leading to prohibitive memory and computational costs. To address these challenges, we propose a multiscale primal-dual interior-point relaxation method (MSIPRM). The multiscale outer framework constructs a hierarchy of standard OT problems at progressively finer levels. At each level, the OT problem is solved over a sequence of adaptively refined active sets initialized based on the solution support at the previous level. This yields a sequence of closely related sparse subproblems, thereby substantially reducing memory requirements. The primal-dual interior-point relaxation method (IPRM) serves as the inner solver for each sparse subproblem. Since IPRM does not require strictly interior iterates, it can readily use the solution of the previous subproblem as a warm start. To efficiently obtain the Newton direction, we solve a reduced Schur complement system derived from the normal equations. Furthermore, we develop an effective support-identification strategy based on the approximate solutions obtained by IPRM. We establish condition number estimates for the Schur complement matrices and analyze the global and local convergence properties of the algorithm. Numerical experiments on large-scale test problems demonstrate the computational efficiency and scalability of MSIPRM and show that it compares favorably with existing solvers. In particular, MSIPRM can handle instances whose full formulations contain trillions of transport variables.
Shengyun Sun, Rui-Jin Zhang, Ruoyu Diao et al.· 0 citations
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
The total scaled-gradient variation (TSGV) regularizer, derived from sparse modeling of piecewise-linear structures, has been shown to preserve edges and corners in image restoration. However, its highly nonconvex and nonlinear nature poses severe computational challenges, as existing methods often suffer from parameter sensitivity or lack convergence guarantees. To overcome this, we propose a tailored bilinear decomposition that decouples the nonlinear weighted gradient in the TSGV regularizer. This approach yields an equivalent optimization problem governed by cone or sphere constraints, depending on the chosen scaling function. In particular, the cone constraint plays a central role in characterizing edge- and corner-preserving behavior. We solve this reformulation using the alternating minimization method (AMM) equipped with a majorization--minimization strategy, ensuring a monotonic decrease in energy without step-size tuning. Furthermore, we provide a geometric interpretation of the edge-preserving properties of these constraints by analyzing their asymptotic behavior near image singularities. We establish the global convergence of the proposed method to a critical point within the Kurdyka--{\L}ojasiewicz framework. Extensive numerical experiments on Gaussian denoising and non-line-of-sight (NLOS) imaging show that the proposed method achieves PSNR and SSIM competitive with or superior to representative variational methods, especially at high noise levels, and improves the structural reconstruction under dense and sparse scanning.
Hai-Bin Su, Chunlin Wu, Huibin Chang et al.· 0 citations
Abstract.
We consider Riemannian inequality-constrained optimization problems. Such problems inherit the benefits of Riemannian approach developed in the unconstrained setting and naturally arise from applications in control, machine learning, and other fields. We propose a Riemannian primal-dual interior point trust region method (RIPTRM) for solving them. We prove its global convergence to an approximate Karush–Kuhn–Tucker point and a weak second-order stationary point. Under the strict complementarity condition, this result reduces to global convergence to a second-order stationary point. To the best of our knowledge, this is the first algorithm that incorporates the trust region strategy for constrained optimization on Riemannian manifolds and has the second-order convergence property for optimization problems on Riemannian manifolds with nonlinear inequality constraints. We conduct numerical experiments in which we introduce a truncated conjugate gradient method and an eigenvalue-based subsolver for RIPTRM to approximately and exactly solve the trust region subproblems, respectively. Empirical results show that RIPTRMs consistently find solutions with high accuracy.
