Estimating upper bounds on the limit points of majorizing sequences for Newton’s method

We present new sufficient conditions for the semilocal convergence of Newton’s method to a locally unique solution of an equation in a Banach space setting. Upper bounds on the limit points of majorizing sequences are also given. Numerical examples are provided, where our new results compare favorably to earlier ones such as Argyros (J Math Anal Appl 298:374–397, 2004), Argyros and Hilout (J Comput Appl Math 234:2993-3006, 2010, 2011), Ortega and Rheinboldt (1970) and Potra and Pták (1984).     

Proper and adjoint exhausters in nonsmooth analysis: optimality conditions

The notions of upper and lower exhausters represent generalizations of the notions of exhaustive families of upper convex and lower concave approximations (u.c.a., l.c.a.). The notions of u.c.a.’s and l.c.a.’s were introduced by Pshenichnyi (Convex Analysis and Extremal Problems, Series in Nonlinear Analysis and its Applications, 1980), while the notions of exhaustive families of u.c.a.’s and l.c.a.’s were described by Demyanov and Rubinov in Nonsmooth Problems of Optimization Theory and Control, Leningrad University Press, Leningrad, 1982. These notions allow one to solve the problem of optimization of an arbitrary function by means of Convex Analysis thus essentially extending the area of application of Convex Analysis. In terms of exhausters it is possible to describe extremality conditions, and it turns out that conditions for a minimum are expressed via an upper exhauster while conditions for a maximum are formulated in terms of a lower exhauster (Abbasov and Demyanov (2010), Demyanov and Roshchina (Appl Comput Math 4(2): 114–124, 2005), Demyanov and Roshchina (2007), Demyanov and Roshchina (Optimization 55(5–6): 525–540, 2006)). This is why an upper exhauster is called a proper exhauster for minimization problems while a lower exhauster is called a proper one for maximization problems. The results obtained provide a simple geometric interpretation and allow one to construct steepest descent and ascent directions. Until recently, the problem of expressing extremality conditions in terms of adjoint exhausters remained open. Demyanov and Roshchina (Appl Comput Math 4(2): 114–124, 2005), Demyanov and Roshchina (Optimization 55(5–6): 525–540, 2006) was the first to derive such conditions. However, using the conditions obtained (unlike the conditions expressed in terms of proper exhausters) it was not possible to find directions of descent and ascent. In Abbasov (2011) new extremality conditions in terms of adjoint exhausters were discovered. In the present paper, a different proof of these conditions is given and it is shown how to find steepest descent and ascent conditions in terms of adjoint exhausters. The results obtained open the way to constructing numerical methods based on the usage of adjoint exhausters thus avoiding the necessity of converting the adjoint exhauster into a proper one.     

Computing Final Polynomials and Final Syzygies Using Buchberger’s Gröbner Bases Method

Final polynomials and final syzygies provide an explicit representation of polynomial identities promised by Hilbert’s Nullstellensatz. Such representations have been studied independently by Bokowski [2,3,4] and Whiteley [23,24] to derive invariant algebraic proofs for statements in geometry. In the present paper we relate these methods to some recent developments in computational algebraic geometry. As the main new result we give an algorithm based on B. Buchberger’s Gröbner bases method for computing final polynomials and final syzygies over the complex numbers. Degree upper bound for final polynomials are derived from theorems of Lazard and Brownawell, and a topological criterion is proved for the existence of final syzygies. The second part of this paper is expository and discusses applications of our algorithm to real projective geometry, invariant theory and matrix theory.     

An improved local convergence analysis for a two-step Steffensen-type method

