The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization

The BFGS method is the most effective of the quasi-Newton methods for solving unconstrained optimization problems. Wei, Li, and Qi [16] have proposed some modified BFGS methods based on the new quasi-Newton equation B _k+1 s _k = y* _k , where y* _k is the sum of y _k and A _k s _k, and A _k is some matrix. The average performance of Algorithm 4.3 in [16] is better than that of the BFGS method, but its superlinear convergence is still open. This article proves the superlinear convergence of Algorithm 4.3 under some suitable conditions.     

Global convergence of a modified BFGS-type method for unconstrained non-convex minimization

To the unconstrained programme of non-convex function, this article give a modified BFGS algorithm associated with the general line search model. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equationB _k +1s _k =y _k ^* ,, wherey _k ^* is the sum ofy _k andA _k s _k , andA _k is some matrix. The global convergence properties of the algorithm associating with the general form of line search is proved.     

Certain sufficient conditions of uniformity for systems of functions of many-valued logic

For any finite system A of functions of the k-valued logic taking values in the set E _s = {0,1,…, s ? 1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set E _s contains a near-unanimity function, it is proved that there exist constants c and d such that for an arbitrary function f ∈ [A] the depth D _A (f) and the complexity L _A (f) of f in the class of formulas over A satisfy the relation D _A (f) ≤ clog₂ L _A (f) + d.     

Estimates related to sumfree subsets of sets of integers

A subsetA of the positive integers ?₊ is called sumfree provided (A+A)∩A=ø. It is shown that any finite subsetB of ?₊ contains a sumfree subsetA such that |A|≥1/3(|B|+2), which is a slight improvement of earlier results of P. Erdös [Erd] and N. Alon-D. Kleitman [A-K]. The method used is harmonic analysis, refining the original approach of Erdös. In general, defines _k (B) as the maximum size of ak-sumfree subsetA ofB, i.e. (A) _k = $\underbrace {A + ... + A}_{k times}$ % MathType!End!2!1! is disjoint fromA. Elaborating the techniques permits one to prove that, for instance, $s_3 \left( B \right) > \frac{{\left| B \right|}}{4} + c\frac{{\log \left| B \right|}}{{\log \log \left| B \right|}}$ % MathType!End!2!1!as an improvement of the estimate $s_k \left( B \right) > \frac{{\left| B \right|}}{4}$ % MathType!End!2!1! resulting from Erdös’ argument. It is also shown that in an inequalitys _k (B)>δ _k |B|, valid for any finite subsetB of ?₊, necessarilyδ _k → 0 fork → ∞ (which seemed to be an unclear issue). The most interesting part of the paper are the methods we believe and the resulting harmonic analysis questions. They may be worthwhile to pursue.     

Polar cographs

A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite graph and B a disjoint union of at most k cliques. Recognizing a polar graph is known to be NP-complete. Here we consider the class of polar graphs which are also cographs. We provide polynomial time algorithms and forbidden subgraphs characterizations for problems related to polar cographs.     

A modified BFGS method and its superlinear convergence in nonconvex minimization with general line search rule

In this paper, a modification of the BFGS algorithm for unconstrained nonconvex optimization is proposed. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equation B _k+1 s _k =y _k ^* , where y _k ^* is the sum of y _k and t _k ‖g(x _k )‖s _k . The global convergence property of the algorithm associated with the general line search rule is prove.     

On the maximum size of a k-zero-free set in an abelian group

A subset A of elements in an abelian group G is called k-zero-free if the equation x ₁ + x ₂ + ... + x _k = 0 has no solution in A. A k-zero-free set A in G is called maximal if A ∪ {x} is k-zero-free for no x ∈ G\A. Some bounds for the maximum size of a k-zero free set are obtained. In particular, we determine the maximum speed of a k-zero-free arithmetic progression in the cyclic group Z _n and find the upper and lower bounds for the maximum size of a k-zero-free set in an abelian group G. We describe the structure of a maximal k-zero-free set A in the cyclic group Z _n provided that gcd(n, k) = 1 and k|A| ≥ n + 1.     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Roundoff-error analysis of a new class of conjugate-gradient algorithms

We perform the rounding-error analysis of the conjugate-gradient algorithms for the solution of a large system of linear equations Ax=b where Ais an hermitian and positive definite matrix. We propose a new class of conjugate-gradient algorithms and prove that in the spectral norm the relative error of the computed sequence {x_k} (in floating-point arithmetic) depends at worst on ζк^{$\text{3}\text{2}$}, where ζ is the relative computer precision and к is the condition number of A. We show that the residual vectors r_k=Ax_k-b are at worst of order ζк?vA?v ?vx_k?v. We p oint out that with iterative refinement these algorithms are numerically stable. If ζк ² is at most of order unity, then they are also well behaved.     

A sufficient condition for a graph to be weakly k-linked

For a pair (s, t) of vertices of a graph G, let λ_G(s, t) denote the maximal number of edge-disjoint paths between s and t. Let (s₁, t₁), (s₂, t₂), (s₃, t₃) be pairs of vertices of G and k > 2. It is shown that if λ_G(s_i, t_i) ≥ 2k + 1 for each i = 1, 2, 3, then there exist 2k + 1 edge-disjoint paths such that one joins s₁ and t₁, another joins s₂ and t₂ and the others join s₃ and t₃. As a corollary, every (2k + 1)-edge-connected graph is weakly (k + 2)-linked for k ≥ 2, where a graph is weakly k-linked if for any k vertex pairs (s_i, t_i), 1 ≤ i ≤ k, there exist k edge-disjoint paths P₁, P₂,…, P_k such that P_i joins s_i and t_i for i = 1, 2,…, k.     

On the stability properties of perturbed linear nonstationary systems

Several results are presented that relate the stability properties of a perturbed linear nonstationary system ?(t) = (A(t) + B(t)) x(t) to those of an unperturbed linear system ?(t) = A(t) x(t). Similarly, the stability properties of the discrete system x_{k + 1} = (A_k + B_k) x_k are related to those of x_{k + 1} = A_kx_k.     

Formulas for sums of powers of integers by functional equations

This paper presents a direct and simple approach to obtaining the formulas forS _k(n)= 1 ^k + 2 ^k + ... +n ^k wheren andk are nonnegative integers. A functional equation is written based on the functional properties ofS _k (n) and several methods of solution are presented. These lead to several recurrence relations for the functions and a simple one-step differential-recurrence relation from which the polynomials can easily be computed successively. Arbitrary constants which arise are (almost) the Bernoulli numbers when evaluated and identities for these modified Bernoulli numbers are obtained. The functional equation for the formulas leads to another functional equation for the generating function for these formulas and this is used to obtain the generating functions for theS _k 's and for the modified Bernoulli numbers. This leads to an explicit representation, not a recurrence relation, for the modified Bernoulli numbers which then yields an explicit formula for eachS _k not depending on the earlier ones. This functional equation approach has been and can be applied to more general types of arithmetic sequences and many other types of combinatorial functions, sequences, and problems.     

Graph partition into K 3s and K 4s

Let s and k be two integers with 0≤s≤k and let G be a simple graph of order n≥3s+4(k?s)+3. In this paper we prove that if σ ₂(G)≥3(n?s)/2+k?2, then G ? sK ₃+(k?s)K ₄. We also show that the degree condition is sharp in some sense.     

On the equivalence of the Euler-Pommier operators in spaces of analytic functions

In the space A (θ) of all one-valued functions f(z) analytic in an arbitrary region G ? ? (0 ∈ G) with the topology of compact convergence, we establish necessary and sufficient conditions for the equivalence of the operators L ₁=α _n z ⁿ Δ ⁿ + ... + α₁ zΔ+α₀ E and L ₂= z ⁿ a _n (z)Δ ⁿ + ... + za ₁(z)Δ+a ₀(z)E, where δ: (Δ?)(z)=(f(z)-?(0))/z is the Pommier operator in A(G), n ∈ ?, α _n ∈ ?, a _k (z) ∈ A(G), 0≤k≤n, and the following condition is satisfied: Σ _j=s ^n?1 α _j+1 ∈ 0, s=0,1,...,n?1. We also prove that the operators z ^s+1Δ+β(z)E, β(z) ∈ A _R , s ∈ ?, and z ^s+1 are equivalent in the spaces A _R, 0?R?-∞, if and only if β(z) = 0.     

On the Vinogradov additive problem

Let us state the main result of the paper. Suppose that the collection N ₁, ..., N _n is admissible. Then, in the representation $$ \left\{ \begin{gathered} p_1 + p_2 + \cdots + p_k = N_1 , \hfill \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \hfill \\ p_1^n + p_2^n + \cdots + p_k^n = N_n , \hfill \\ \end{gathered} \right. $$ where the unknowns p ₁, p ₂, ..., p _k take prime values under the condition p _s > n+ 1, s = 1, ..., k, the number k is of the form $$ k = k_0 + b\left( n \right)s, $$ where s is a nonnegative integer. Further, if k ₀ ≥ a, then, in the representation for k, we can set s = 0, but if k ₀ ≤ a ? 1, then, for a given k ₀ there exist admissible collections (N ₁, ..., N _n ) that cannot be expressed as k ₀ summands of the required form, but can be expressed as k ₀ + b(n) summands.     

Adams谱序列上的非平凡乘积b_0k_0δ_(s+4)

主要用May谱序列证明了非平凡的乘积b_0k_0δ_(s+4)∈Ext_A~(s+8,t)(Z_p,Z_p),其中p是大于等于7的素数,0≤sp-4,q=2(p-1),t=(s+4)p~3q+(s+3)p~2q+(s+5)pq+(s+2)q+s.     

An accelerated subspace minimization three-term conjugate gradient algorithm for unconstrained optimization

A three-term conjugate gradient algorithm for large-scale unconstrained optimization using subspace minimizing technique is presented. In this algorithm the search directions are computed by minimizing the quadratic approximation of the objective function in a subspace spanned by the vectors: ?g _k+1, s _k and y _k . The search direction is considered as: d _k+1 = ?g _k+1 + a _k s _k + b _k y _k , where the scalars a _k and b _k are determined by minimization the affine quadratic approximate of the objective function. The step-lengths are determined by the Wolfe line search conditions. We prove that the search directions are descent and satisfy the Dai-Liao conjugacy condition. The suggested algorithm is of three-term conjugate gradient type, for which both the descent and the conjugacy conditions are guaranteed. It is shown that, for uniformly convex functions, the directions generated by the algorithm are bounded above, i.e. the algorithm is convergent. The numerical experiments, for a set of 750 unconstrained optimization test problems, show that this new algorithm substantially outperforms the known Hestenes and Stiefel, Dai and Liao, Dai and Yuan and Polak, Ribiére and Poliak conjugate gradient algorithms, as well as the limited memory quasi-Newton method L-BFGS and the discrete truncated-Newton method TN.     

On a problem of Sierpiński,Ⅱ

For any integer s≥ 2, let μsbe the least integer so that every integer l μs is the sum of exactly s integers which are pairwise relatively prime. In 1964, Sierpi′nski asked for the determination of μs. Let pibe the i-th prime and let μs= p2 + p3 + + ps+1+ cs. Recently, the authors solved this problem. In particular,we have(1) cs=-2 if and only if s = 2;(2) the set of integers s with cs= 1100 has asymptotic density one;(3) cs∈ A for all s ≥ 3, where A is an explicit set with A ■[2, 1100] and |A| = 125. In this paper, we prove that,(1) for every a ∈ A, there exists an index s with cs= a;(2) under Dickson's conjecture, for every a ∈ A,there are infinitely many s with cs= a. We also point out that recent progress on small gaps between primes can be applied to this problem.     

Asymptotics for the logarithm of the number of (k, l)-sum-free sets in groups of prime order

The subset A of a group G is (k, l)-sum-free if x ₁ + ?? + x _k ? x _{k + 1} ? ?? ? x _k+l?1 does not belong to the set A for any x ₁, ??, x _k+l?1 ?? A. Asymptotics for the logarithm of the number of sets (k, l)-sum-free in groups of prime order is obtained.