On a Global Complexity Bound of the Levenberg-Marquardt Method

In this paper, we investigate a global complexity bound of the Levenberg-Marquardt method (LMM) for the nonlinear least squares problem. The global complexity bound for an iterative method solving unconstrained minimization of φ is an upper bound to the number of iterations required to get an approximate solution, such that ‖∇φ(x)‖≤ε. We show that the global complexity bound of the LMM is O(ε ⁻²).     

Finding stabbing lines in 3-space

A line intersecting all polyhedra in a setℬ is called a “stabber” for the setℬ. This paper addresses some combinatorial and algorithmic questions about the setℒ(ℬ) of all lines stabbingℬ. We prove that the combinatorial complexity ofℒ(ℬ) has an upper bound, wheren is the total number of facets inℬ, andc is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one. The research of M. Pellegrini was partially supported by Eni and Enidata within the AXL project, and by NSF Grant CCR-8901484. A preliminary version appeared in theProceedings of the Second ACM-SIAM Symposium on Discrete Algorithms, pp. 24–31.     

The Loewy Length of the Descent Algebra of Type <Emphasis Type="Italic">D</Emphasis>

In this article the Loewy length of the descent algebra of D _2m + 1 is shown to be m + 2, for m ≥ 2, by providing an upper bound that agrees with the lower bound in Bonnafé and Pfeiffer (2006). The bound is obtained by showing that the length of the longest path in the quiver of the descent algebra of D _2m + 1 is at most m + 1. To achieve this bound, the geometric approach to the descent algebra is used, in which the descent algebra of a finite Coxeter group W is identified with an algebra associated to the reflection arrangement of W.     

Non-existence of bipartite graphs of diameter at least 4 and defect 2

The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Δ and diameter D. Bipartite graphs of maximum degree Δ, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Δ such that Δ−1 is a prime power.     

Projection–difference method for controlled Fourier filtering

A projection–difference method is developed for approximating controlled Fourier filtering for quasilinear parabolic functional-differential equations. The method relies on a projection–difference scheme (PDS) for the approximation of the differential problem and derives a O(τ^1/2 + h) bound on the rate of convergence of PDS in the weighted energy norm without prior assumptions of additional smoothness of the generalized solutions. The PDS leads to a natural approximation of the objective functional in the optimal Fourier filtering problem. A bound of the same order is obtained for the rate of convergence in the functional of the problems approximating the Fourier filter control problem.     

Exact Bounds on Cross-Intersecting Families

 Let ?, ℬ be cross-intersecting families, where ? is a k-uniform, ℬ is an l-uniform family on a finite underlying set. A tight bound is given on |?|+|ℬ|, if c≤|?|≤d holds for some natural numbers c,d. Received: February 8, 1999 Final version received: May 17, 2000     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Extension of Turán's Theorem to the 2-Stability Number

 Given a graph G with n vertices and stability number α(G), Turán's Theorem gives a lower bound on the number of edges in G. Furthermore, Turán has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α₂(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α₂(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's Theorem to the q-stability number, for q>2. Received: July 21, 1999 Final version received: August 22, 2000 Present address: GERAD, 3000 ch. de la Cote-Ste-Catherine, Montreal, Quebec H3T 2A7, Canada. e-mail: Alain.Hertz@gerad.ca     

Convergence Properties of the Regularized Newton Method for the Unconstrained Nonconvex Optimization

The regularized Newton method (RNM) is one of the efficient solution methods for the unconstrained convex optimization. It is well-known that the RNM has good convergence properties as compared to the steepest descent method and the pure Newton’s method. For example, Li, Fukushima, Qi and Yamashita showed that the RNM has a quadratic rate of convergence under the local error bound condition. Recently, Polyak showed that the global complexity bound of the RNM, which is the first iteration k such that ‖∇ f(x _k )‖≤ε, is O(ε ⁻⁴), where f is the objective function and ε is a given positive constant. In this paper, we consider a RNM extended to the unconstrained “nonconvex” optimization. We show that the extended RNM (E-RNM) has the following properties. (a) The E-RNM has a global convergence property under appropriate conditions. (b) The global complexity bound of the E-RNM is O(ε ⁻²) if ∇ ² f is Lipschitz continuous on a certain compact set. (c) The E-RNM has a superlinear rate of convergence under the local error bound condition.     

On Diophantine approximations to log <Emphasis Type="Italic">x</Emphasis>

A lower bound for Diophantine approximations to linear combination of the numbers log(5/3) and (1/√15) arctan(1/√15) is obtained.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

Bichromatic and Equichromatic Lines in ℂ2 and ℝ2

Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ². For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic lines passing through at most four, five, or six points.     

Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

Counting Overlattices in Automorphism Groups of Trees

We give an upper bound for the number u _Γ(n) of “overlattices” in the automorphism group of a tree, containing a fixed lattice Γ with index n. For an example of Γ in the automorphism group of a 2p-regular tree whose quotient is a loop, we obtain a lower bound of the asymptotic behavior as well.     

Approximations for node-weighted Steiner tree in unit disk graphs

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound 4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞.     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

The size of epimorphic extensions

A sharp bound is given for the size of epimorphic extensions in categories of models defined over elementary logic andL _κκ where κ is strongly compact. For fragments ofL _ω1ω an example is given of a category which has a countable model with epimorphic extensions whose cardinalities approach and include the first measurable cardinal. If no measurable cardinal exists then this category has a countable model with epimorphic extensions of unbounded cardinality. This work was supported in part by the National Research Council of Canada under grant numbers A8599, A5603 and A8190. Presented by J. D. Monk.     

Degree complexity for a modified pigeonhole principle

 We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt [7], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6]. Received: 29 March 2001 / Published online: 2 September 2002 RID="⋆" ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999 RID="†" ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03. RID="††" ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study supported by a NSF grant n. 9987845     

Robust <Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> Output Dynamic Observer-Based Control Design of Uncertain Neutral Systems

In this paper, the robust H _∞ control problem of output dynamic observer-based control for a class of uncertain neutral systems is considered. The linear matrix inequality optimization approach is used to design the new H _∞ output dynamic controls. Three classes of H _∞ observer-based controls are proposed. The minimal H _∞-norm bound and the maximal perturbed bound are given. Based on the result of this paper, the constraint of matrix equality is not necessary for designing the H _∞ observer-based controls. A numerical example is given to stress the usefulness of the proposed results. Communicated by C. T. Leondes The research reported here was supported by the National Science Council of Taiwan, ROC under Grant NSC 94-2213-E-507-002.