On solving a D.C. programming problem by a sequence of linear programs

We are dealing with a numerical method for solving the problem of minimizing a difference of two convex functions (a d.c. function) over a closed convex set in ⁿ . This algorithm combines a new prismatic branch and bound technique with polyhedral outer approximation in such a way that only linear programming problems have to be solved.Parts of this research were accomplished while the third author was visiting the University of Trier, Germany, as a fellow of the Alexander von Humboldt foundation.     

The design centering problem as a D.C. programming problem

The following problem is studied: Given a compact setS inR ⁿ and a Minkowski functionalp(x), find the largest positive numberr for which there existsx S such that the set of ally R ⁿ satisfyingp(y–x) r is contained inS. It is shown that whenS is the intersection of a closed convex set and several complementary convex sets (sets whose complements are open convex) this design centering problem can be reformulated as the minimization of some d.c. function (difference of two convex functions) overR ⁿ . In the case where, moreover,p(x) = (x ^T Ax)^1/2, withA being a symmetric positive definite matrix, a solution method is developed which is based on the reduction of the problem to the global minimization of a concave function over a compact convex set.     

On a problem of A. D. Sands

Summary If a finite abelian (p, q)-group whosep-Sylow subgroup is cyclic is factorized by subsets of cardinalitiesq or a power ofp, then at least one of the factors is periodic.     

On a result of C. Mueller and E. Perkins

Summary. The equation du=(au”+bu′+cu) dt+νu ^γ W(dx,dt) is considered for γ∈(0,1). It is proved that u(t,·) has compact support for all t≥0 if u(0,·) does. This result extends a result of C. Mueller and E. Perkins who considered the case a=1,b=c=0. The proof does not use the nonstandard analysis unlike the one by C. Mueller and E. Perkins. Received: 6 September 1996 / In revised form: 12 February 1997     

Necessary optimality conditions of a D.C. set-valued bilevel optimization problem

In this article, we consider a bilevel vector optimization problem where objective and constraints are set valued maps. Our approach consists of using a support function [1–3,14,15,32] together with the convex separation principle for the study of necessary optimality conditions for D.C. bilevel set-valued optimization problems. We give optimality conditions in terms of the strong subdifferential of a cone-convex set-valued mapping introduced by Baier and Jahn 6 Baier, J and Jahn, J. 1999. On subdifferentials of set-valued maps. J. Optim. Theory Appl., 100: 233–240. [Crossref], [Web of Science ®] , [Google Scholar] and the weak subdifferential of a cone-convex set-valued mapping of Sawaragi and Tanino 28 Sawaragi, Y and Tanino, T. 1980. Conjugate maps and duality in multiobjective optimization. J. Optim. Theory Appl., 31: 473–499.  [Google Scholar]. The bilevel set-valued problem is transformed into a one level set-valued optimization problem using a transformation originated by Ye and Zhu 34 Ye, JJ and Zhu, DL. 1995. Optimality conditions for bilevel programming problems. Optimization, 33: 9–27. [Taylor & Francis Online] , [Google Scholar]. An example illustrating the usefulness of our result is also given.     

On a problem of D.H. Lehmer over short intervals

Let p be an odd prime and a be an integer coprime to p. Denote by N(a,p) the number of pairs of integers b,c with bc≡a (mod p), and with b,c having different parity. The main purpose of this paper is to study the sum , and obtain a sharp asymptotic formula.     

Splitting and cone avoidance in the D.C.E. degrees

It is shown that the Cooper splitting theorem for the n-c.e. degrees is not compatible with cone avoidance: For any n > 1, there exist n-c.e. degree a, c.e. degree b such that 0 < b < a and such that for any n-c.e. degrees x,y, if x ∨ y = a, then either b ≤ x or b ≤ y. This provides a new type of elementary difference between the classes of c.e. and d.c.e. degrees, implementable at lower levels of the high/low hierarchy.     

On the generalization of the D. H. Lehmer problem

Let n ≥ 2 be a fixed positive integer, q ≥ 3 and c be two integers with （n, q） = （c, q） = 1. We denote by rn（51, 52, C; q） （δ 〈 δ1,δ2≤ 1） the number of all pairs of integers a, b satisfying ab ≡ c（mod q）, 1 〈 a ≤δ1q, 1 ≤ b≤δ2q, （a,q） = （b,q） = 1 and nt（a＋b）. The main purpose of this paper is to study the asymptotic properties of rn （δ1, δ2, c; q）, and give a sharp asymptotic formula for it.     

On Lipschitz and D.C. surfaces of finite codimension in a Banach space

Properties of Lipschitz and d.c. surfaces of finite codimension in a Banach space and properties of generated σ-ideals are studied. These σ-ideals naturally appear in the differentiation theory and in the abstract approximation theory. Using these properties, we improve an unpublished result of M. Heisler which gives an alternative proof of a result of D. Preiss on singular points of convex functions.     

Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching

We give the solution to the following question of C. D. Godsil[2]: Among the bipartite graphsG with a unique perfect matching and such that a bipartite graph obtains when the edges of the matching are contracted, characterize those having the property thatG ⁺G, whereG ⁺ is the bipartite multigraph whose adjacency matrix,B ⁺, is diagonally similar to the inverse of the adjacency matrix ofG put in lower-triangular form. The characterization is thatG must be obtainable from a bipartite graph by adding, to each vertex, a neighbor of degree one. Our approach relies on the association of a directed graph to each pair (G, M) of a bipartite graphG and a perfect matchingM ofG.     

On Covering Methods for D.C. Optimization

Covering methods constitute a broad class of algorithms for solving multivariate Global Optimization problems. In this note we show that, when the objective f is d.c. and a d.c. decomposition for f is known, the computational burden usually suffered by multivariate covering methods is significantly reduced. With this we extend to the (non-differentiable) d.c. case the covering method of Breiman and Cutler, showing that it is a particular case of the standard outer approximation approach. Our computational experience shows that this generalization yields not only more flexibility but also faster convergence than the covering method of Breiman-Cutler.     

Solution to a problem of A. D. sands

If a finite cyclic group is a direct product of its subsets such that the cardinality of one factor is a product of two primes and the others are of prime cardinalities, then at least one of the factors is a direct product of a subset and a proper subgroup of the group. This settles a 30 years old problem of A. D. Sands,.     

On a problem of A. Pleijel

In 1955, Arne Pleijel proposed the following problem which remains unsolved to this day: Given a closed plane convex curve C and a point x() at a fixed distance above the plane, as the point x() varies, characterize the point for which the conical surface with vertex x() and base C attains its minimum, and determine the limits as 0 and of this minimum point. The purpose of this paper is to solve the cases where approach its extremities and in the course of the solution, we obtain an interesting characterization of the limit points, which we shall call the Pleijel points of C. A consequence is that the inner Pleijel point provides an upper bound for the isoperimetric defect of C. We also generalize the problem to higher dimensional spaces, and obtain the corresponding characterizations of the limiting points for convex surfaces.