An O(n 2) Active Set Algorithm for Solving Two Related Box Constrained Parametric Quadratic Programs

Recently, O(n ²) active set methods have been presented for minimizing the parametric quadratic functions (1/2)x Dx–a x+| x–c| and (1/2)x Dx–a x+(/2)( x–c)², respectively, subject to lxb, for all nonnegative values of the parameter . Here, D is a positive diagonal n×n matrix, and a are arbitrary n-vectors, c is an arbitrary scalar; l and b are arbitrary n-vectors such that lb. In this paper, we show that each one of these algorithms may be used to simultaneously solve both parametric programs withno additional computational cost.     

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

On the restricted arc-connectivity of s-geodetic digraphs

For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′（D） is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V（D1） contains an arc. Let S be a subset of vertices of D. We denote by w＋（S） the set of arcs uv with u ∈ S and v S, and by w-（S） the set of arcs uv with u S and v ∈ S. A digraph D = （V, A） is said to be λ′-optimal if λ′（D） =ξ′（D）, where ξ′（D） is the minimum arc-degree of D defined as ξ（D） = min {ξ′（xy） ： xy ∈ A}, and ξ′（xy） = min（｜ω＋（{x,y}）｜, ｜w-（{x,y}）｜, ｜w＋（x） ∪ w- （y） ｜, ｜w- （x） ∪ω＋ （y）｜}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh（D） of a s-geodetic digraph is λ′-optimal for certain iteration h.     

On simple modules of Hecke algebras of type Dn

This is a continuation of our previous work. We classify all the simple ℋ_q(D _n )-modules via an automorphismh defined on the set { λ | D^λ ≠ 0}. Whenf _n(q) ≠ 0, this yields a classification of all the simple ℋ ^q (D _n)- modules for arbitrary n. In general ( i. e., q arbitrary), if λ⁽¹⁾ = λ⁽²⁾,wegivea necessary and sufficient condition ( in terms of some polynomials ) to ensure that the irreducible ℋ_q,1(B _n )- module D^λ remains irreducible on restriction to ℋ_q(D _n ).     

Quadratic programming and combinatorial minimum weight product problems

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a ^T x + γ)(b ^T x + δ) under linear constraints A x ≤ d. Examples of such problems are combinatorial minimum weight product problems such as the following: given a graph G = (V,E) and two edge weights find an s − t path P that minimizes a(P)b(P), the product of its edge weights relative to a and b.      

Set systems with three intersections

LetX be a finite set ofn elements and ℱ a family of 4a+5-element subsets,a≧6. Suppose that all the pairwise intersections of members of ℱ have cardinality 0,a or 2a+1. We show thatc ₁ n ^4/3<max |F|<c ₂ n ^4/3 for some positivec _i’s. This answers a question of P. Frankl.     

The Łojasiewicz exponent of an analytic function at an isolated zero

Let f be a real analytic function defined in a neighborhood of 0 ? \Bbb Rⁿ 0 \in {\Bbb R}^n such that f^-1(0)={0} f^{-1}(0)=\{0\} . We describe the smallest possible exponents !, #, / for which we have the following estimates: |f(x)| 3 c|x|^a |f(x)|\geq c|x|^{\alpha} , |grad f(x)| 3 c|x|^b |{\rm grad}\,f(x)|\geq c|x|^{\beta} , |grad f(x)| 3 c|f(x)|^q |{\rm grad}\,f(x)|\geq c|f(x)|^{\theta} for x near zero with c > 0 c > 0 . We prove that a = b+1 \alpha=\beta+1, q = b/a\theta=\beta/\alpha . Moreover b = N+a/b \beta=N+a/b where $ 0 h a < b h N^{n-1} $ 0 h a < b h N^{n-1} . If f is a polynomial then |f(x)| 3 c|x|^(degf-1)n+1 |f(x)|\geq c|x|^{(\deg f-1)^n+1} in a small neighborhood of zero.     

