An improved class of regula falsi methods of third order for solving nonlinear equations in R

A class of quadratically convergent regula falsi iterative methods for solving nonlinear equations f(x)=0 is proposed in Chen and Li (Appl. Numer. Math. 57:80–88, 2007). It is also shown there that both the sequences of diameters and iterative points sequence converge to zero simultaneously. The aim of this paper is to accelerate further the convergence of these methods from quadratic to cubic. This is done by replacing the parameter p in the iteration of Chen and Li (Appl. Numer. Math. 57:80–88, 2007) by a function p(x) defined suitably. A convergence theorem for establishing the cubic convergence of both the sequence of iterates and the sequence of diameters to the root is given. The numerical examples are worked out to demonstrate that our modified methods are more effective and comparable to those given in Chen and Li (Appl. Numer. Math. 57:80–88, 2007) as well as Newton’s method, Steffensen’s method and regula falsi method.     

Metrics with conical singularities on the sphere and sharp extensions of the theorems of Landau and Schottky

An explicit formula for the generalized hyperbolic metric on the thrice-punctured sphere ${\mathbb {P} \backslash \{z_1, z_2, z_3\}}$ with singularities of order ?? _j ?? 1 at z _j is obtained in all possible cases ?? ₁?+??? ₂?+??? ₃ >?2. The existence and uniqueness of such a metric was proved long time ago by Picard (J Reine Angew Math 130:243?C258, 1905) and Heins (Nagoya Math J 21:1?C60, 1962), while explicit formulas for the cases ?? ₁?=??? ₂?=?1 were given earlier by Agard (Ann Acad Sci Fenn Ser A I 413, 1968) and recently by Anderson et?al. (Math Z, to appear, doi:10.1007/s00209-009-0560-5). We also establish precise and explicit lower bounds for the generalized hyperbolic metric. This extends work of Hempel (J Lond Math Soc II Ser 20:435?C445, 1979) and Minda (Complex Var 8:129?C144, 1987). As applications, sharp versions of Landau- and Schottky-type theorems for meromorphic functions are obtained.     

Ergodic transport theory and piecewise analytic subactions for analytic dynamics

We consider a piecewise analytic real expanding map f: [0, 1] ?? [0, 1] of degree d which preserves orientation, and a real analytic positive potential g: [0, 1] ?? ?. We assume the map and the potential have a complex analytic extension to a neighborhood of the interval in the complex plane. We also assume log g is well defined for this extension. It is known in Complex Dynamics that under the above hypothesis, for the given potential ?? log g, where ?? is a real constant, there exists a real analytic eigenfunction ? _?? defined on [0, 1] (with a complex analytic extension) for the Ruelle operator of ?? log g. Under some assumptions we show that $\frac{1} {\beta }\log \varphi _\beta$ converges and is a piecewise analytic calibrated subaction. Our theory can be applied when log g(x) = ?log f??(x). In that case we relate the involution kernel to the so called scaling function.     

Extragradient Methods and Linesearch Algorithms for Solving Ky Fan Inequalities and Fixed Point Problems

In this paper, we introduce some new iterative methods for finding a common element of the set of points satisfying a Ky Fan inequality, and the set of fixed points of a contraction mapping in a Hilbert space. The strong convergence of the iterates generated by each method is obtained thanks to a hybrid projection method, under the assumptions that the fixed-point mapping is a ??-strict pseudocontraction, and the function associated with the Ky Fan inequality is pseudomonotone and weakly continuous. A?Lipschitz-type condition is assumed to hold on this function when the basic iteration comes from the extragradient method. This assumption is unnecessary when an Armijo backtracking linesearch is incorporated in the extragradient method. The particular case of variational inequality problems is examined in a last section.     

Behavior of DCA sequences for solving the trust-region subproblem

