A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

A Generalized Cubic Functional Equation

In this paper, we determine the general solution of the functional equation f1 （2x ＋ y） ＋ f2（2x - y） = f3（x ＋ y） ＋ f4（x - y） ＋ f5（x） without assuming any regularity condition on the unknown functions f1,f2,f3, f4, f5 ： R→R. The general solution of this equation is obtained by finding the general solution of the functional equations f（2x ＋ y） ＋ f（2x - y） = g（x ＋ y） ＋ g（x - y） ＋ h（x） and f（2x ＋ y） - f（2x - y） = g（x ＋ y） - g（x - y）. The method used for solving these functional equations is elementary but exploits an important result due to Hosszfi. The solution of this functional equation can also be determined in certain type of groups using two important results due to Szekelyhidi.     

On an Asymptotic Behavior of Exponential Functional Equation

The stability problems of the exponential （functional） equation on a restricted domain will be investigated, and the results will be applied to the study of an asymptotic property of that equation. More precisely, the following asymptotic property is proved： Let X be a real （or complex） normed space. A mapping f ： X → C is exponential if and only if f（x ＋ y） - f（x）f（y） → 0 as ｜｜x｜｜ ＋ ｜｜y｜｜ → ∞ under some suitable conditions.     

A continuation theorem with applications to periodically forced Liénard equations in the presence of a separatrix

In this paper we prove a result on the existence of periodic motions for the periodically forced Liénard differential equation x ^″+f(x)x ^′+g(x)=e(t) in a situation where the phase portrait of the associated autonomous equation is similar to that of a centre limited by an unbounded separatrix. The existence result, which is based on a degree theoretic continuation theorem, enables us to treat some interesting cases not previously considered in the literature. Received: April 27, 2000 Published online: December 19, 2001     

Homomorphisms between JC＊-algebras and Lie C＊-algebras

It is shown that every almost ＊-homomorphism h ： A→B of a unital JC＊-algebra A to a unital JC＊-algebra B is a ＊-homomorphism when h（rx） = rh（x） （r 〉 1） for all x∈A, and that every almost linear mapping h ： A→B is a ＊-homomorphism when h（2^nu o y） - h（2^nu） o h（y）, h（3^nu o y） - h（3^nu） o h（y） or h（q^nu o y） = h（q^nu） o h（y） for all unitaries u ∈A, all y ∈A, and n = 0, 1,.... Here the numbers 2, 3, q depend on the functional equations given in the almost linear mappings. We prove that every almost ＊-homomorphism h ： A→B of a unital Lie C＊-algebra A to a unital Lie C＊-algebra B is a ＊-homomorphism when h（rx） = rh（x） （r 〉 1） for all x ∈A.     

On the Cauchy difference on normed spaces

LetX be a real linear normed space, (G, +) be a topological group, andK be a discrete normal subgroup ofG. We prove that if a continuous at a point or measurable (in the sense specified later) functionf:X →G fulfils the condition:f(x +y) -f(x) -f(y) ∈K whenever ‖x‖ = ‖y‖, then, under some additional assumptions onG,K, andX, there esists a continuous additive functionA :X →G such thatf(x) -A(x) ∈K.     

Weighted mean convergence of Hakopian interpolation on the disk

In this paper, we study weighted mean integral convergence of Hakopian interpolation on the unit disk D. We show that the inner product between Hakopian interpolation polynomial Hn(f;x,y) and a smooth function g(x,y) on D converges to that of f(x,y) and g(x,y) on D when n →∞, provided f(x,y) belongs to C(D) and all first partial derivatives of g(x,y) belong to the space LipαM(0 ＜α≤ 1). We further show that provided all second partial derivatives of g(x,y) also belong to the space LipαM and f(x,y) belongs to C1 (D), the inner product between the partial derivative of Hakopian interpolation polynomial (6)/(6)xHn(f;x,y) and g(x,y) on D converges to that between (6)/(6)xf(x,y) and g(x,y) on D when n →∞.     

A comparative study of functional equations characterising sine and cosine

A comparative study of the functional equationsf(x+y)f(x–y)=f ²(x)–f ²(y),f(y){f(x+y)+f(x–y)}=f(x)f(2y) andf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} which characterise the sine function has been carried out. The zeros of the functionf satisfying any one of the above equations play a vital role in the investigations. The relation of the equationf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} with D'Alembert's equation,f(x+y)+f(x–y)=2f(x)f(y) and the sine-cosine equationg(x–y)=g(x)g(y) +f(x)f(y) has also been investigated.     

Generalized weighted quasi-arithmetic means

Under some natural assumptions on real functions f and g defined on a real interval I, we show that a two variable function M _f,g : I ² → I defined by

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

Convex envelopes of products of convex and component-wise concave functions

In this paper, we consider functions of the form f(x,y)=f(x)g(y){\phi(x,y)=f(x)g(y)} over a box, where f(x), x ? \mathbb R{f(x), x\in {\mathbb R}} is a nonnegative monotone convex function with a power or an exponential form, and g(y), y ? \mathbb Rⁿ{g(y), y\in {\mathbb R}^n} is a component-wise concave function which changes sign over the vertices of its domain. We derive closed-form expressions for convex envelopes of various functions in this category. We demonstrate via numerical examples that the proposed envelopes are significantly tighter than popular factorable programming relaxations.     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Convexity of Products of Univariate Functions and Convexification Transformations for Geometric Programming