We study a class of Steffensen-type algorithm for solving nonsmooth variational inclusions in Banach spaces. We provide a local convergence analysis under ω-conditioned divided difference, and the Aubin continuity property. This work on the one hand extends the results on local convergence of Steffensen’s method related to the resolution of nonlinear equations (see Amat and Busquier in Comput. Math. Appl. 49:13–22, 2005; J. Math. Anal. Appl. 324:1084–1092, 2006; Argyros in Southwest J. Pure Appl. Math. 1:23–29, 1997; Nonlinear Anal. 62:179–194, 2005; J. Math. Anal. Appl. 322:146–157, 2006; Rev. Colomb. Math. 40:65–73, 2006; Computational Theory of Iterative Methods, 2007). On the other hand our approach improves the ratio of convergence and enlarges the convergence ball under weaker hypotheses than one given in Hilout (Commun. Appl. Nonlinear Anal. 14:27–34, 2007).     

An augmented Lagrangian approach for sparse principal component analysis

Principal component analysis (PCA) is a widely used technique for data analysis and dimension reduction with numerous applications in science and engineering. However, the standard PCA suffers from the fact that the principal components (PCs) are usually linear combinations of all the original variables, and it is thus often difficult to interpret the PCs. To alleviate this drawback, various sparse PCA approaches were proposed in the literature (Cadima and Jolliffe in J Appl Stat 22:203–214, 1995; d’Aspremont et?al. in J Mach Learn Res 9:1269–1294, 2008; d’Aspremont et?al. SIAM Rev 49:434–448, 2007; Jolliffe in J Appl Stat 22:29–35, 1995; Journée et?al. in J Mach Learn Res 11:517–553, 2010; Jolliffe et?al. in J Comput Graph Stat 12:531–547, 2003; Moghaddam et?al. in Advances in neural information processing systems 18:915–922, MIT Press, Cambridge, 2006; Shen and Huang in J Multivar Anal 99(6):1015–1034, 2008; Zou et?al. in J Comput Graph Stat 15(2):265–286, 2006). Despite success in achieving sparsity, some important properties enjoyed by the standard PCA are lost in these methods such as uncorrelation of PCs and orthogonality of loading vectors. Also, the total explained variance that they attempt to maximize can be too optimistic. In this paper we propose a new formulation for sparse PCA, aiming at finding sparse and nearly uncorrelated PCs with orthogonal loading vectors while explaining as much of the total variance as possible. We also develop a novel augmented Lagrangian method for solving a class of nonsmooth constrained optimization problems, which is well suited for our formulation of sparse PCA. We show that it converges to a feasible point, and moreover under some regularity assumptions, it converges to a stationary point. Additionally, we propose two nonmonotone gradient methods for solving the augmented Lagrangian subproblems, and establish their global and local convergence. Finally, we compare our sparse PCA approach with several existing methods on synthetic (Zou et?al. in J Comput Graph Stat 15(2):265–286, 2006), Pitprops (Jeffers in Appl Stat 16:225–236, 1967), and gene expression data (Chin et?al in Cancer Cell 10:529C–541C, 2006), respectively. The computational results demonstrate that the sparse PCs produced by our approach substantially outperform those by other methods in terms of total explained variance, correlation of PCs, and orthogonality of loading vectors. Moreover, the experiments on random data show that our method is capable of solving large-scale problems within a reasonable amount of time.     

Immersed Solutions of Plateau’s Problem for Piecewise Smooth Boundary Curves with Small Total Curvature

We provide a new proof of the classical result that any closed rectifiable Jordan curve ${\Gamma \subset \mathbb{R}^3}$ being piecewise of class C ² bounds at least one immersed minimal surface of disc-type, under the additional assumption that the total curvature of Γ is smaller than 6π. In contrast to the methods due to Osserman (Ann Math 91(2):550–569, 1970), Gulliver (Ann Math 97(2):275–305, 1973) and Alt (Math Z 127:333–362, 1972, Math Ann 201:33–35, 1973), our proof relies on a polygonal approximation technique, using the existence of immersed solutions of Plateau’s problem for polygonal boundary curves, provided by the first author’s accomplishment (The Plateau problem, Fuchsian equations and the Riemann–Hilbert problem. Mémoires de la Soc. Math. Fr. (to appear) arXiv: 1003.0978) of Garnier’s ideas in (Annales scientifiques de l’É.N.S. 45:53–144, 1928).     