From our results it follows that any DCA sequence for solving the trust-region subproblem (see Pham Dinh and Le Thi, in SIAM J Optim 8:476?C505, 1998) is convergent provided that the basic matrix of the problem is nonsingular and it does not have multiple negative eigenvalues. Besides, under this additional assumption, there exists such an open set ?? containing the global minimizers and the unique local-nonglobal minimizer (if such exists) that any DCA sequence with the initial point from ?? is contained in the set and converges to a global minimizer or the local-nonglobal minimizer. Various examples are given to illustrate the limiting behavior and stability of the DCA sequences. Structure of the KKT point set of the trust-region subproblem is also analyzed.     

Inexact non-interior continuation method for monotone semidefinite complementarity problems

Chen and Tseng (Math Program 95:431?C474, 2003) extended non-interior continuation methods for solving linear and nonlinear complementarity problems to semidefinite complementarity problems (SDCP), in which a system of linear equations is exactly solved at each iteration. However, for problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a version of one of the non-interior continuation methods for monotone SDCP presented by Chen and Tseng that incorporates inexactness into the linear system solves. Only one system of linear equations is inexactly solved at each iteration. The global convergence and local superlinear convergence properties of the method are given under mild conditions.     

On the Uniqueness of the Kendall Generalized Convolution

Kendall (Foundations of a theory of random sets, in Harding, E.F., Kendall, D.G. (eds.), pp. 322?C376, Willey, New York, 1974) showed that the operation $\diamond_{1}\colon \mathcal{P}_{+}^{2}\rightarrow \mathcal{P}_{+}$ given by $$\delta_x\diamond_1\delta_1=x\pi_2+(1-x)\delta_1,$$ where x??[0,1] and ?? _?? is the Pareto distribution with the density function ?? s ^????1 on the set [1,??), defines a generalized convolution on ?₊. Kucharczak and Urbanik (Quasi-stable functions, Bull. Pol. Acad. Sci., Math. 22(3):263?C268, 1974) noticed that also the following operation $$\delta_x\diamond_{\alpha}\delta_1=x^{\alpha}\pi_{2\alpha}+\bigl(1-x^{\alpha}\bigr)\delta_1$$ defines generalized convolutions on ?₊. In this paper, we show that ? _?? convolutions are the only possible convolutions defined by the convex linear combination of two fixed measures. To be precise, we show that if ? :?²??? is a generalized convolution defined by $$\delta_x\diamond \delta_1=p(x)\lambda_1+\bigl(1-p(x)\bigr)\lambda_2,$$ for some fixed probability measures ?? ₁,?? ₂ and some continuous function p :[0,1]??[0,1], p(0)=0=1?p(1), then there exists an ??>0 such that p(x)=x ^?? , ?=? _?? , ?? ₁=?? _2?? and ?? ₂=?? ₁. We present a similar result also for the corresponding weak generalized convolution.     

Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints

In this paper, we strengthen the edge-based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655?C673, 2008) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise-aware version of ESDP_lb (??-ESDP_lb) and show that, for small noise, a small individual trace is equivalent to the sensor being accurately positioned by a certain analytic center solution. We then propose a postprocessing heuristic based on ??-ESDP_lb and a distributed algorithm to solve it. Our computational results show that, when applied to a solution obtained by solving ??-ESDP proposed of Pong and Tseng (Math. Program. doi:10.1007/s10107-009-0338-x), this heuristics usually improves the RMSD by at least 10%. Furthermore, it provides a certificate for identifying accurately positioned sensors in the refined solution, which is not common for existing refinement heuristics.     

On invariants of discrete series representations of classical p-adic groups

To an irreducible square integrable representation ?? of a classical p-adic group, M?glin has attached invariants Jord(??), ?? _cusp and ${\epsilon_\pi}$ . These triples classify square integrable representations modulo cuspidal data (assuming a natural hypothesis). The definition of these invariants in M?glin (J Eur Math Soc 4(2):143?C200, 2002) is rather simple??in terms of induced representations, except at one case when a coherent normalization of standard intertwining operators is required. In this paper we show how one can define this case also in terms of induced representations.     