We investigate the characteristics that have to be possessed by a functional mapping f:ℝ↦ℝ so that it is suitable to be employed in a variable transformation of the type x→f(y) in the convexification of posynomials. We study first the bilinear product of univariate functions f ₁(y ₁), f ₂(y ₂) and, based on convexity analysis, we derive sufficient conditions for these two functions so that ℱ₂(y ₁,y ₂)=f ₁(y ₁)f ₂(y ₂) is convex for all (y ₁,y ₂) in some box domain. We then prove that these conditions suffice for the general case of products of univariate functions; that is, they are sufficient conditions for every f _i (y _i ), i=1,2,…,n, so as ℱ _n (y ₁,y ₂,…,y _n )=∏ _i=1 ⁿ f _i (y _i ) to be convex. In order to address the transformation of variables that are exponentiated to some power κ≠1, we investigate under which further conditions would the function (f) ^κ be also suitable. The results provide rigorous reasoning on why transformations that have already appeared in the literature, like the exponential or reciprocal, work properly in convexifying posynomial programs. Furthermore, a useful contribution is in devising other transformation schemes that have the potential to work better with a particular formulation. Finally, the results can be used to infer the convexity of multivariate functions that can be expressed as products of univariate factors, through conditions on these factors on an individual basis. The authors gratefully acknowledge support from the National Science Foundation.     

On the well-definedness of the order of an ordinary differential equation

It is proved that if the differential equations y ^{( n )}=f(x, y, y′, …, y ^{( n ?1 )}) and y ^{( m )}=g(x, y, y′, …, y ^{( n ?1 )}) have the same particular solutions in a suitable region where f and g are continuous real-valued functions with continuous partial derivatives (alternatively, continuous functions satisfying the classical Lipschitz condition), then n?=?m and the functions f and g are equal. This note could find classroom use in a course on differential equations as enrichment material for the unit on the existence and uniqueness theorems for solutions of initial value problems.     

Functional equations on abelian groups with involution

Summary We produce complete solution formulas of selected functional equations of the formf(x +y) ±f(x + σ (ν)) = Σ _I ² =₁ g _l (x)h _l (y),x, y∈G, where the functionsf,g ₁,h ₁ to be determined are complex valued functions on an abelian groupG and where σ:G→G is an involution ofG. The special case of σ=−I encompasses classical functional equations like d’Alembert’s, Wilson’s first generalization of it, Jensen’s equation and the quadratic equation. We solve these equations, the equation for symmetric second differences in product form and similar functional equations for a general involution σ.     

A generalized mixed type of quartic–cubic–quadratic–additive functional equations

We determine the general solution of the functional equation f(x + ky) + f(x-ky) = g(x + y) + g(x-y) + h(x) + h(y) for fixed integers with k ≠ 0; ±1 without assuming any regularity conditions for the unknown functions f, g, h, and0020[(h)\tilde] \tilde{h} . The method used for solving these functional equations is elementary but it exploits an important result due to Hosszú. The solution of this functional equation can also be obtained in groups of certain type by using two important results due to Székelyhidi.     

Weak and strong forms of β-irresolute functions

A subset A of a topological space X is said to be β-open [1] if A ⊂ Cl (Int (Cl (A))). A function f : X → Y is said to be β-irresolute [4] if for every β-open set V of Y, f ^-1(V) is β-open in X. In this paper we introduce weak and strong forms of β-irresolute functions and obtain several basic properties of such functions. This revised version was published online in August 2006 with corrections to the Cover Date.     

Interpolation problems on the spectrum of <Emphasis Type="Italic">H</Emphasis><Superscript>∞</Superscript>

We characterize those sequences (x _n ) in the spectrum of H ^∞ whose Nevanlinna–Pick interpolation problems admit thin Blaschke products as solutions. We also study under which conditions there is a Blaschke product B with prescribed zero-set distribution and solving problems of the form B(x) = f _n (x) for every x ∈ P(x _n ), where P(x _n ) is the Gleason part associated with the point x _n and where (f _n ) is an arbitrary sequence of functions in the unit ball of H ^∞. As a corollary we get a new characterization of Carleson–Newman Blaschke products in terms of bounded universal functions, a result first proved by Gallardo and Gorkin.      

Biconvex sets and optimization with biconvex functions: a survey and extensions

The problem of optimizing a biconvex function over a given (bi)convex or compact set frequently occurs in theory as well as in industrial applications, for example, in the field of multifacility location or medical image registration. Thereby, a function is called biconvex, if f(x,y) is convex in y for fixed x∈X, and f(x,y) is convex in x for fixed y∈Y. This paper presents a survey of existing results concerning the theory of biconvex sets and biconvex functions and gives some extensions. In particular, we focus on biconvex minimization problems and survey methods and algorithms for the constrained as well as for the unconstrained case. Furthermore, we state new theoretical results for the maximum of a biconvex function over biconvex sets. J. Gorski and K. Klamroth were partially supported by a grant of the German Research Foundation (DFG).