The Shapley value for shortest path games: a non-graph-based approach

The shortest path games are considered in this paper. The transportation of a good in a network has costs and benefits. The problem is to divide the profit of the transportation among the players. Fragnelli et al. (Math Methods Oper Res 52: 251–264, 2000) introduce the class of shortest path games and show it coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further five characterizations of the Shapley value (Hart and Mas-Colell’s in Econometrica 57:589–614, 1989; Shapley’s in Contributions to the theory of games II, annals of mathematics studies, vol 28. Princeton University Press, Princeton, pp 307–317, 1953; Young’s in Int J Game Theory 14:65–72, 1985, Chun’s in Games Econ Behav 45:119–130, 1989; van den Brink’s in Int J Game Theory 30:309–319, 2001 axiomatizations), and conclude that all the mentioned axiomatizations are valid for the shortest path games. Fragnelli et al. (Math Methods Oper Res 52:251–264, 2000)’s axioms are based on the graph behind the problem, in this paper we do not consider graph specific axioms, we take $TU$ axioms only, that is we consider all shortest path problems and we take the viewpoint of an abstract decision maker who focuses rather on the abstract problem than on the concrete situations.     

To the question on the almost everywhere convergence of the Riesz means of double orthogonal series

Sufficient conditions of the classical type ensuring the almost everywhere (a.e.) convergence of the nonnegative-order Riesz means of double orthogonal series are indicated. Analogies of the onedimensional results of Kolmogoroff [7] and Kaczmarz?CZygmund [5, 12] have been obtained for the Cesaro means and those of Zygmund [13] for the Riesz means. These analogies establish the a.e. equiconvergence of the lacunary subsequences of rectangular partial sums and of the entire sequence of Riesz means, generalize the corresponding results of Moricz [9] for the Cesaro a.e. summability by (C, 1, 1), (C, 1, 0), and (C, 0, 1) methods of double orthogonal series, and were announced earlier without proofs in the author??s work [3].     

Preconditioning Newton–Krylov methods in nonconvex large scale optimization

We consider an iterative preconditioning technique for non-convex large scale optimization. First, we refer to the solution of large scale indefinite linear systems by using a Krylov subspace method, and describe the iterative construction of a preconditioner which does not involve matrices products or matrices storage. The set of directions generated by the Krylov subspace method is used, as by product, to provide an approximate inverse preconditioner. Then, we experience our preconditioner within Truncated Newton schemes for large scale unconstrained optimization, where we generalize the truncation rule by Nash–Sofer (Oper. Res. Lett. 9:219–221, 1990) to the indefinite case, too. We use a Krylov subspace method to both approximately solve the Newton equation and to construct the preconditioner to be used at the current outer iteration. An extensive numerical experience shows that the proposed preconditioning strategy, compared with the unpreconditioned strategy and PREQN (Morales and Nocedal in SIAM J. Optim. 10:1079–1096, 2000), may lead to a reduction of the overall inner iterations. Finally, we show that our proposal has some similarities with the Limited Memory Preconditioners (Gratton et al. in SIAM J. Optim. 21:912–935, 2011).     

Continuity of the solution mapping to parametric generalized vector equilibrium problems

In this paper, two kinds of parametric generalized vector equilibrium problems in normed spaces are studied. The sufficient conditions for the continuity of the solution mappings to the two kinds of parametric generalized vector equilibrium problems are established under suitable conditions. The results presented in this paper extend and improve some main results in Chen and Gong (Pac J Optim 3:511–520, 2010), Chen and Li (Pac J Optim 6:141–152, 2010), Chen et al. (J Glob Optim 45:309–318, 2009), Cheng and Zhu (J Glob Optim 32:543–550, 2005), Gong (J Optim Theory Appl 139:35–46, 2008), Li and Fang (J Optim Theory Appl 147:507–515, 2010), Li et al. (Bull Aust Math Soc 81:85–95, 2010) and Peng et al. (J Optim Theory Appl 152(1):256–264, 2011).     