Gradient Consistency for Integral-convolution Smoothing Functions

Chen and Mangasarian (Comput Optim Appl 5:97–138, 1996) developed smoothing approximations to the plus function built on integral-convolution with density functions. X. Chen (Math Program 134:71–99, 2012) has recently picked up this idea constructing a large class of smoothing functions for nonsmooth minimization through composition with smooth mappings. In this paper, we generalize this idea by substituting the plus function for an arbitrary finite max-function. Calculus rules such as inner and outer composition with smooth mappings are provided, showing that the new class of smoothing functions satisfies, under reasonable assumptions, gradient consistency, a fundamental concept coined by Chen (Math Program 134:71–99, 2012). In particular, this guarantees the desired limiting behavior of critical points of the smooth approximations.     

Iterative hard thresholding methods for l_0 regularized convex cone programming

In this paper we consider \(l_0\) regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving \(l_0\) regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an \({{\epsilon }}\) -local-optimal solution. We then propose a method for solving \(l_0\) regularized convex cone programming by applying the IHT method to its quadratic penalty relaxation and establish its iteration complexity for finding an \({{\epsilon }}\) -approximate local minimizer. Finally, we propose a variant of this method in which the associated penalty parameter is dynamically updated, and show that every accumulation point is a local izer of the problem.     

On the mean curvature of semi-Riemannian graphs in semi-Riemannian warped products

We investigate the mean curvature of semi-Riemannian graphs in the semi-Riemannian warped product M× _f ? _?? , where M is a semi-Riemannian manifold, ? _?? is the real line ? with metric ??dt ² (???=?±1), and f: M???^?+? is the warping function. We obtain an integral formula for mean curvature and some results dealing with estimates of mean curvature, among these results is a Heinz?CChern type inequality.     

Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity

An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi:, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413–431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(e^-3/2){\mathcal{O}(\epsilon^{-3/2})} iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy e{\epsilon}, and O(e^-3){\mathcal{O}(\epsilon^{-3})} iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.     

Generalized-Hukuhara penalty method for optimization problem with interval-valued functions and its application in interval-valued portfolio optimization problems

In this study, a gH-penalty method is developed to obtain efficient solutions to constrained optimization problems with interval-valued functions. The algorithmic implementation of the proposed method is illustrated. In order to develop the gH-penalty method, an interval-valued penalty function is defined and the characterization of efficient solutions of a CIOP is done. As an application of the proposed method, a portfolio optimization problem with interval-valued return is solved.     

Bump solutions for the mesoscopic Allen�CCahn equation in periodic media

Given a double-well potential F, a ${\mathbb{Z}^n}$ -periodic function H, small and with zero average, and ???>?0, we find a large R, a small ?? and a function H _?? which is ??-close to H for which the following two problems have solutions:

