2026/07/27 by Wenqi Zhu, Haibin Chen, Guanglu Zhou
#math.OC #cs.NA #math.NA
High-order methods can improve worst-case evaluation complexity, but for orders p≥3 their Taylor subproblems are nonconvex polynomial optimization problems and are generally difficult to solve. We develop a radius-controlled boundary approach based on homogeneous tensor representations. By augmenting the step with a constant coordinate, any pth-order Taylor polynomial can be represented exactly as an order-p homogeneous tensor form; at a prescribed radius, the boundary model is a spherical polynomial optimization problem. The representation applies to arbitrary p, while the algorithmic development focuses on the cubic case p=3. For an inhomogeneous cubic on the sphere, we introduce a quadratic shift and prove, under an explicit shift bound, equivalence with a three-block multilinear formulation at global optimality. This motivates a proximal alternating minimization (PAM) method with closed-form block updates; its objective values decrease and every accumulation point is stationary. We embed the boundary-step mechanism in an Adaptive Homogeneous Tensor Method (Ada--HTM). Under explicit smoothness, safeguarded-decrease, weak-curvature nondegeneracy, and local-refinement conditions, Ada--HTM attains the adaptive-regularization-type (ARp-type) evaluation complexity O(ε-(p+1)/p) for first-order stationarity. Numerically, PAM matches order-2 moment--sum-of-squares (SOS) certificates on the structured cubic instances for which certification is tractable, scales particularly well for low-rank tensors, and makes Ada--HTM competitive with trust-region and cubic-regularization methods, with its largest gains on ill-conditioned and badly-scaled problems.