Convergence of a hybrid algorithm for a reversible semigroup of nonlinear operators in Banach spaces

The purpose of this paper is to study hybrid iterative schemes of Halpern types for a semigroup ℑ={T(s):s∈S} of relatively nonexpansive mappings on a closed and convex subset C of a Banach space with respect to a sequence {μ_n} of asymptotically left invariant means defined on an appropriate invariant subspace of l^∞(S). We prove that given a certain sequence {α_n} in [0,1], x∈C, we can generate an iterative sequence {x_n} which converges strongly to Π_F(ℑ)x where Π_F(ℑ)x is the generalized projection from C onto the fixed point set F(ℑ). Our main result is even new for the case of a Hilbert space.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

New Coins from Old, Smoothly

Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O’Brien (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (N<∞) equal to 1 exists if and only if f is continuous. Nacu and Peres (Ann. Appl. Probab. 15(1A):93–115, 2005) proved that f is real analytic in an open set S⊂(0,1) if and only if such a simulation scheme exists with the probability ℙ _p (N>n) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, f is in the space C ^α [0,1] if and only if a simulation scheme as above exists with ℙ _p (N>n)≤C(Δ _n (p)) ^α , where \varDelta _n(x):=max{?{x(1-x)/n},1/n}\varDelta _{n}(x):=\max\{\sqrt{x(1-x)/n},1/n\}. The key to the proof is a new result in approximation theory: Let B⁺_n\mathcal{B}^{+}_{n} be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in C ^α [0,1] if and only if f has a series representation ?_n=1^￥F_n\sum_{n=1}^{\infty}F_{n} with F_n ? B⁺_nF_{n}\in \mathcal{B}^{+}_{n} and ∑ _k>n F _k (x)≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (Math. Ann. 151:239–251, 1963), who claimed that if some j_n ? B⁺_n\varphi_{n}\in\mathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1, then f∈C ^α [0,1].     

A new method of proof of Filippov’s theorem based on the viability theorem

Filippov??s theorem implies that, given an absolutely continuous function y: [t ₀; T] ?? ? ^d and a set-valued map F(t, x) measurable in t and l(t)-Lipschitz in x, for any initial condition x ₀, there exists a solution x(·) to the differential inclusion x??(t) ?? F(t, x(t)) starting from x ₀ at the time t ₀ and satisfying the estimation $$\left| {x(t) - y(t)} \right| \leqslant r(t) = \left| {x_0 - y(t_0 )} \right|e^{\int_{t_0 }^t {l(s)ds} } + \int_{t_0 }^t \gamma (s)e^{\int_s^t {l(\tau )d\tau } } ds,$$ where the function ??(·) is the estimation of dist(y??(t), F(t, y(t))) ?? ??(t). Setting P(t) = {x ?? ? ⁿ : |x ?y(t)| ?? r(t)}, we may formulate the conclusion in Filippov??s theorem as x(t) ?? P(t). We calculate the contingent derivative DP(t, x)(1) and verify the tangential condition F(t, x) ?? DP(t, x)(1) ?? ?. It allows to obtain Filippov??s theorem from a viability result for tubes.     

Equality of two variable weighted means: reduction to differential equations

Summary. Let F, Y \Phi, \Psi be strictly monotonic continuous functions, F,G be positive functions on an interval I and let n ? \Bbb N \{1} n \in {\Bbb N} \setminus \{1\} . The functional equation¶¶F^-1 ([(?_i=1ⁿF(x_i)F(x_i))/(?_i=1ⁿ F(x_i)]) Y^-1 ([(?_i=1ⁿY(x_i)G(x_i))/(?_i=1ⁿ G(x_i))])  (x₁,?,x_n ? I) \Phi^{-1}\,\left({\sum\limits_{i=1}^{n}\Phi(x_{i})F(x_{i})\over\sum\limits_{i=1}^{n} F(x_{i}}\right) \Psi^{-1}\,\left({\sum\limits_{i=1}^{n}\Psi(x_{i})G(x_{i})\over\sum\limits_{i=1}^{n} G(x_{i})}\right)\,\,(x_{1},\ldots,x_{n} \in I) ¶was solved by Bajraktarevi' [3] for a fixed n 3 3 n\ge 3 . Assuming that the functions involved are twice differentiable he proved that the above functional equation holds if and only if¶¶Y(x) = [(aF(x) + b)/(cF(x) + d)],       G(x) = kF(x)(cF(x) + d) \Psi(x) = {a\Phi(x)\,+\,b\over c\Phi(x)\,+\,d},\qquad G(x) = kF(x)(c\Phi(x) + d) ¶where a,b,c,d,k are arbitrary constants with k(c²+d²)(ad-bc) 1 0 k(c^2+d^2)(ad-bc)\ne 0 . Supposing the functional equation for all n = 2,3,... n = 2,3,\dots Aczél and Daróczy [2] obtained the same result without differentiability conditions.¶The case of fixed n = 2 is, as in many similar problems, much more difficult and allows considerably more solutions. Here we assume only that the same functional equation is satisfied for n = 2 and solve it under the supposition that the functions involved are six times differentiable. Our main tool is the deduction of a sixth order differential equation for the function j = F°Y^-1 \varphi = \Phi\circ\Psi^{-1} . We get 32 new families of solutions.     

A compact updating formula for quasi-Newton minimization algorithms

Quasi-Newton algorithms minimize a functionF(x),x ∈R ⁿ, searching at any iterationk along the directions _k=?H _kg_k, whereg _k=?F(x _k) andH _k approximates in some sense the inverse Hessian ofF(x) atx _k. When the matrixH is updated according to the formulas in Broyden's family and when an exact line search is performed at any iteration, a compact algorithm (free from the Broyden's family parameter) can be conceived in terms of the followingn ×n matrix: $$H{_R} = H - Hgg{^T} H/g{^T} Hg,$$ which can be viewed as an approximating reduced inverse Hessian. In this paper, a new algorithm is proposed which uses at any iteration an (n?1)×(n?1) matrixK related toH _R by $$H_R = Q\left[ {\begin{array}{*{20}c} 0 & 0 \\ 0 & K \\ \end{array} } \right]Q$$ whereQ is a suitable orthogonaln×n matrix. The updating formula in terms of the matrixK incorporated in this algorithm is only moderately more complicated than the standard updating formulas for variable-metric methods, but, at the same time, it updates at any iteration a positive definite matrixK, instead of a singular matrixH _R. Other than the compactness with respect to the algorithms with updating formulas in Broyden's class, a further noticeable feature of the reduced Hessian algorithm is that the downhill condition can be stated in a simple way, and thus efficient line searches may be implemented.     

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function f: {0,1} ⁿ → {?1,+1} is the least degree of a real polynomial p with f(x) ≡ sgnp(x). We prove that the intersection of two halfspaces on {0,1} ⁿ has threshold degree Ω(n), which matches the trivial upper bound and solves an open problem due to Klivans (2002). The best previous lower bound was Ω({ie73-1}). Our result shows that the intersection of two halfspaces on {0,1} ⁿ only admits a trivial {ie73-2}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas.     

Generalized monotone approximation inL p Space

Letf(x) ∈L _p[0,1], 1?p? ∞. We shall say that functionf(x)∈Δ^k (integerk?1) if for anyh ∈ [0, 1/k] andx ∈ [0,1?kh], we have Δ _h ^k f(x)?0. Denote by ∏ _n the space of algebraic polynomials of degree not exceedingn and define $$E_{n,k} (f)_p : = \mathop {\inf }\limits_{\mathop {P_n \in \prod _n }\limits_{P_n^{(\lambda )} \geqslant 0} } \parallel f(x) - P_n (x)\parallel _{L_p [0,1]} .$$ We prove that for any positive integerk, iff(x) ∈ Δ ^k ∩ L _p[0, 1], 1?p?∞, then we have $$E_{n,k} (f)_p \leqslant C\omega _2 \left( {f,\frac{1}{n}} \right)_p ,$$ whereC is a constant only depending onk.     

On thin-complete ideals of subsets of groups

Let F ì P_G \mathcal{F} \subset {\mathcal{P}_G} be a left-invariant lower family of subsets of a group G. A subset A ⊂ G is called F \mathcal{F} -thin if xA ?yA ? F xA \cap yA \in \mathcal{F} for any distinct elements x, y ∈ G. The family of all F \mathcal{F} -thin subsets of G is denoted by t( F ) \tau \left( \mathcal{F} \right) . If t( F ) = F \tau \left( \mathcal{F} \right) = \mathcal{F} , then F \mathcal{F} is called thin-complete. The thin-completion t^*( F ) {\tau^*}\left( \mathcal{F} \right) of F \mathcal{F} is the smallest thin-complete subfamily of P_G {\mathcal{P}_G} that contains F \mathcal{F} . Answering questions of Lutsenko and Protasov, we prove that a set A ⊂ G belongs to τ*(G) if and only if, for any sequence (g _n ) _n∈ω of nonzero elements of G, there is n ∈ ω such that

Asymptotic properties of least squares estimators for discrete compound distributions

Let (X, Λ) be a pair of random variables, where Λ is an Ω (a compact subset of the real line) valued random variable with the density functiong(Θ: α) andX is a real-valued random variable whose conditional probability function given Λ=Θ is P {X=x|Θ} withx=x ₀, x₁, …. Based onn independent observations ofX, x ⁽ⁿ⁾, we are to estimate the true (unknown) parameter vectorα=(α ₁, α₂, ...,α_m) of the probability function ofX, P_α(X=∫_ΩP{X=x|Θ}g(Θ:α)dΘ. A least squares estimator of α is any vector \(\hat \alpha \left( {X^{\left( n \right)} } \right)\) which minimizes $$n^{ - 1} \sum\limits_{i = 1}^n {\left( {P_\alpha \left( {x_i } \right) - fn\left( {x_i } \right)} \right)^2 } $$ wherex ⁽ⁿ⁾=(x₁, x₂,…,x _n) is a random sample ofX andf _n(x_i)=[number ofx _i inx ⁽ⁿ⁾]/n. It is shown that the least squares estimators exist as a unique solution of the normal equations for all sufficiently large sample size (n) and the Gauss-Newton iteration method of obtaining the estimator is numerically stable. The least squares estimators converge to the true values at the rate of \(O\left( {\sqrt {2\log \left( {{{\log n} \mathord{\left/ {\vphantom {{\log n} n}} \right. \kern-0em} n}} \right)} } \right)\) with probability one, and has the asymptotically normal distribution.     

Stability of the Graph of a Convex Function

Let x: M → A ⁿ⁺¹ be the graph of some strongly convex function x ⁿ+1= ?( x₁,…,x_n) defined on a domain Ω ? A ⁿ in a real affine space. We consider the relative metric G, defined by $ G=\sum{\partial^{2}f\over\partial x_{i}\partial x_{j}}dx_{i}dx_{j}$ .In this paper, we calculate the second variation of the area integral with respect to the relative metric G. We prove that the parabolic affine hyperspheres are stable.     

Linear transformations of monotone functions on the discrete cube

For a function f:{0,1}ⁿ→R and an invertible linear transformation L∈GL_n(2), we consider the function Lf:{0,1}ⁿ→R defined by Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if f is Boolean and monotone then I(Lf)≥I(f), where I(f) is the total influence of f. Second, we conjecture that if both f and L(f) are monotone, then f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where L is upper triangular.     

Connection-graph and iteration-graph of monotone boolean functions

In this paper, we establish some relationships between the circuits of the connection-graph G_C(F), and the circuits of theiteration-graph G₁(F), of a monotone boolean function F. We first show that if G₁(F) contains an element circuit of length multiple of p? {2,3}, then G_C(F) contains an elementary circuit of length multiple of p; then we prove that if G_C(F) is a subgraph of a caterpillar, then G₁(F) is a subgraph of a tree; at last we exhibit an infinite family of monotone boolean functions {F_n; n = 2 × 5^q, q ≥ 1} such that any G_C(F_n) is a subgraph of a tree, and G₁(F_n) contains a circuit of length 2^q+1, i.e., of the order $\text{n}{}^{\mathrm{<mtext>log</mtext><mtext>2</mtext><mtext>log5</mtext>}}$.     

From Chaos to Global Convergence

The main purpose of this paper is to investigate dynamical systems F : \mathbbR² ? \mathbbR²{F : \mathbb{R}^2 \rightarrow \mathbb{R}^2} of the form F(x, y) = (f(x, y), x). We assume that f : \mathbbR² ? \mathbbR{f : \mathbb{R}^2 \rightarrow \mathbb{R}} is continuous and satisfies a condition that holds when f is non decreasing with respect to the second variable. We show that for every initial condition x₀ = (x ₀, y ₀), such that the orbit

Finite determinacy and Whitney equisingularity of map germs from {\mathbb{C}^n} to {\mathbb{C}^{2n-1}}

We show that a holomorphic map germ ${f : (\mathbb{C}^n,0)\to(\mathbb{C}^{2n-1},0)}$ is finitely determined if and only if the double point scheme D(f) is a reduced curve. If n ≥ 3, we have that μ(D ²(f)) = 2μ(D ²(f)/S ₂)+C(f)?1, where D ²(f) is the lifting of the double point curve in ${(\mathbb{C}^n\times \mathbb{C}^n,0)}$ , μ(X) denotes the Milnor number of X and C(f) is the number of cross-caps that appear in a stable deformation of f. Moreover, we consider an unfolding F(t, x) = (t, f _t (x)) of f and show that if F is μ-constant, then it is excellent in the sense of Gaffney. Finally, we find a minimal set of invariants whose constancy in the family f _t is equivalent to the Whitney equisingularity of F. We also give an example of an unfolding which is topologically trivial, but it is not Whitney equisingular.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

On conjugacy of some systems of functions

Summary. We investigate the bounded solutions j:[0,1]? X \varphi:[0,1]\to X of the system of functional equations¶¶j(f_k(x))=F_k(j(x)),    k=0,?,n-1,x ? [0,1] \varphi(f_k(x))=F_k(\varphi(x)),\;\;k=0,\ldots,n-1,x\in[0,1] ,(*)¶where X is a complete metric space, f₀,?,f_n-1:[0,1]?[0,1] f_0,\ldots,f_{n-1}:[0,1]\to[0,1] and F₀,...,F_n-1:X? X F_0,...,F_{n-1}:X\to X are continuous functions fulfilling the boundary conditions f₀(0) = 0, f_n-1(1) = 1, f_k+1(0) = f_k(1), F₀(a) = a,F_n-1(b) = b,F_k+1(a) = F_k(b), k = 0,?,n-2 f_{0}(0) = 0, f_{n-1}(1) = 1, f_{k+1}(0) = f_{k}(1), F_{0}(a) = a,F_{n-1}(b) = b,F_{k+1}(a) = F_{k}(b),\,k = 0,\ldots,n-2 , for some a,b ? X a,b\in X . We give assumptions on the functions f_k and F_k which imply the existence, uniqueness and continuity of bounded solutions of the system (*). In the case X = \Bbb C X= \Bbb C we consider some particular systems (*) of which the solutions determine some peculiar curves generating some fractals. If X is a closed interval we give a collection of conditions which imply respectively the existence of homeomorphic solutions, singular solutions and a.e. nondifferentiable solutions of (*).     

Finite Element Matrix Sequences: the Case of Rectangular Domains

In the present paper, we consider a preconditioning strategy for Finite Element (FE) matrix sequences {A _n (a)} _n discretizing the elliptic problem $$\left\{ \begin{gathered} A_a u \equiv ( - )^k \nabla ^k [a(x,y)\nabla ^k u(x,y)] = f(x,y),{ }(x,y) \in \Omega = (0,1)^2 , \hfill \\ \left. {\left( {\frac{{\partial ^s }}{{\partial v^s }}u(x,y)} \right)} \right|_{\partial \Omega } \equiv 0,{ }s = 0,...,k - 1,{ }^{^{^{^{^{^{(1)} } } } } } \hfill \\ \end{gathered} \right.$$ with a(x,y) being a uniformly positive function and ν denoting the unit outward normal direction. More precisely, in connection with preconditioned conjugate gradient (PCG) like methods, we define the preconditioning sequence: {P _n (a)} _n , P _n (a):= $$\widetilde D$$ _n ^1/2(a)A _n (1) $$\widetilde D$$ _n ^1/2(a), where $$\widetilde D$$ _n (a) is the suitable scaled main diagonal of A _n (a). In fact, under the mild assumption of Lebesgue integrability of a(x), the weak clustering at the unity of the corresponding preconditioned sequence is proved. Moreover, if a(x,y) is regular enough and if a uniform triangulation is considered, then the preconditioned sequence shows a strong clustering at the unity so that the sequence {P _n (a)} _n turns out to be a superlinear preconditioning sequence for {A _n (a)} _n . The computational interest is due to the fact that the computation with A _n (a) is reduced to computations involving diagonals and two-level Toeplitz structures {A _n (1)} _n with banded pattern. Some numerical experimentations confirm the efficiency of the discussed proposal.     

Searching for a Best Least Absolute Deviations Solution of an Overdetermined System of Linear Equations Motivated by Searching for a Best Least Absolute Deviations Hyperplane on the Basis of Given Data

We consider the problem of searching for a best LAD-solution of an overdetermined system of linear equations Xa=z, X∈?^m×n, m≥n, \(\mathbf{a}\in \mathbb{R}^{n}, \mathbf {z}\in\mathbb{R}^{m}\). This problem is equivalent to the problem of determining a best LAD-hyperplane x?a ^T x, x∈? ⁿ on the basis of given data \((\mathbf{x}_{i},z_{i}), \mathbf{x}_{i}= (x_{1}^{(i)},\ldots,x_{n}^{(i)})^{T}\in \mathbb{R}^{n}, z_{i}\in\mathbb{R}, i=1,\ldots,m\), whereby the minimizing functional is of the form

$F(\mathbf{a})=\|\mathbf{z}-\mathbf{Xa}\|_1=\sum_{i=1}^m|z_i-\mathbf {a}^T\mathbf{x}_i|.$

An iterative procedure is constructed as a sequence of weighted median problems, which gives the solution in finitely many steps. A criterion of optimality follows from the fact that the minimizing functional F is convex, and therefore the point a ^?∈? ⁿ is the point of a global minimum of the functional F if and only if 0∈?F(a ^?).

Motivation for the construction of the algorithm was found in a geometrically visible algorithm for determining a best LAD-plane (x,y)?αx+βy, passing through the origin of the coordinate system, on the basis of the data (x _i ,y _i ,z _i ),i=1,…,m.