Serre weights for rank two unitary groups

We study the weight part of (a generalisation of) Serre’s conjecture for mod $l$ Galois representations associated to automorphic representations on rank two unitary groups for odd primes $l$ . We propose a conjectural set of Serre weights, agreeing with all conjectures in the literature, and under a mild assumption on the image of the mod $l$ Galois representation we are able to show that any modular representation is modular of each conjectured weight. We make no assumptions on the ramification or inertial degrees of $l$ . Our main innovations are the use of outer forms of $\text{ GL}_2$ to avoid the parity difficulties with inner forms, and the use of the lifting techniques and “change of weight” results introduced in Barnet-Lamb et al. [J Am Math Soc 24(2):411–469, 2011; Duke Math J 161(8):1521–1580, 2012; Potential automorphy and change of weight, Preprint, 2010].     

A Kantorovich-type analysis of Broyden’s method using recurrent functions

We provide a semilocal convergence analysis for Broyden’s method for approximating locally unique solutions of nonlinear operator equations. Using the majorant principle we show that under the same or weaker hypotheses, in combination with our new idea of recurrent functions, we can find weaker sufficient conditions for the convergence of Broyden’s method as well as finer error bounds on the distances involved, and a more precise information on the location of the solution than before (Broyden, Math. Comput. 19:577–593, 1965; Chen, Ann. Inst. Stat. Math. 42:387–401, 1990; Dennis, Nonlinear Functional Analysis and Applications, pp. 425–472, Academic Press, San Diego, 1971; Li and Fukushima, Ann. Oper. Res. 103:71–97, 2001). Numerical examples are also provided involving polynomial, integral, and differential equations.     

The Dirac delta function in two settings of Reverse Mathematics

The program of Reverse Mathematics (Simpson 2009) has provided us with the insight that most theorems of ordinary mathematics are either equivalent to one of a select few logical principles, or provable in a weak base theory. In this paper, we study the properties of the Dirac delta function (Dirac 1927; Schwartz 1951) in two settings of Reverse Mathematics. In particular, we consider the Dirac Delta Theorem, which formalizes the well-known property ${\int_\mathbb{R}f(x)\delta(x)\,dx=f(0)}$ of the Dirac delta function. We show that the Dirac Delta Theorem is equivalent to weak K?nig’s Lemma (see Yu and Simpson in Arch Math Log 30(3):171–180, 1990) in classical Reverse Mathematics. This further validates the status of WWKL₀ as one of the ‘Big’ systems of Reverse Mathematics. In the context of ERNA’s Reverse Mathematics (Sanders in J Symb Log 76(2):637–664, 2011), we show that the Dirac Delta Theorem is equivalent to the Universal Transfer Principle. Since the Universal Transfer Principle corresponds to WKL, it seems that, in ERNA’s Reverse Mathematics, the principles corresponding to WKL and WWKL coincide. Hence, ERNA’s Reverse Mathematics is actually coarser than classical Reverse Mathematics, although the base theory has lower first-order strength.     

Finite simple 3′-groups are cyclic or Suzuki groups

In this note we prove that all finite simple 3′-groups are cyclic of prime order or Suzuki groups. This is well known in the sense that it is mentioned frequently in the literature, often referring to unpublished work of Thompson. Recently an explicit proof was given by Aschbacher [3], as a corollary of the classification of ${\mathcal{S}_3}$ -free fusion systems. We argue differently, following Glauberman’s comment in the preface to the second printing of his booklet [8]. We use a result by Stellmacher (see [12]), and instead of quoting Goldschmidt’s result in its full strength, we give explicit arguments along his ideas in [10] for our special case of 3′-groups.     

Imitation, local interaction, and coordination

