A note on duality gap in the simple plant location problem

This paper studies the duality gap in the simple plant location problem, and presents general formulas for the gap when certain complementary slackness conditions are satisfied. We show that the duality gap derived by Erlenkotter [A dual-based procedure for uncapacitated facility location, Operations Research 26 (1978) 992–1009], and which has been widely used in the literature, is a special case of the formulas presented here. A counterexample demonstrates that an underlying assumption in Erlenkotter may be violated. The results may be used to obtain improved lower bounds for branch-and-bound algorithms.     

q-Hypergeometric Series and Macdonald Functions

We derive a duality formula for two-row Macdonald functions by studying their relation with basic hypergeometric functions. We introduce two parameter vertex operators to construct a family of symmetric functions generalizing Hall-Littlewood functions. Their relation with Macdonald functions is governed by a very well-poised q-hypergeometric functions of type ₄₃, for which we obtain linear transformation formulas in terms of the Jacobi theta function and the q-Gamma function. The transformation formulas are then used to give the duality formula and a new formula for two-row Macdonald functions in terms of the vertex operators. The Jack polynomials are also treated accordingly.     

Nonstationary generalized Duru-Kleinert transformation of path integrals for systems of differential equations in one-dimensional space

We obtain new formulas for the transformations of Wiener path integrals corresponding to the parabolic systems of two differential equations with time-dependent coefficients in one-dimensional space. These formulas determine the transformation of the path integrals under a rheonomous-homogeneous-pointwise transformation of integration variables and the path reparameterization transformation. These formulas allow us to obtain an integral relation between the Green's functions of related systems of differential equations. We show how to obtain the generalized Shepp formula from this relation for the path integral under consideration. We derive these new formulas using the properties of random processes under phase transitions and a random change in time.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 109, No. 1, pp. 17–27, October, 1996.     

The Thresholding Greedy Algorithm, Greedy Bases, and Duality

Some new conditions that arise naturally in the study of the Thresholding Greedy Algorithm are introduced for bases of Banach spaces. We relate these conditions to best n-term approximation and we study their duality theory. In particular, we obtain a complete duality theory for greedy bases.     

Mixed Measures of Convex Cylinders and Quermass Densities of Boolean Models

Translative integral formulas for curvature measures of convex bodies were obtained by Schneider and Weil by introducing mixed measures of convex bodies. These results can be extended to arbitrary closed convex sets since mixed measures are locally defined. Furthermore, iterated versions of these formulas due to Weil were used by Fallert to introduce quermass densities for (non-stationary and non-isotropic) Poisson processes of convex bodies and respective Boolean models. In the present paper, we first compute the special form of mixed measures of convex cylinders and prove a translative integral formula for them. After adapting some results for mixed measures of convex bodies to this setting we then use this integral formula to obtain quermass densities for (non-stationary and non-isotropic) Poisson processes of convex cylinders. Furthermore, quermass densities of Boolean models of convex cylinders are expressed in terms of mixed densities of the underlying Poisson process generalizing classical formulas by Davy and recent results by Spiess and Spodarev.      

Duality estimates for the numerical solution of integral equations

Summary We formulate and prove Aubin-Nitsche-type duality estimates for the error of general projection methods. Examples of applications include collocation methods and augmented Galerkin methods for boundary integral equations on plane domains with corners and three-dimensional screen and crack problems. For some of these methods, we obtain higher order error estimates in negative norms in cases where previous formulations of the duality arguments were not applicable.     

Testing copositivity with the help of difference-of-convex optimization

We consider the problem of minimizing an indefinite quadratic form over the nonnegative orthant, or equivalently, the problem of deciding whether a symmetric matrix is copositive. We formulate the problem as a difference of convex functions problem. Using conjugate duality, we show that there is a one-to-one correspondence between their respective critical points and minima. We then apply a subgradient algorithm to approximate those critical points and obtain an efficient heuristic to verify non-copositivity of a matrix.     

Some basic relationships among transforms, convolution products, first variations and inverse transforms

In this paper we obtain several basic formulas for generalized integral transforms, convolution products, first variations and inverse integral transforms of functionals defined on function space.     

On The Existence of a Countable Set of Positive Solutions for a Nonlocal Boundary-Value Problem with Vector-Valued Response

ABSTRACT

The existence of a countable set of positive solutions for a nonlocal boundary-value problem with vector-valued response is investigated by some variational methods based on the idea of the Fenchel conjugate. As a consequence of a duality developed here, we obtain the existence of a countable set of solutions for our problem that are minimizers to a certain integral functional. We derive (also in the superlinear case) a measure of a duality gap between primal and dual functional for approximate solutions.     

Characterization of infinite divisibility by duality formulas. Application to Lévy processes and random measures

