On the complexity of finding first-order critical points in constrained nonlinear optimization

The complexity of finding $\epsilon $ -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $O(\epsilon ^{-2})$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.     

First-order algorithm with {\mathcal{O}({\rm ln}(1{/}\epsilon))} convergence for {\epsilon}-equilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ${\epsilon}$ -equilibrium to this min-max problem in ${\mathcal {O}\left(\frac{\|A\|}{\delta(A)} \, {\rm ln}(1{/}\epsilon)\right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${\mathcal {O}(1{/}\epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${\epsilon}$ . Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s method with an outer loop that lowers the target ${\epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). Computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).     

Solving structured nonsmooth convex optimization with complexity $$\mathcal {O}(\varepsilon ^{-1/2})$$

This paper describes an algorithm for solving structured nonsmooth convex optimization problems using the optimal subgradient algorithm (OSGA), which is a first-order method with the complexity \(\mathcal {O}(\varepsilon ^{-2})\) for Lipschitz continuous nonsmooth problems and \(\mathcal {O}(\varepsilon ^{-1/2})\) for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem so that it can be solved efficiently by a new setup of OSGA (called OSGA-V) with the complexity \(\mathcal {O}(\varepsilon ^{-1/2})\). Further, to solve the reformulated problem, we equip OSGA-O with an appropriate prox-function for which the OSGA-O subproblem can be solved either in a closed form or by a simple iterative scheme, which decreases the computational cost of applying the algorithm for large-scale problems. We show that applying the new scheme is feasible for many problems arising in applications. Some numerical results are reported confirming the theoretical foundations.     

Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization

In a recent paper, we introduced a trust-region method with variable norms for unconstrained minimization, we proved standard asymptotic convergence results, and we discussed the impact of this method in global optimization. Here we will show that, with a simple modification with respect to the sufficient descent condition and replacing the trust-region approach with a suitable cubic regularization, the complexity of this method for finding approximate first-order stationary points is \(O(\varepsilon ^{-3/2})\). We also prove a complexity result with respect to second-order stationarity. Some numerical experiments are also presented to illustrate the effect of the modification on practical performance.     

New generalized cyclotomic binary sequences of period $$p^2$$

New generalized cyclotomic binary sequences of period \(p^2\) are proposed in this paper, where p is an odd prime. The sequences are almost balanced and their linear complexity is determined. The result shows that the proposed sequences have very large linear complexity if p is a non-Wieferich prime.     

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for \(p\ge 1\)) and to assume Lipschitz continuity of the p-th derivative, then an \(\epsilon \)-approximate first-order critical point can be computed in at most \(O(\epsilon ^{-(p+1)/p})\) evaluations of the problem’s objective function and its derivatives. This generalizes and subsumes results known for \(p=1\) and \(p=2\).     

Logical laws for existential monadic second-order sentences with infinite first-order parts

We consider existential monadic second-order sentences ?X φ(X) about undirected graphs, where ?X is a finite sequence of monadic quantifiers and φ(X) ∈ +_∞ω^ω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.     

Supersound many-valued logics and Dedekind-MacNeille completions

In Hájek et al. (J Symb Logic 65(2):669–682, 2000) the authors introduce the concept of supersound logic, proving that first-order Gödel logic enjoys this property, whilst first-order ?ukasiewicz and product logics do not; in Hájek and Shepherdson (Ann Pure Appl Logic 109(1–2):65–69, 2001) this result is improved showing that, among the logics given by continuous t-norms, Gödel logic is the only one that is supersound. In this paper we will generalize the previous results. Two conditions will be presented: the first one implies the supersoundness and the second one non-supersoundness. To develop these results we will use, between the other machineries, the techniques of completions of MTL-chains developed in Labuschagne and van Alten (Proceedings of the ninth international conference on intelligent technologies, 2008) and van Alten (2009). We list some of the main results. The first-order versions of MTL, SMTL, IMTL, WNM, NM, RDP are supersound; the first-order version of an axiomatic extension of BL is supersound if and only it is n-potent (i.e. it proves the formula \({\varphi^{n}\,\to\,\varphi^{n\,{+}\,1}}\) for some \({n\,\in\,\mathbb{N}^+}\)). Concerning the negative results, we have that the first-order versions of ΠMTL, WCMTL and of each non-n-potent axiomatic extension of BL are not supersound.     

From error bounds to the complexity of first-order descent methods for convex functions

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-?ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Hölderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple method: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form \(O(q^{k})\) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with \(\ell ^1\) regularization.     

On the O(1/t) convergence rate of the LQP prediction–correction method

The logarithmic-quadratic proximal (abbreviated by LQP) prediction–correction method is attractive for structured monotone variational inequalities, and it ensures the global convergence under some suitable conditions. In this paper, we are interested in investigating the convergence rate of the LQP prediction–correction method. Motivated by the research work about the convergence rate or iteration complexity for various first-order algorithms in the literature, we provide a simple proof to show the $O(1/t)$ convergence rate for the LQP prediction–correction method.     

A sharp estimate for the Hilbert transform along finite order lacunary sets of directions

We prove, in ZFC, that there is an infinite strictly descending chain of classes of theories in Keisler’s order. Thus Keisler’s order is infinite and not a well order. Moreover, this chain occurs within the simple unstable theories, considered model-theoretically tame. Keisler’s order is a central notion of the model theory of the 60s and 70s which compares first-order theories, and implicitly ultrafilters, according to saturation of ultrapowers. Prior to this paper, it was long thought to have finitely many classes, linearly ordered. The model-theoretic complexity we find is witnessed by a very natural class of theories, the n-free k-hypergraphs studied by Hrushovski. This complexity reflects the difficulty of amalgamation and appears orthogonal to forking.     

A Lower Bound for the Determinantal Complexity of a Hypersurface

We prove that the determinantal complexity of a hypersurface of degree \(d > 2\) is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least 5. As a result, we obtain that the determinantal complexity of the \(3 \times 3\) permanent is 7. We also prove that for \(n> 3\), there is no nonsingular hypersurface in \({\mathbb {P}}^n\) of degree d that has an expression as a determinant of a \(d \times d\) matrix of linear forms, while on the other hand for \(n \le 3\), a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is 5.     

An interior point algorithm ofO(\sqrt m \left| {\ln \varepsilon } \right|) iterations forC 1-convex programming

We present a theoretical result on a path-following algorithm for convex programs. The algorithm employs a nonsmooth Newton subroutine. It starts from a near center of a restricted constraint set, performs a partial nonsmooth Newton step in each iteration, and converges to a point whose cost is within accuracy of the optimal cost in iterations, wherem is the number of constraints in the problem. Unlike other interior point methods, the analyzed algorithm only requires a first-order Lipschitzian condition and a generalized Hessian similarity condition on the objective and constraint functions. Therefore, our result indicates the theoretical feasibility of applying interior point methods to certainC ¹-optimization problems instead ofC ²-problems. Since the complexity bound is unchanged compared with similar algorithms forC ²-convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.This author's work is supported in part by the National Science Foundation of the USA under grant DDM-8721709.This author's work is supported in part by the Australian Research Council.     

Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

Adaptive Wavelet Methods for Linear and Nonlinear Least-Squares Problems

The adaptive wavelet Galerkin method for solving linear, elliptic operator equations introduced by Cohen et al. (Math Comp 70:27–75, 2001) is extended to nonlinear equations and is shown to converge with optimal rates without coarsening. Moreover, when an appropriate scheme is available for the approximate evaluation of residuals, the method is shown to have asymptotically optimal computational complexity. The application of this method to solving least-squares formulations of operator equations $G(u)=0$ , where $G:H \rightarrow K'$ , is studied. For formulations of partial differential equations as first-order least-squares systems, a valid approximate residual evaluation is developed that is easy to implement and quantitatively efficient.     

A Complex Analogue of Toda’s Theorem

Toda (SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result (with a compactness hypothesis) in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines (Blum et al. in Bull. Am. Math. Soc. 21(1):1–46, 1989) was proved in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010). Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, the proof in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) is topological in nature; the properties of the topological join are used in a fundamental way. However, the constructions used in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) were semi-algebraic—they used real inequalities in an essential way and as such do not extend to the complex case. In this paper, we extend the techniques developed in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) to the complex projective case. A key role is played by the complex join of quasi-projective complex varieties. As a consequence, we obtain a complex analogue of Toda’s theorem. The results of this paper, combined with those in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010), illustrate the central role of the Poincaré polynomial in algorithmic algebraic geometry, as well as in computational complexity theory over the complex and real numbers: the ability to compute it efficiently enables one to decide in polynomial time all languages in the (compact) polynomial hierarchy over the appropriate field.     

