A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

On the stability of linear systems with an exact constraint set

This paper deals with the stability of the intersection of a given set with the solution, , of a given linear system whose coefficients can be arbitrarily perturbed. In the optimization context, the fixed constraint set X can be the solution set of the (possibly nonlinear) system formed by all the exact constraints (e.g., the sign constraints), a discrete subset of (as or { 0,1} ⁿ , as it happens in integer or Boolean programming) as well as the intersection of both kind of sets. Conditions are given for the intersection to remain nonempty (or empty) under sufficiently small perturbations of the data. Research supported by Fondecyt Grant 1020(7020)-646. Research supported by DGES and FEDER, Grant BFM2002-04114-C02-01     

Inference of a minimum size boolean function from examples by using a new efficient branch-and-bound approach

This paper deals with the problem of identifying a hidden Boolean function : 0, 1' 0, 1 from positive and negative examples. This problem is of paramount importance in many real life applications of artificial intelligence. The method proposed in this paper is based on a branch-and-bound approach. This approach is an expansion of some earlier work (Triantaphyllouet al., 1994). Computational results, comparing the new method with one based on Karmakar's interior point method, suggest that the new method is very efficient.     

Finite checkability for integer rounding properties in combinatorial programming problems

LetA be a nonnegative integral matrix with no zero columns. Theinteger round-up property holds forA if for each nonnegative integral vectorw, the solution value to the integer programming problem min{1 y: yA w, y 0, y integer} is obtained by rounding up to the nearest integer the solution value to the corresponding linear programming problem min{1 y: yA w, y 0}. Theinteger round-down property is similarly defined for a nonnegative integral matrixB with no zero rows by considering max{1 y: yB w, y 0, y integer} and its linear programming correspondent. It is shown that the integer round-up and round-down properties can be checked through a finite process. The method of proof motivates a new and elementary proof of Fulkerson's Pluperfect Graph Theorem.Research partially supported by NSF Grants ENG76-09936 and ENG78-09882.     

Sensitivity theorems in integer linear programming

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Axb}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integer programming proximity results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Axb} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that each integer programming value function is a Gomory function.Supported by a grant from the Alexander von Humboldt Stiftung.Since September 1985: Department of Operations Research, Upson Hall, Cornell University, Ithaca, NY 14853, USA.Partially supported by the Sonderforschungbereich 21 (DFG), Institut für Ökonometrie und Operations Research of the University of Bonn, FR Germany.     

Hölder Regularity for Solutions of Ultraparabolic Equations in Divergence Form

We consider the second order differential equation , where (x,t) ^N+1, 0<m ₀N, the coefficients a _i,j belong to a suitable space of vanishing mean oscillation functions VMO _L and B=(b _i,j ) is a constant real matrix. The aim of this paper is to study interior regularity for weak solutions to the above equation assuming that F _j belong to a function space of Morrey type.     

Primal separation algorithms

Given an integer polyhedron , an integer point , and a point , the primal separation problem is the problem of finding a linear inequality which is valid for P _I , violated by x ^*, and satisfied at equality by . The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.Received: November 2002, Revised: March 2003,     

On boundedness of (quasi-)convex integer optimization problems

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained integer problem is nonempty over any subset of .     

Inner Product Space and Concept Classes Induced by Bayesian Networks

Bayesian networks have become one of the major models used for statistical inference. In this paper we discuss the properties of the inner product spaces and concept class induced by some special Bayesian networks and the problem whether there exists a Bayesian network such that lower bound on dimensional inner product space just is some positive integer. We focus on two-label classification tasks over the Boolean domain. As main results we show that lower bound on the dimension of the inner product space induced by a class of Bayesian networks without v-structures is where m _i denotes the number of parents for ith variable. As the variable’s number of Bayesian network is n≤5, we also show that for each integer m∈[n+1,2 ⁿ −1] there is a Bayesian network such that VC dimension of concept class and lower bound on dimensional inner product space induced by all are m. This work was supported by National Natural Science Foundation of China (60574075).     

Inequalities for absolute maxima of a polynomial and its derivative

Suppose z ₁, z ₂, ... z _n are complex numbers with absolute values more than 1 and Arg z _j Arg z _k for j k where Arg w stands for the argument of the complex number w in [0,2). In this note we show that

Tight representations of semilattices and inverse semigroups

By a Boolean inverse semigroup we mean an inverse semigroup whose semilattice of idempotents is a Boolean algebra. We study representations of a given inverse semigroup in a Boolean inverse semigroup which are tight in a certain well defined technical sense. These representations are supposed to preserve as much as possible any trace of Booleanness present in the semilattice of idempotents of  . After observing that the Vagner–Preston representation is not tight, we exhibit a canonical tight representation for any inverse semigroup with zero, called the regular tight representation. We then tackle the question as to whether this representation is faithful, but it turns out that the answer is often negative. The lack of faithfulness is however completely understood as long as we restrict to continuous inverse semigroups, a class generalizing the E ^*-unitaries. Partially supported by CNPq.     

On ultraproducts of Boolean algebras and irr