1. Find a set E _?? ,R whose boundary is uniformly close to ? B _R and has mean curvature equal to ?H _?? at any point,
2. Find u = u _?? ,R,?? solving $$ -\delta\,\Delta u + \frac{F'(u)}{\delta} +\frac{c_0}{2} H_\varepsilon = 0, $$ such that u _??,R,?? goes from a ??-neighborhood of +?1 in B _R to a ??-neighborhood of ?1 outside B _R .

     

A Double-Parameter Scaling Broyden–Fletcher–Goldfarb–Shanno Method Based on Minimizing the Measure Function of Byrd and Nocedal for Unconstrained Optimization

In this paper, the first two terms on the right-hand side of the Broyden–Fletcher–Goldfarb–Shanno update are scaled with a positive parameter, while the third one is also scaled with another positive parameter. These scaling parameters are determined by minimizing the measure function introduced by Byrd and Nocedal (SIAM J Numer Anal 26:727–739, 1989). The obtained algorithm is close to the algorithm based on clustering the eigenvalues of the Broyden–Fletcher–Goldfarb–Shanno approximation of the Hessian and on shifting its large eigenvalues to the left, but it is not superior to it. Under classical assumptions, the convergence is proved by using the trace and the determinant of the iteration matrix. By using a set of 80 unconstrained optimization test problems, it is proved that the algorithm minimizing the measure function of Byrd and Nocedal is more efficient and more robust than some other scaling Broyden–Fletcher–Goldfarb–Shanno algorithms, including the variants of Biggs (J Inst Math Appl 12:337–338, 1973), Yuan (IMA J Numer Anal 11:325–332, 1991), Oren and Luenberger (Manag Sci 20:845–862, 1974) and of Nocedal and Yuan (Math Program 61:19–37, 1993). However, it is less efficient than the algorithms based on clustering the eigenvalues of the iteration matrix and on shifting its large eigenvalues to the left, as shown by Andrei (J Comput Appl Math 332:26–44, 2018, Numer Algorithms 77:413–432, 2018).     

Weighted Norm Inequalities on Graphs

Let (??,??) be an infinite graph endowed with a reversible Markov kernel p and let P be the corresponding operator. We also consider the associated discrete gradient ?. We assume that ?? is doubling, a uniform lower bound for p(x,y) when p(x,y)>0, and gaussian upper estimates for the iterates of p. Under these conditions (and in some cases assuming further some Poincaré inequality) we study the comparability of (I?P)^1/2 f and ?f in Lebesgue spaces with Muckenhoupt weights. Also, we establish weighted norm inequalities for a Littlewood?CPaley?CStein square function, its formal adjoint, and commutators of the Riesz transform with bounded mean oscillation functions.     

An active set feasible method for large-scale minimization problems with bound constraints

We are concerned with the solution of the bound constrained minimization problem {minf(x), l??x??u}. For the solution of this problem we propose an active set method that combines ideas from projected and nonmonotone Newton-type methods. It is based on an iteration of the form x ^k+1=[x ^k +?? ^k d ^k ]^?, where ?? ^k is the steplength, d ^k is the search direction and [?]^? is the projection operator on the set [l,u]. At each iteration a new formula to estimate the active set is first employed. Then the components $d_{N}^{k}$ of d ^k corresponding to the free variables are determined by a truncated Newton method, and the components $d_{A}^{k}$ of d ^k corresponding to the active variables are computed by a Barzilai-Borwein gradient method. The steplength ?? ^k is computed by an adaptation of the nonmonotone stabilization technique proposed in Grippo et?al. (Numer. Math. 59:779?C805, 1991). The method is a feasible one, since it maintains feasibility of the iterates x ^k , and is well suited for large-scale problems, since it uses matrix-vector products only in the truncated Newton method for computing $d_{N}^{k}$ . We prove the convergence of the method, with superlinear rate under usual additional assumptions. An extensive numerical experimentation performed on an algorithmic implementation shows that the algorithm compares favorably with other widely used codes for bound constrained problems.     

Automorphisms of partition order-decreasing transformation monoids

Let T _n be the full transformation semigroup on a finite set X _n ={1,2,??,n}. Let ?? be an equivalence relation on X _n and ? be a total order on the partition set X _n /??. We describe all automorphisms of the partition order-decreasing transformation monoid: $$T(\rho,\preceq)=\bigl\{\alpha\in T_{n}: (x\alpha)\rho\preceq x\rho, \forall x\in X_{n}\bigr\} $$ that generalizes the results of Schreier (Fundam. Math., 28:261?C264, 1936) and ?utov (Izv. Vys?. U?ebn. Zaved., Mat., 3:177?C184, 1961).     

Calmness and Exact Penalization in Constrained Scalar Set-Valued Optimization

In this paper, we study a class of constrained scalar set-valued optimization problems, which includes scalar optimization problems with cone constraints as special cases. We introduce (local) calmness of order??? for this class of constrained scalar set-valued optimization problems. We show that the (local) calmness of order??? is equivalent to the existence of a (local) exact set-valued penalty map.