Convergence analysis of inexact MBA method for constrained upper- π’ž 2 \mathcal{C}^{2} optimization problems

Ruyu Liu and Shaohua Pan Β· 2025

Read Convergence analysis of inexact MBA method for constrained upper- π’ž 2 \mathcal{C}^{2} optimization problems by Ruyu Liu and Shaohua Pan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-09940.txt.

Introduction

Ruyu Liu and Shaohua Pan develop an inexact moving balls approximation method for constrained optimization problems whose objective and constraint functions are both upper-C-two, a class covering many nonconvex, nonsmooth problems. Exact subproblem solving is costly, so their method accepts approximate solutions under a workable inexactness rule. The goal is a practical method that still carries a full convergence certificate.

Using a global error bound for the associated strongly convex programs, they prove the whole iterate sequence converges under two named conditions on multipliers and the potential function. When the potential satisfies a Kurdyka-Lojasiewicz property with a suitable exponent, they also get local convergence rates, plus a checkable condition for that property. They describe it as the first implementable inexact method of its kind with full guarantees.

Catalog record

CREATORRuyu Liu and Shaohua Pan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-09940

Browse the full library Β· About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convergence analysis of inexact MBA method for constrained upper- π’ž 2 \mathcal{C}^{2} optimization problems Ruyu Liu and Shaohua Pan Abstract This paper concerns a class of constrained optimization problems in which, the objective and constraint functions are both upper- π’ž 2 \mathcal{C}^{2} . For such nonconvex and nonsmooth optimization problems, we develop an inexact moving balls approximation (MBA) method by a workable inexactness criterion for the solving of subproblems. By leveraging a global error bound for the strongly convex program associated with parametric optimization problems, we establish the full convergence of the iterate sequence under the partial bounded multiplier property (BMP) and the Kurdyka-Łojasiewicz (KL) property of the constructed potential function, and achieve the local convergence rate of the iterate and objective value sequences if the potential function satisfies the KL property of exponent q ∈ [ 1 / 2 , 1 ) q\in[1/2,1) . A verifiable condition is also provided to check whether the potential function satisfies the KL property of exponent q ∈ [ 1 / 2 , 1 ) q\in[1/2,1) at the given critical point. To the best of our knowledge, this is the first implementable inexact MBA method with a full convergence certificate for the constrained nonconvex and nonsmooth optimization problem. 1 Introduction Constrained optimization problems are a class of tough composite optimization problems in which the outer nonsmooth function is an indicator of some closed convex set. They naturally arise when one attempts to seek a solution that minimizes an objective under some restrictions. On the other hand, nonconvex and nonsmooth functions abound with lower- \mathcal{C}^{2} functions [ 16 , 11 ] ; for example, locally Lipschitz prox-regular functions are the common ones, so their negatives (upper- \mathcal{C}^{2} functions) often appear in the difference programming problems [ 1 , 23 , 2 , 29 ] . We are interested in developing an efficient algorithm for the constrained upper- \mathcal{C}^{2} problem \min_{x\in\mathbb{R}^{n}}F(x):=g_{0}(x)+\delta_{\mathbb{R}_{-}^{m}}(g(x))+\phi(x), (1) where \delta_{\mathbb{R}_{-}^{m}}(\cdot) is the indicator of the non-positive orthant \mathbb{R}_{-}^{m} , g:=(g_{1},\ldots,g_{m})^{\top} is a mapping, and the functions g_{i} for i=0,1,\ldots,m and \phi satisfy Assumption 1 below. It is worth pointing out that the upper- \mathcal{C}^{2} min-max problem \min_{x\in\mathbb{R}^{n}}\max_{1\leq i\leq m}g_{i}(x) can also be reformulated as the form of ( 1 ) by introducing an additional variable. Assumption 1 (i) g_{0}\!:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=(-\infty,\infty] is locally Lipschitz and upper- \mathcal{C}^{2} at every point of an open convex set \mathcal{O}\supset\Gamma:=g^{-1}(\mathbb{R}_{-}^{m})\neq\emptyset , and g_{i}\!:\mathbb{R}^{n}\to\mathbb{R} for i=1,\ldots,m are locally Lipschitz and upper- \mathcal{C}^{2} at any point of \mathbb{R}^{n} ; (ii) \phi\!:\mathbb{R}^{n}\to\mathbb{R} is a convex function, and F is bounded from below on the set \Gamma . Many methods have been developed for constrained optimization problems; for example, sequential quadratic programming (SQP) methods are known to be a class of popular ones for the classical nonlinear programming problems (NLPs), but they cannot be directly applied to cope with constrained nonsmooth problems like ( 1 ). Recently, some efforts have been made that incorporate certain key ideas from the classical algorithms to develop an iterative framework tailored for constrained nonsmooth problems. For the smooth equality and box constrained optimization problem with an upper- \mathcal{C}^{2} objective function, Wang and Petra [ 34 ] proposed a nonsmooth SQP method with the proximal parameters updated by a trust-region strategy. Under the LICQ assumption on every accumulation point, they achieved the subsequence convergence of the iterate sequence. Mordukhovich et al. [ 29 ] considered ( 1 ) with g_{i}=f_{i}\!-\!h_{i} for i=0,1 and \phi=\delta_{X} , where f_{i}:\mathbb{R}^{n}\to\mathbb{R} are assumed to be \mathcal{C}^{1+} (continuously differentiable with locally Lipschitzian gradients) and h_{i}:\mathbb{R}^{n}\to\overline{\mathbb{R}} are locally Lipschitz and prox-regular over the closed convex set X . They proposed a novel variant of the extended sequential quadratic method introduced in [ 8 ] for NLPs, and established the full convergence of the iterate sequence under the boundedness of penalty parameters and the KL property of the constructed potential function. Compared with the SQP methods, the moving ball approximation (MBA) method is a new type one, which was first proposed by Auslender et al. [ 7 ] for NLPs. Different from the standard SQP method, it generates a sequence of feasible iterates from a feasible starting point. The authors of [ 7 ] proved that under the MFCQ, any cluster point of the iterate sequence is a stationary point, and the whole sequence converges to a minimizer under the additional convexity. Later, for semialgebraic NLPs, Bolte and Pauwels [ 12 ] established the full convergence and convergence rate of the iterate sequence for the MBA method under the MFCQ, thereby enhancing the convergence results of [ 7 ] . Recently, Yu et al. [ 37 ] studied a line-search variant of the MBA method for problem ( 1 ) with L -smooth g . Under the MFCQ and the assumption that g_{0} is \mathcal{C}^{1+} on an open set containing the stationary point set of ( 1 ), they achieved the full convergence of the iterate sequence if the constructed potential function has the KL property, and the local convergence rate if the KL property is of exponent q\in[1/2,1) . The above MBA methods all require the subproblems to be solved exactly, which is unrealistic especially in large-scale applications due to computation error and cost. To overcome the issue, for problem ( 1 ) with \phi\equiv 0 but every g_{i} being a sum of an L -smooth function and a continuous convex function, Boob et al. [ 15 ] developed a level constrained proximal gradient (LCPG) method to allow the subproblems to be computed inexactly. They put more emphasis on the complexity analysis of LCPG under the MFCQ for stochastic and deterministic setting, though the subsequential convergence of the iterate sequence was also proved. Their inexactness criterion (see [ 15 , Definition 7] ) involves the exact primal-dual optimal solutions of subproblems and the optimal values of subproblems, and now it is unclear whether such an inexactness criterion is workable or not in practical computation. For problem ( 1 ) with all g_{i} being L -smooth, Nabou and Necoara [ 31 ] developed an inexact moving Taylor approximation (MTA) method with an implementable inexactness criterion, which reduces to the MBA method when the involved p and q both take 1 . Under the MFCQ, they established the full convergence of the iterate sequence if the constructed proximal Lagrange potential function has the KL property, and the local convergence rate if the potential function has the KL property of exponent q\in[1/2,1) . The convergence analysis in [ 31 ] for the inexact MBA method depends heavily on the fact that an L -smooth function is globally upper- \mathcal{C}^{2} as well as lower- \mathcal{C}^{2} . Obviously, it is inapplicable to problem ( 1 ) where all g_{i} are only assumed to be locally upper- \mathcal{C}^{2} . Then, there is still a lack of a practical MBA method with convergence guarantee for solving ( 1 ). On the other hand, the existing asymptotic convergence results on the MBA method are all obtained for ( 1 ) with L -smooth g_{i} under the MFCQ. The robustness of MFCQ ensures the uniform boundedness of the Lagrange multipliers of subproblems, which greatly reduces the difficulty caused by the multipliers of subproblems. For NLPs, the past two decades have witnessed

Read the complete text