1. Consistent inequality [We prove the consistency of irrirr(B_i)/D where D is an ultrafilter on and each B_i is a Boolean algebra and irr(B) is the maximal size of irredundant subsets of a Boolean algebra B, see full definition in the text. This solves the last problem, 35, of this form from Monk's list of problems in [M2]. The solution applies to many other properties, e.g. Souslinity.] 2. Consistency for small cardinals [We get similar results with =₁ (easily we cannot have it for =₀) and Boolean algebras B_i (i<) of cardinality .] This article continues Magidor Shelah [MgSh:433] and Shelah Spinas [ShSi:677], but does not rely on them: see [M2] for the background. I would like to thank Alice Leonhardt for the beautiful typing. This research was partially supported by the Israel Science Foundation. Publication 703     

Positive solutions to semilinear polyharmonic Dirichlet problems involving critical Sobolev exponents

We are concerned with the semilinear polyharmonic model problem (–)K v = v +v|v| ^s–1 inB,D v|B = 0 for ¦|<-K – 1. HereK ,B is the unit ball in ⁿ,n >2K, is the critical Sobolev exponent. Let ₁ denote the first Dirichlet eigenvalue of (-)^K inB. The existence of a positive radial solutionv is shown for

Finitely generated relatively universal varieties of Heyting algebras

Given distinct varieties and of the same type, we say that is relatively -universal if there exists an embedding :K from a universal categoryK such that for every pairA, B ofK-objects, a homomorphismf:A B has the formf=_g for someK-morphismg:A B if and only if Im(f) . Finitely generated relatively -universal varieties of Heyting algebras are described for the variety of Boolean algebras, the variety generated by a three element chain, and for the variety generated by the four element Boolean algebra with an added greatest element.Dedicated to the memory of Alan DayPresented by J. Sichler.The support of the NSERC is gratefully acknowledged.     

Über Mittelwerte aus Potenzproduktsummen

Using symmetric forms A(n)=number of terms of the sum,a >0,k _i0,i=1,...,n) the meansm _{k 1},...,k_p:=(M_{k 1},...,k_p1/(k₁+...+k_p)(k₁+...+k_p0) are formed and investigated as to monotonicity under the hypothesis that the exponentsk ₁,...,k _p are certain linear functions of only one parameterk(k _i = _i k+ ₁, _i >0, ₁+... _p =0). (The means , e. g., are increasing ifk is increasing.) The proofs are elementary and use the known method of positive logarithmically convex (or concave) sequences and certain generalizations of Muirhead's theorem.     

Random fixed point theorems for a certain class of mappings in banach spaces

Let (, ) be a measurable space and C a nonempty bounded closed convex separable subset of p-uniformly convex Banach space E for some p > 1. We prove random fixed point theorems for a class of mappings T: × C C satisfying: for each x, y C, and integer n 1,

The third boundary value problem in potential theory for domains with a piecewise smooth boundary

The paper investigates the third boundary value problem for the Laplace equation by the means of the potential theory. The solution is sought in the form of the Newtonian potential (1), (2), where is the unknown signed measure on the boundary. The boundary condition (4) is weakly characterized by a signed measure the corresponding operator on the space of signed measures on the boundary of the investigated domain G. If there is 0 such that the essential spectral radius of is smaller than || (for example, if G R ³ is a domain with a piecewise smooth boundary and the restriction of the Newtonian potential on G is a finite continuous functions) then the third problem is uniquely solvable in the form of a single layer potential (1) with the only exception which occurs if we study the Neumann problem for a bounded domain. In this case the problem is solvable for the boundary condition for which (G) = 0.     

Boundary blow-up for a Brezis-Peletier problem on a singular domain

Let , , be a bounded domain as defined by Flucher, Garroni and Müller [6], which has a singular point such that the Robins function achieves its infimum at . Considering the elliptic problem in ; u = 0 on , with p = (N + 2)/(N-2), , and a minimizing solution of , concentrates at as goes to zero.Received: 15 September 2002, Accepted: 5 November 2002, Published online: 16 May 2003Mathematics Subject Classification: 35J65Angela Pistoia: The author is supported by M.U.R.S.T., project Metodi variazionali e topologici nello studio di fenomeni non lineari     

The range of two-parameter random walk in space

Summary Let {X _ij; i>0, j>0} be a double sequence of i.i.d. random variables taking values in the d-dimensional integer lattice E _d . Also let . Then the range of random walk {S _mn: m>0, n>0} up to time (m, n), denoted by R _mn , is the cardinality of the set {S _pq: 0m, n). In this paper a sufficient condition in terms of the characteristic function of X ₁₁ is given so that a.s. as either (m, n) or m(n) tends to infinity.     

Capacitary Estimates for Solutions of the Dirichlet Problem for Second Order Elliptic Equations in Divergence Form

We consider the Dirichlet problem for A-harmonic functions, i.e. the solutions of the uniformly elliptic equationdiv( in an n-dimensional domain , n 3. The matrix A is assumed to have bounded measurable entries. We obtain pointwise estimates for the A-harmonic functions near a boundary point. The estimates are in terms of the Wiener capacity and the so called capacitary interior diameter. They imply pointwise estimates for the A-harmonic measure of the domain , which in turn lead to a sufficient condition for the Hölder continuity of A-harmonic functions at a boundary point. The behaviour of A-harmonic functions at infinity and near a singular point is also studied and theorems of Phragmén–Lindelöf type, in which the geometry of the boundary is taken into account, are proved. We also obtain pointwise estimates for the Green function for the operator -div( in a domain and for the solutions of the nonhomogeneous equation -div with measure on the right-hand side.