This paper analyzes players’ long-run behavior in evolutionary coordination games with imitation and one-dimensional local interaction. Players are assumed to interact with their two neighbors and to imitate actions with the highest average payoffs. We find that the payoff-dominant equilibrium survives in the long run with positive probability. The results derive the conditions under which both risk-dominant-strategy and payoff-dominant-strategy takers co-exist in the long run. The risk-dominant equilibrium is the unique long-run equilibrium for the remaining cases. This study extends and complements the analyses of Eshel et al. (Am Econ Rev 88:157–179, 1998) and Vega-Redondo (Evolution, games, and economic behaviour, 1996). Combining Alós-Ferrer and Weidenholzer’s (Econ Lett 93:163–168, 2006; J Econ Theory 14:251–274, 2008) and our results, we conclude that players’ long-run behavior varies with imitation rules and information collecting modes. Finally, we show the convergence rate to all the long-run equilibria.     

Constructive finite free resolutions

Northcott’s book Finite Free Resolutions (1976), as well as the paper (J. Reine Angew. Math. 262/263:205–219, 1973), present some key results of Buchsbaum and Eisenbud (J. Algebra 25:259–268, 1973; Adv. Math. 12: 84–139, 1974) both in a simplified way and without Noetherian hypotheses, using the notion of latent nonzero divisor introduced by Hochster. The goal of this paper is to simplify further the proofs of these results, which become now elementary in a logical sense (no use of prime ideals, or minimal prime ideals) and, we hope, more perspicuous. Some formulations are new and more general than in the references (J. Algebra 25:259–268, 1973; Adv. Math. 12: 84–139, 1974; Finite Free Resolutions 1976) (Theorem 7.2, Lemma 8.2 and Corollary 8.5).     

Additive Results of the Drazin Inverse for Bounded Linear Operators

Given two bounded linear operators $P$ and $Q$ on a Banach space the formula for the Drazin inverse of $P+Q$ is given, under the assumptions $P^2 Q+PQ^2=0$ and $P^3 Q=PQ^3=0$ . In particular, some recent results arising in Drazin (Am Math Mon 65:506–514, 1958), Hartwig et al. (Linear Algebra Appl 322:207–217, 2001) and Castro-González et al. (J Math Anal Appl 350:207–215, 2009) are extended.     

On Ulm’s method for Fréchet differentiable operators

We provide new sufficient convergence conditions for the semilocal convergence of Ulm’s method (Izv. Akad. Nauk Est. SSR 16:403–411, 1967) in order to approximate a locally unique solution of an equation in a Banach space setting. We show that in some cases, our hypotheses hold true but the corresponding ones (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) do not. We also show that under the same hypotheses and computational cost as (Burmeister in Z. Angew. Math. Mech. 52:101–110, 1972; Kornstaedt in Aequ. Math. 13:21–45, 1975; Petzeltova in Comment. Math. Univ. Carol. 21:719–725, 1980; Potra and Ptǎk in Cas. Pest. Mat. 108:333–341, 1983; Ulm in Izv. Akad. Nauk Est. SSR 16:403–411, 1967) finer error sequences can be obtained. Numerical examples are also provided further validating the results.     

Linear SPDEs Driven by Stationary Random Distributions

Using tools from the theory of stationary random distributions developed in It? (Mem. Coll. Sci., Univ. Kyoto, Ser. A: Math., 28:209?C223,?1954) and Yaglom (Theory Probab. Appl., 2:273?C320,?1957), we introduce a new class of processes which can be used as a model for the noise perturbing an SPDE. This type of noise is not necessarily Gaussian, but it includes the spatially homogeneous Gaussian noise introduced in Dalang (Electron. J. Probab. 4(6)?1999), and the fractional noise considered in Balan and Tudor (Stoch. Process. Appl., 120:2468?C2494,?2010). We derive some general conditions for the existence of a random field solution of a linear SPDE with this type of noise, under some mild conditions imposed on the Green function of the differential operator which appears in this equation. This methodology is applied to the study of the heat and wave equations (possibly replacing the Laplacian by one of its fractional powers), extending in this manner the results of Balan and Tudor (Stoch. Process. Appl., 120:2468?C2494,?2010) to the case H<1/2.