Partially separable convexly-constrained optimization
with non-Lipschitzian singularities and its complexity
X. Chen, Ph. L. Toint and H. Wang April 2017
An adaptive regularization algorithm using high-order models is proposed for
partially separable convexly constrained nonlinear optimization problems whose
objective function contains non-Lipschitzian $\ell_q$-norm regularization
terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order
Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$
evaluations of the objective function and its derivatives (at points where
they are defined) to produce an $\epsilon$-approximate first-order critical
point. This result is obtained either with Taylor models at the price of
requiring the feasible set to be 'kernel-centered' (which includes bound
constraints and many other cases of interest), or for non-Lipschitz models, at
the price of passing the difficulty to the computation of the step. Since this
complexity bound is identical in order to that already known for purely
Lipschitzian minimization subject to convex constraints [Cartis et al., 2016],
the new result shows that introducing non-Lipschitzian singularities in the
objective function may not affect the worst-case evaluation complexity
order. The result also shows that using the problem's partially separable
structure (if present) does not affect complexity order either. A final
(worse) complexity bound is derived for the case where Taylor models are used
with a general convex feasible set.