Search

In this paper, we consider the tensor absolute value equations (TAVEs). When one tensor is row diagonal with odd order, we show that the TAVEs can be reduced to an algebraic equation; when it is row diagonal and nonsingular with even order, we prove that the TAVEs is equivalent to a polynomial complementary problem. When no tensor is row diagonal, we formulate the TAVEs equivalently as polynomial optimization problems in two different ways. Each of them can be solved by Lasserre's hierarchy of semideflnite relaxations. The finite convergence properties are also discussed. Numerical experiments show the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

The reconstruction of a function from its spectrogram (i.e., the absolute value of its short-time Fourier transform (STFT)) arises as a key problem in several important applications, including coherent diffraction imaging and audio processing. It is a classical result that for suitable windows any function can, in principle, be uniquely recovered up to a global phase factor from its spectrogram. However, for most practical applications only discrete samples--typically from a lattice--of the spectrogram are available. This raises the question of whether lattice samples of the spectrogram contain sufficient information for determining a function f Є L²(Rd) up to a global phase factor. In the present paper, we answer this question in the negative by providing general nonidentifiability results which lead to a non-uniqueness theory for the sampled STFT phase retrieval problem. Precisely, given any dimension d, any window function g, and any (symplectic or separable) lattice L < Rd, we construct pairs of functions f,h Є L²(Rd) that do not agree up to a global phase factor, but whose spectrograms agree on L. Our techniques are sufficiently flexible to produce counterexamples to unique recoverability under even more stringent assumptions; for example, if the window function is real-valued, the functions f,h can even be chosen to satisfy | f| =| h|. Our results thus reveal the non-existence of a critical sampling density in the absence of phase information, a property which is in stark contrast to uniqueness results in time-frequency analysis. [ABSTRACT FROM AUTHOR]

A typo in the paper [M. Hladík, SIAM J. Matrix Anal. Appl., 44 (2023), pp. 175-195] is corrected. [ABSTRACT FROM AUTHOR]

The ubiquity of semilinear parabolic equations is clear from their numerous applications ranging from physics and biology to materials and social sciences. In this paper, we consider a practically desirable property for a class of semilinear parabolic equations of the abstract form ut = u + f[u], with a linear dissipative operator and f a nonlinear operator in space, namely, a time-invariant maximum bound principle, in the sense that the timedependent solution u preserves for all time a uniform pointwise bound in absolute value imposed by its initial and boundary conditions. We first study an analytical framework for sufficient conditions on and f that lead to such a maximum bound principle for the time-continuous dynamic system of infinite or finite dimensions. Then we utilize a suitable exponential time-differencing approach with a properly chosen generator of the contraction semigroup to develop first- and second-order accurate temporal discretization schemes that satisfy the maximum bound principle unconditionally in the time-discrete setting. Error estimates of the proposed schemes are derived along with their energy stability. Extensions to vector- and matrix-valued systems are also discussed. We demonstrate that the abstract framework and analysis techniques developed here offer an effective and unified approach to studying the maximum bound principle of the abstract evolution equation that covers a wide variety of well-known models and their numerical discretization schemes. Some numerical experiments are also carried out to verify the theoretical results. [ABSTRACT FROM AUTHOR]

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]

The maximum bound principle (MBP) is an important property for a large class of semilinear parabolic equations, in the sense that the time-dependent solution of the equation with appropriate initial and boundary conditions and nonlinear operator preserves for all time a uniform pointwise bound in absolute value. It has been a challenging problem to design unconditionally MBPpreserving high-order accurate time-stepping schemes for these equations. In this paper, we combine the integrating factor Runge--Kutta (IFRK) method with the linear stabilization technique to develop a stabilized IFRK (sIFRK) method, and we successfully derive sufficient conditions for the proposed method to preserve the MBP unconditionally in the discrete setting. We then elaborate some sIFRK schemes with up to the third-order accuracy, which are proven to be unconditionally MBP-preserving by verifying these conditions. In addition, it is shown that many classic strong stability-preserving sIFRK schemes do not satisfy these conditions except the first-order one. Extensive numerical experiments are also carried out to demonstrate the performance of the proposed method. [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]

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v1, . . ., vm È Rd and a constraint family B \subseteq 2[m], find a set S ÈB that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = ([m] r), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [J. Complexity, 11 (1995) pp. 138--153] who gave an rO(r) approximation algorithm for a special case of this problem. Recently, Nikolov and Singh [Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 192-- 201] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when \scrB corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, ACM, 2006, pp. 417--426], and was recently extended to regular matroids [Straszak and Vishnoi, Proceedings of the Forty-ninth ACM SIGACT Symposium on Theory of Computing, 2017, pp. 370--383] and [Anaris and Gharan, Proceedings of the Forty-ninth Annual SIGACT Symposium on Theory of Computing, 2017, pp. 384--396] and general matroids [Anari, Gharan, and Vinzant, Proceedings of the Fifty-ninth IEEE Annual Symposium on Foundations of Computer Science, 2018, pp. 35-- 46]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms--that also output a set--remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem, for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions, which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena have recently been deployed. [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]