  


Partially separable convexlyconstrained optimization with nonLipschitz singularities and its complexity
X Chen(maxjchenpolyu.edu.hk) Abstract: An adaptive regularization algorithm using highorder models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains nonLipschitzian $\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 firstorder critical point. This result is obtained either with Taylor models at the price of requiring the feasible set to be 'kernelcentered' (which includes bound constraints and many other cases of interest), or for nonLipschitz 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[CartGoulToin2016], the new result shows that introducing nonLipschitzian singularities in the objective function may not affect the worstcase 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. Keywords: complexity theory, nonlinear optimization, nonLipschitz Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: The Hong Kong Polytechnic UNiversity Download: [PDF] Entry Submitted: 04/20/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  