Processes with independent increments are proven to be the unique solutions of duality formulas. This result is based on a simple characterization of infinitely divisible random vectors by a functional equation in which a difference operator appears. This operator is constructed by a variational method and compared to approaches involving chaos decompositions. We also obtain a related characterization of infinitely divisible random measures.     

Convex Duality and Calculus: Reduction to Cones

An attempt is made to justify results from Convex Analysis by means of one method. Duality results, such as the Fenchel-Moreau theorem for convex functions, and formulas of convex calculus, such as the Moreau-Rockafellar formula for the subgradient of the sum of sublinear functions, are considered. All duality operators, all duality theorems, all standard binary operations, and all formulas of convex calculus are enumerated. The method consists of three automatic steps: first translation from the given setting to that of convex cones, then application of the standard operations and facts (the calculi) for convex cones, finally translation back to the original setting. The advantage is that the calculi are much simpler for convex cones than for other types of convex objects, such as convex sets, convex functions and sublinear functions. Exclusion of improper convex objects is not necessary, and recession directions are allowed as points of convex objects. The method can also be applied beyond the enumeration of the calculi.     

A Characterization of Grand Canonical Gibbs Measures by Duality

We introduce Skorohod type integral operators that satisfy an integration by parts formula under Gibbs measures and obtain a characterization of grand canonical Gibbs measures by duality, without use of a differential structure on the underlying configuration space.     

Distributive Envelopes and Topological Duality for Lattices via Canonical Extensions

We establish a topological duality for bounded lattices. The two main features of our duality are that it generalizes Stone duality for bounded distributive lattices, and that the morphisms on either side are not the standard ones. A positive consequence of the choice of morphisms is that those on the topological side are functional. Towards obtaining the topological duality, we develop a universal construction which associates to an arbitrary lattice two distributive lattice envelopes with a Galois connection between them. This is a modification of a construction of the injective hull of a semilattice by Bruns and Lakser, adjusting their concept of ‘admissibility’ to the finitary case. Finally, we show that the dual spaces of the distributive envelopes of a lattice coincide with completions of quasi-uniform spaces naturally associated with the lattice, thus giving a precise spatial meaning to the distributive envelopes.     

Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution

We prove duality results for adjoint operators and product norms in the framework of Euclidean spaces. We show how these results can be used to derive condition numbers especially when perturbations on data are measured componentwise relatively to the original data. We apply this technique to obtain formulas for componentwise and mixed condition numbers for a linear function of a linear least squares solution. These expressions are closed when perturbations of the solution are measured using a componentwise norm or the infinity norm and we get an upper bound for the Euclidean norm.      

关于一些数值求积公式的渐近性

该文给出了一些数值求积公式的渐近性质,这些公式包括求积分的矩形法则、梯形法则和抛物线法则,包含于余项中的中介点的位置当积分区间的长度趋于零时被确定,对应于该法则的校正公式被得到,它们具有较高的代数精度,我们也进行了一些数值试验,得到较满意的数值结果。     

R~(n+1)中常高阶平均曲率超曲面

本文给出了Rn+1中超曲面的一些积分公式,并利用这些积分公式得到了以球面为边界的常高阶平均曲率超曲面的一些唯一性结果.     

Applications of optimization methods to robust stability of linear systems

We study the robust stability problem for a family of polynomials. We allow for all the coefficients of the polynomials to be affinely perturbed, where the size of the perturbation is measured by an arbitrary convex function. We apply optimization techniques, and in particular convex duality methods, to derive simple formulas for the stability radius, to find a minimal perturbation which destroys stability, and to obtain necessary and sufficient conditions for robust stability. Our framework is general enough to cover many applications. As special cases, we obtain many results recently reported in the literature.The work of the first author was partially supported by AFOSR Grant 91-008 and NSF Grant DMS-92-01297.     

On the optimality of some classes of invex problems

In this paper we define two notions: Kuhn–Tucker saddle point invex problem with inequality constraints and Mond–Weir weak duality invex one. We prove that a problem is Kuhn–Tucker saddle point invex if and only if every point, which satisfies Kuhn–Tucker optimality conditions forms together with the respective Lagrange multiplier a saddle point of the Lagrange function. We prove that a problem is Mond–Weir weak duality invex if and only if weak duality holds between the problem and its Mond–Weir dual one. Additionally, we obtain necessary and sufficient conditions, which ensure that strong duality holds between the problem with inequality constraints and its Wolfe dual. Connections with previously defined invexity notions are discussed.     

Solution of certain weakly singular integral equations of the first kind with indefinite parameters

In this paper we study a two-dimensional weakly singular integral equation of the first kind with logarithmic kernel. We construct a pair of spaces of the desired elements and the right-hand sides, where we prove the correctness of the problem under consideration and obtain inversion formulas for the integral operator.