Asymptotic analysis of the exponential penalty trajectory in linear programming

We consider the linear program min{cx: Axb} and the associated exponential penalty functionf _r(x) = cx + rexp[(A _ix – b_i)/r]. Forr close to 0, the unconstrained minimizerx(r) off _r admits an asymptotic expansion of the formx(r) = x ^* + rd^* + (r) wherex ^* is a particular optimal solution of the linear program and the error term(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to : the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.Corresponding author. Both authors partially supported by FONDECYT.     

Criteria of exponential decay for eigenfunctions of some classes of integral operators

We study sufficient conditions for exponential decay at infinity for eigenfunctions of a class of integral equations in unbounded domains in ℝ ⁿ . We consider integral operators K whose kernels have the form

Magnetovolume and chemical bonding effects of Ni atom in γ’-(Fe1- x Ni x )4N compounds

By X-ray diffraction and high pressure Mossbauer spectroscopy, the structure and the hyperfine parameters of Ni substituted γ’-Fe₄N were investigated. The results of X-ray diffraction indicate that single phase γ’-(Fe₁-_xNi_x)₄N compounds can be prepared in the composition range of 0⩽x⩽0.6, and with the increase of Ni content the lattice parameter is fit for the relationshipa ₀(x)=3.790 5-0.021 57x-0.031 67x ². By high pressure Mossbauer spectra, effects of magnetovolume and chemical bonding of Ni atom on hyperfine magnetic field and isomer shift of iron were distinguished for the first time, and their composition dependences for different lattice sites were studied simultaneously. It is found that the magnetovolume and chemical bonding have different influences on the properties of γ’-(Fe₁-_xNi_x)₄N, and the latter one plays a key role in the property changes of γ’-(Fe₁-_xNi_x)₄N. Project supported by the National Natural Science Foundation of China, the Natural Science Fund of Gansu Province and the Postdoctoral Fund of China.     

Equazioni ellittiche non variazionali a coefficienti continui

Riassunto Si considera un'equazione ellittica non variazionale a_aD^au=f a coefficienti continui in un apertogW di ℝⁿ e si dimostrano certe proprietà locali delle soluzioni forti dell'equazione medesima nell'ipotesi che f appartenga allo spazio di Morrey L ^2,λ(Ω) o allo spazio di John-Nirenberg ℰ(Ω). Analoga indagine è svolta supponendoΩ=ℝ ₊ ⁿ e supponendo che u verifichi sull'iperpiano x_n=0 condizioni di Dirichlet omogenee. Ricerca svolta nell'ambito dei Contratti di Ricerca del Comitato per la Matematica del C.N.R. Entrata in Redazione il 17 febbraio 1970.     

Proof of some conjectures on the mean-value of Titchmarsh series — III

With some applications in view, the following problem is solved in some special case which is not too special. LetF(s) =Σ _n ^∞ =1a_n λ _n ^−s be a generalized Dirichlet series with 1 =λ ₁ <λ ₂ < …,λ _n≤Dn, andλ _n+1 -λ _n ≥D ^{− 1} λ _n+1 ^{− a} where α>0 andD(≥ 1) are constants. Then subject to analytic continuation and some growth conditions, a lower bound is obtained for . These results will be applied in other papers to appear later.     

On a sum involving Fourier coefficients of cusp forms

We improve the existing upper bound for the quantity |∑ _n⩽x a(n ²)|, where a(n ²) is the n ²th Hecke eigenvalue of a normalized holomorphic cusp form (Hecke eigenform) of the full modular group SL(2, ℤ), whenever the weight of the original holomorphic cusp form (Hecke eigenform) lies in a certain range. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 4, pp. 565–583, October–December, 2006.     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Characterization of polyanalytic functions by meromorphic extensions from chains of circles

Let C _t = {z ∈ ℂ: |z − c(t)| = r(t), t ∈ (0, 1)} be a C ¹-family of circles in the plane such that lim _t→0+ C _t = {a}, lim _t→1− C _t = {b}, a ≠ b, and |c′(t)|² + |r′(t)|² ≠ 0. The discriminant set S of the family is defined as the closure of the set {c(t) + r(t)w(t), t ∈ [0, 1]}, where w = w(t) is the root of the quadratic equation ̅c′(t)w ² + 2r′(t)w + c′(t) = 0 with |w| < 1, if such a root exists.     

Small prime solutions of a pair of linear equations in five prime variables

Assume an additional congruent condition on the coefficients. We prove that the pair 5 of linear equations ∑j=1^5 αλjpj = bλ （λ= 1, 2） has solutions in primes pj satisfying pj 〈〈 （｜b1｜＋｜b2｜＋1） maxλ,j ｜αλj｜^2318＋ε. This improves the exponent 79680 without assuming the additional condition of the second author＇s.     

Annihilating power values of co-commutators with generalized derivations

Let R be a prime ring with its Utumi ring of quotient U, H and G be two generalized derivations of R and L a noncentral Lie ideal of R. Suppose that there exists 0 ≠ a ∈ R such that a(H(u)u − uG(u)) ⁿ  = 0 for all u ∈ L, where n ≥ 1 is a fixed integer. Then there exist b′,c′ ∈ U such that H(x) = b′x + xc′, G(x) = c′x for all x ∈ R with ab′ = 0, unless R satisfies s ₄, the standard identity in four variables.     

Systems of equations driven by stable processes

Let Z^j_t, j = 1, . . . , d, be independent one-dimensional symmetric stable processes of index α ∈ (0,2). We consider the system of stochastic differential equations where the matrix A(x)=(A_ij(x))1≤ i, j ≤ d is continuous and bounded in x and nondegenerate for each x. We prove existence and uniqueness of a weak solution to this system. The approach of this paper uses the martingale problem method. For this, we establish some estimates for pseudodifferential operators with singular state-dependent symbols. Let λ₂ > λ₁ > 0. We show that for any two vectors a, b∈ ℝ_d with |a|, |b| ∈ (λ₁, λ₂) and p sufficiently large, the L^p-norm of the operator whose Fourier multiplier is (|u · a|^α - |u · b|^α) / ∑_j=1^d |u_i|^α is bounded by a constant multiple of |a−b|^θ for some θ > 0, where u=(u₁ , . . . , u_d) ∈ ℝ^d. We deduce from this the L^p-boundedness of pseudodifferential operators with symbols of the form ψ(x,u)=|u · a(x)|^α / ∑_j=1^d |u_i|^α, where u=(u₁,...,u_d) and a is a continuous function on ℝ^d with |a(x)|∈ (λ₁, λ₂) for all x∈ ℝ^d. Research partially supported by NSF grant DMS-0244737. Research partially supported by NSF grant DMS-0303310.     

Generalized uncertainty inequalities

The Heisenberg–Pauli–Weyl (HPW) uncertainty inequality on \mathbbRⁿ{\mathbb{R}^n} says that

Convergence of mock Fourier series

For certain Cantor measures μ on ℝⁿ, it was shown by Jorgensen and Pedersen that there exists an orthonormal basis of exponentialse ^2πiγ·x for λεΛ. a discrete subset of ℝⁿ called aspectrum for μ. For anyL ¹ functionf, we define coefficientsc _γ(f)=∝f(y)e ^−2πiγiy dμ(y) and form the Mock Fourier series ∑_λ∈Λ^cλ(f)e ^2πiλ·x . There is a natural sequence of finite subsets Λ_n increasing to Λ asn→∞, and we define the partial sums of the Mock Fourier series by We prove, under mild technical assumptions on μ and Λ, thats _n(f) converges uniformly tof for any continuous functionf and obtain the rate of convergence in terms of the modulus of continuity off. We also show, under somewhat stronger hypotheses, almost everywhere convergence forfεL ¹. Research supported in part by the National Science Foundation, Grant DMS-0140194.