Second-Order Optimality and Beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order \(\epsilon \)-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order \(q \ge 1\) can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most \(O(\epsilon ^{-(q+1)})\) evaluations of f and its derivatives to compute an \(\epsilon \)-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.     

Condition Length and Complexity for the Solution of Polynomial Systems

Smale’s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale’s problem is Beltrán and Pardo (Found Comput Math 11(1):95–129, 2011) and Bürgisser and Cucker (Ann Math 174(3):1785–1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Bürgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014).     

Set Theory is Interpretable in the Automorphism Group of an Infinitely Generated Free Group

In [6] S. Shelah showed that in the endomorphism semi-groupof an infinitely generated algebra which is free in a varietyone can interpret some set theory. It follows from his resultsthat, for an algebra F which is free of infinite rank in avariety of algebras in a language L, if > |L|, then thefirst-order theory of the endomorphism semi-group of F, Th(End(F)),syntactically interprets Th(,L₂), the second-order theory ofthe cardinal . This means that for any second-order sentence of empty language there exists *, a first-order sentence ofsemi-group language, such that for any infinite cardinal >|L|, Th(,L₂)*Th(End(F)) In his paper Shelah notes that it is natural to study a similarproblem for automorphism groups instead of endomorphism semi-groups;a priori the expressive power of the first-order logic for automorphismgroups is less than the one for endomorphism semi-groups. Forinstance, according to Shelah's results on permutation groups[4, 5], one cannot interpret set theory by means of first-orderlogic in the permutation group of an infinite set, the automorphismgroup of an algebra in empty language. On the other hand, onecan do this in the endomorphism semi-group of such an algebra. In [7, 8] the author found a solution for the case of the varietyof vector spaces over a fixed field. If V is a vector spaceof an infinite dimension over a division ring D, then the theoryTh(, L₂) is interpretable in the first-order theory of GL(V),the automorphism group of V. When a field D is countable anddefinable up to isomorphism by a second-order sentence, thenthe theories Th(GL(V)) and Th(, L₂) are mutually syntacticallyinterpretable. In the general case, the formulation is a bitmore complicated. The main result of this paper states that a similar result holdsfor the variety of all groups.