Multivariate McCormick relaxations

McCormick (Math Prog 10(1):147–175, 1976) provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form \(F\circ f\) , where \(F\) is a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions \(F\) , and theory for the propagation of subgradients is presented. The generalization interprets the McCormick relaxation approach as a decomposition method for the auxiliary variable method. In addition to extending the framework, the new result provides a tool for the proof of relaxations of specific functions. Moreover, a direct consequence is an improved relaxation for the product of two functions, at least as tight as McCormick’s result, and often tighter. The result also allows the direct relaxation of multilinear products of functions. Furthermore, the composition result is applied to obtain improved convex underestimators for the minimum/maximum and the division of two functions for which current relaxations are often weak. These cases can be extended to allow composition of a variety of functions for which relaxations have been proposed.     

Generalized McCormick relaxations

Convex and concave relaxations are used extensively in global optimization algorithms. Among the various techniques available for generating relaxations of a given function, McCormick’s relaxations are attractive due to the recursive nature of their definition, which affords wide applicability and easy implementation computationally. Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures. This article leverages the recursive nature of McCormick’s relaxations to define a generalized form which both affords a new framework within which to analyze the properties of McCormick’s relaxations, and extends the applicability of McCormick’s technique to challenging open problems in global optimization. Specifically, relaxations of the parametric solutions of ordinary differential equations are considered in detail, and prospects for relaxations of the parametric solutions of nonlinear algebraic equations are discussed. For the case of ODEs, a complete computational procedure for evaluating convex and concave relaxations of the parametric solutions is described. Through McCormick’s composition rule, these relaxations may be used to construct relaxations for very general optimal control problems.     

Convergence rate of McCormick relaxations

Theory for the convergence order of the convex relaxations by McCormick (Math Program 10(1):147–175, 1976) for factorable functions is developed. Convergence rules are established for the addition, multiplication and composition operations. The convergence order is considered both in terms of pointwise convergence and of convergence in the Hausdorff metric. The convergence order of the composite function depends on the convergence order of the relaxations of the factors. No improvement in the order of convergence compared to that of the underlying bound calculation, e.g., via interval extensions, can be guaranteed unless the relaxations of the factors have pointwise convergence of high order. The McCormick relaxations are compared with the αBB relaxations by Floudas and coworkers (J Chem Phys, 1992, J Glob Optim, 1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

Differentiable Distance Spaces

The distance function \({\varrho(p, q) ({\rm or} d(p, q))}\) of a distance space (general metric space) is not differentiable in general. We investigate such distance spaces over \({\mathbb{R}^n}\), whose distance functions are differentiable like in case of Finsler spaces. These spaces have several good properties, yet they are not Finsler spaces (which are special distance spaces). They are situated between general metric spaces (distance spaces) and Finsler spaces. We will investigate such curves of differentiable distance spaces, which possess the same properties as geodesics do in Finsler spaces. So these curves can be considered as forerunners of Finsler geodesics. They are in greater plenitude than Finsler geodesics, but they become geodesics in a Finsler space. We show some properties of these curves, as well as some relations between differentiable distance spaces and Finsler spaces. We arrive to these curves and to our results by using distance spheres, and using no variational calculus. We often apply direct geometric considerations.     

On Skorokhod Differentiable Measures

Ukrainian Mathematical Journal - We present a survey of the Skorohod differentiability of measures on linear spaces, which also gives new proofs of some key results in this area parallel with some...     

Forcing and Differentiable Functions

We consider covering $\aleph_1 \times \aleph_1$ rectangles by countably many smooth curves, and differentiable isomorphisms between $\aleph_1$ -dense sets of reals.     

一个处处连续但处处不可导的一元函数

通过分析一元函数连续性与可导性之间的联系,构造出一个在实数域上处处连续但处处不可导的一元函数.     

Differentiable perturbation of unbounded operators

If A(t) is a C^1,-curve of unbounded self-adjoint operators with compact resolvents and common domain of definition, then the eigenvalues can be parameterized C¹ in t. If A is C then the eigenvalues can be parameterized twice differentiably.Mathematics Subject Classification (2000): 26C10PWM was supported by FWF, Projekt P 14195 MAT.     

Differentiable Functions on the Rationals

We construct a smooth bijective function from the rationalsto the rationals whose inverse is nowhere continuous.     

Differentiable functions of quaternion variables

We investigate differentiability of functions defined on regions of the real quaternion field and obtain a noncommutative version of the Cauchy-Riemann conditions. Then we study the noncommutative analog of the Cauchy integral as well as criteria for functions of a quternion variable to be analytic. In particular, the quaternionic exponential and logarithmic functions are being considered. Main results include quaternion versions of Hurwitz' theorem, Mittag-Leffler's theorem and Weierstrass' theorem.     

Differentiable monoids with smooth boundary

We investigate here the structure of monoids which are based upon differentiable manifolds with smooth boundary and which have differentiable multiplication function. If the multiplication function of such a monoid, S, is C^k for k≥2 and the unit element, 1, is in the boundary then the maximal subgroup, H(1), of S containing 1 is a C^k group which is an open subgroup of the boundary of S.     

Differentiable programming in Banach spaces

For an abstract differentiate mathematical programming problem defined in a Banach space we obtain generalized Kuhn-Tucker necessary conditions for optimality. We obtain these conditions by replacing the usual closed cone hypothesis by a closed range condition on a suitable linear operator. The latter condition is automatically satisfied in finite dimensions.