Optimization Online


Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization

Andreas Griewank(griewank***at***yachaytech.edu.ec)
Andrea Walther(andrea.walther***at***uni-paderborn.de)

Abstract: Abstract. In the paper [9] we derived first order (KKT) and second order (SSC) optimality conditions for functions defined by evaluation programs involving smooth elementals and absolute values. In that analysis, a key assumption on the local piecewise linearization was the Linear Independence Kink Qualification (LIKQ), a generalization of the Linear Independence Constraint Qualification (LICQ) known from smooth nonlinear optimization. We show here first that under LIKQ and SSC with strict complementarity, the natural algorithm of successive piecewise linear optimization with a proximal term (SPLOP) achieves a linear rate of convergence. A version of SPLOP called LiPsMin has already been implemented and tested in [10, 4]. Secondly, we observe that, even without any kink qualifications, local optimality of the nonlinear objective always requires local optimality of its piecewise linearization, and strict minimality of the latter is in fact equivalent to sharp minimality of the former. Moreover, we show that SPLOP will converge quadratically to such sharp minimizers, where the function exhibits linear growth. These results are independent of the particular function representation, and allow in particular duplications of switching variables and other intermediates. Furthermore, we derive for nonsharp minimizers necessary and sufficient optimality conditions without any kink qualification. Finally, we present numerical results to illustrate the obtained convergence results.

Keywords: Abs-Normal Form, Sharp Minimizer, Linear Independence Kink Qualification (LIKQ), Karush Kuhn Tucker (KKT), Second Order Sufficiency Condition (SSC), Strict Complementary, Linear Convergence, Quadratic Convergence

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Yachay Tech

Download: [PDF]

Entry Submitted: 11/17/2017
Entry Accepted: 11/17/2017
Entry Last Modified: 11/17/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society