Search

Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max and min operators are piecewise smooth. They can be approximated by piecewise linear functions in abs-linear form. Using this second-order approximation, in [Optim. Methods Softw., 31 (2016), pp. 904–930] we derived local first- and second-order minimality conditions for the underlying piecewise smooth functions. They are necessary and sufficient, respectively. These generalizations of the classical KKT and sufficient second-order theory assumed that the given abslinear approximation satisfies the linear independence kink qualification (LIKQ). In this paper we relax LIKQ to the Mangasarian–Fromovitz kink qualification (MFKQ) and develop constructive conditions for several local convexity concepts. These are the existence of a supporting hyperplane at a given point for the function itself (SUP), the same for its local piecewise linearization (FOS), and the convexity of its local piecewise linearization on a neighborhood (FOC). As a consequence we show that first-order convexity in the sense of (FOC) is always required by subdifferential regularity (REG) as defined in Rockafellar and Wets [Variational Analysis, Springer, Cham, 1998], and is even equivalent to it under MFKQ. Whereas it was observed by Griewank and Walther that testing for local minimality (MIN) is polynomial under LIKQ, in this paper we show that, even under this strong linear independence kink qualification, testing for FOC and thus REG is co-NP-complete. We conjecture that this is also true for testing MFKQ itself. [ABSTRACT FROM AUTHOR]

Machine learning problems such as neural network training, tensor decomposition, and matrix factorization require local minimization of a nonconvex function. This local minimization is challenged by the presence of saddle points, of which there can be many and from which descent methods may take an inordinately large number of iterations to escape. This paper presents a secondorder method that modifies the update of Newton's method by replacing the negative eigenvalues of the Hessian by their absolute values and uses a truncated version of the resulting matrix to account for the objective's curvature. The method is shown to escape saddles in at most 1 + log3/2(δ/2ε) iterations, where ε is the target optimality and δ characterizes a point sufficiently far away from the saddle. This base of this exponential escape is 3/2 independently of problem constants. Adding classical properties of Newton's method, the paper proves convergence to a local minimum with probability 1 - p in O (log(1/p)) + O(log(1/ε)) iterations. [ABSTRACT FROM AUTHOR]

Machine learning problems such as neural network training, tensor decomposition, and matrix factorization require local minimization of a nonconvex function. This local minimization is challenged by the presence of saddle points, of which there can be many and from which descent methods may take an inordinately large number of iterations to escape. This paper presents a secondorder method that modifies the update of Newton's method by replacing the negative eigenvalues of the Hessian by their absolute values and uses a truncated version of the resulting matrix to account for the objective's curvature. The method is shown to escape saddles in at most 1 + log3/2(δ/2ε) iterations, where δ is the target optimality and ε characterizes a point sufficiently far away from the saddle. This base of this exponential escape is 3/2 independently of problem constants. Adding classical properties of Newton's method, the paper proves convergence to a local minimum with probability 1 p in O (log(1/p)) + O(log(1/ε) iterations. [ABSTRACT FROM AUTHOR]

In this paper, we develop convergence analysis of a modified line search method for objective functions whose value is computed with noise and whose gradient estimates are inexact and possibly random. The noise is assumed to be bounded in absolute value without any additional assumptions. We extend the framework based on stochastic methods from [C. Cartis and K. Scheinberg, Math. Program., 169 (2018), pp. 337-375] which was developed to provide analysis of a standard line search method with exact function values and random gradients to the case of noisy functions. We introduce two alternative conditions on the gradient which, when satisfied with some sufficiently large probability at each iteration, guarantees convergence properties of the line search method. We derive expected complexity bounds to reach a near optimal neighborhood for convex, strongly convex and nonconvex functions. The exact dependence of the convergence neighborhood on the noise is specified. [ABSTRACT FROM AUTHOR]

In the paper [Optim. Methods Softw., 31 (2016), pp. 904-930] we derived first order (KKT) and second order (second order sufficiency condition (SOSC)) 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. Firstly, we show here that under LIKQ and SOSC with strict complementarity, the natural algorithm of successive abs-linear minimization with a proximal term (SALMIN) achieves a linear rate of convergence. A version of SALMIN called LiPsMin has already been implemented and tested in [Math. Program., 158 (2016), pp. 383{415; Math. Program. (2018), https://doi.org/10.1007/s10107-018-1273-5]. 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 SALMIN 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. [ABSTRACT FROM AUTHOR]

In the paper [Optim. Methods Softw., 31 (2016), pp. 904{930] we derived first order (KKT) and second order (second order suffciency condition (SOSC)) 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. Firstly, we show here that under LIKQ and SOSC with strict complementarity, the natural algorithm of successive abs-linear minimization with a proximal term (SALMIN) achieves a linear rate of convergence. A version of SALMIN called LiPsMin has already been implemented and tested in [Math. Program., 158 (2016), pp. 383{415; Math. Program. (2018), https://doi.org/10.1007/s10107-018-1273-5]. 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 SALMIN 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 suffcient optimality conditions without any kink qualification. Finally, we present numerical results to illustrate the obtained convergence results. [ABSTRACT FROM AUTHOR]