Tight convex underestimators for $${\mathcal{C}^2}$$ -continuous problems: II. multivariate functions

In Part I (Gounaris, C.E., Floudas, C.A.: Tight convex understimators for -continuous functions: I: Univariate functions. J. Global Optim. (2008). doi: ), we introduced a novel approach for the underestimation of univariate functions which was based on a piecewise application of the well-known αBB underestimator. The resulting underestimators were shown to be very tight and, in fact, can be driven to coincide with the convex envelopes themselves. An approximation by valid linear supports, resulting in piecewise linear underestimators was also presented. In this paper, we demonstrate how one can make use of the high quality results of the approach in the univariate case so as to extend its applicability to functions with a higher number of variables. This is achieved by proper projections of the multivariate αBB underestimators into select two-dimensional planes. Furthermore, since our method utilizes projections into lower-dimensional spaces, we explore ways to recover some of the information lost in this process. In particular, we apply our method after having transformed the original problem in an orthonormal fashion. This leads to the construction of even tighter underestimators, through the accumulation of additional valid linear cuts in the relaxation.     

Convex Underestimation of Twice Continuously Differentiable Functions by Piecewise Quadratic Perturbation: Spline αBB Underestimators

This paper describes the construction of convex underestimators for twice continuously differentiable functions over box domains through piecewise quadratic perturbation functions. A refinement of the classical α BB convex underestimator, the underestimators derived through this approach may be significantly tighter than the classical αBB underestimator. The convex underestimator is the difference of the nonconvex function f and a smooth, piecewise quadratic, perturbation function, q. The convexity of the underestimator is guaranteed through an analysis of the eigenvalues of the Hessian of f over all subdomains of a partition of the original box domain. Smoothness properties of the piecewise quadratic perturbation function are derived in a manner analogous to that of spline construction.     

Analysis of Bounds for Multilinear Functions

We analyze four bounding schemes for multilinear functions and theoretically compare their tightness. We prove that one of the four schemes provides the convex envelope and that two schemes provide the concave envelope for the product of p variables over .     

A New Class of Improved Convex Underestimators for Twice Continuously Differentiable Constrained NLPs

We present a new class of convex underestimators for arbitrarily nonconvex and twice continuously differentiable functions. The underestimators are derived by augmenting the original nonconvex function by a nonlinear relaxation function. The relaxation function is a separable convex function, that involves the sum of univariate parametric exponential functions. An efficient procedure that finds the appropriate values for those parameters is developed. This procedure uses interval arithmetic extensively in order to verify whether the new underestimator is convex. For arbitrarily nonconvex functions it is shown that these convex underestimators are tighter than those generated by the BB method. Computational studies complemented with geometrical interpretations demonstrate the potential benefits of the proposed improved convex underestimators.     

Trilinear Monomials with Mixed Sign Domains: Facets of the Convex and Concave Envelopes

Convex underestimators of nonconvex functions, frequently used in deterministic global optimization algorithms, strongly influence their rate of convergence and computational efficiency. A good convex underestimator is as tight as possible and introduces a minimal number of new variables and constraints. Multilinear monomials over a coordinate aligned hyper-rectangular domain are known to have polyhedral convex envelopes which may be represented by a finite number of facet inducing inequalities. This paper describes explicit expressions defining the facets of the convex and concave envelopes of trilinear monomials over a box domain with bounds of opposite signs for at least one variable. It is shown that the previously used approximations based on the recursive use of the bilinear construction rarely yield the convex envelope itself.     

$${\cal K}$$-Convexity1 in $$\Re^{n}$$

We generalize the concept of K-convexity to an n-dimensional Euclidean space. The resulting concept of -convexity is useful in addressing production and inventory problems where there are individual product setup costs and/or joint setup costs. We derive some basic properties of -convex functions. We conclude the paper with some suggestions for future research. Support from Columbia University and University of Texas at Dallas is gratefully acknowledged. Helpful comments from Qi Feng are appreciated.     

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 .     

Geometric dual formulation for first-derivative-based univariate cubic <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript> splines

With the objective of generating “shape-preserving” smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based -smooth univariate cubic L ₁ splines. An L ₁ spline minimizes the L ₁ norm of the difference between the first-order derivative of the spline and the local divided difference of the data. Calculating the coefficients of an L ₁ spline is a nonsmooth non-linear convex program. Via Fenchel’s conjugate transformation, the geometric dual program is a smooth convex program with a linear objective function and convex cubic constraints. The dual-to-primal transformation is accomplished by solving a linear program.     

A representation of bivariate extreme value distributions via norms on \mathbb{R}^{2}

It is known that a bivariate extreme value distribution (EVD) with reverse exponential margins can be represented as , , where is a suitable norm on . We prove in this paper the converse implication, i.e., given an arbitrary norm on , , , defines an EVD with reverse exponential margins, if and only if the norm satisfies for the condition . This result is extended to bivariate EVDs with arbitrary margins as well as to extreme value copulas. By identifying an EVD , , with the unit ball corresponding to the generating norm , we obtain a characterization of the class of EVDs in terms of compact and convex subsets of .     

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

Inequalities of the Brunn–Minkowski type for Gaussian measures

Let be an integer, let γ be the standard Gaussian measure on , and let . Given this paper gives a necessary and sufficient condition such that the inequality is true for all Borel sets A ₁,...,A _m in of strictly positive γ-measure or all convex Borel sets A ₁,...,A _m in of strictly positive γ-measure, respectively. In particular, the paper exhibits inequalities of the Brunn–Minkowski type for γ which are true for all convex sets but not for all measurable sets.      

Convex underestimators of polynomials

Convex underestimators of a polynomial on a box. Given a non convex polynomial ${f\in \mathbb{R}[{\rm x}]}$ and a box ${{\rm B}\subset \mathbb{R}^n}$ , we construct a sequence of convex polynomials ${(f_{dk})\subset \mathbb{R}[{\rm x}]}$ , which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator ${f^{*}_{d}}$ of f. Indeed, ${f^{*}_{d}}$ minimizes the L ₁-norm ${\Vert f-g\Vert_1}$ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular α BB method and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k.     

Sufficient conditions for the convexity of the level sets of ground-state solutions

Let Ω be a bounded convex domain in . We consider constrained minimization problems related to the Euler-Lagrange equation

Laguerre geometry of hypersurfaces in $$\mathbb{R}^{n}$$

Laguerre geometry of surfaces in is given in the book of Blaschke [Vorlesungen über Differentialgeometrie, Springer, Berlin Heidelberg New York (1929)], and has been studied by Musso and Nicolodi [Trans. Am. Math. soc. 348, 4321–4337 (1996); Abh. Math. Sem. Univ. Hamburg 69, 123–138 (1999); Int. J. Math. 11(7), 911–924 (2000)], Palmer [Remarks on a variation problem in Laguerre geometry. Rendiconti di Mathematica, Serie VII, Roma, vol. 19, pp. 281–293 (1999)] and other authors. In this paper we study Laguerre differential geometry of hypersurfaces in . For any umbilical free hypersurface with non-zero principal curvatures we define a Laguerre invariant metric g on M and a Laguerre invariant self-adjoint operator : TM → TM, and show that is a complete Laguerre invariant system for hypersurfaces in with n≥ 4. We calculate the Euler–Lagrange equation for the Laguerre volume functional of Laguerre metric by using Laguerre invariants. Using the Euclidean space , the semi-Euclidean space and the degenerate space we define three Laguerre space forms , and and define the Laguerre embeddings and , analogously to what happens in the Moebius geometry where we have Moebius space forms S ⁿ , and (spaces of constant curvature) and conformal embeddings and [cf. Liu et al. in Tohoku Math. J. 53, 553–569 (2001) and Wang in Manuscr. Math. 96, 517–534 (1998)]. Using these Laguerre embeddings we can unify the Laguerre geometry of hypersurfaces in , and . As an example we show that minimal surfaces in or are Laguerre minimal in .C. Wang Partially supported by RFDP and Chuang-Xin-Qun-Ti of NSFC.     

Exact inequalities for sums of asymmetric random variables, with applications

Let be independent identically distributed random variables each having the standardized Bernoulli distribution with parameter . Let if and . Let . Let f be such a function that f and f′′ are nondecreasing and convex. Then it is proved that for all nonnegative numbers one has the inequality where . The lower bound on m is exact for each . Moreover, is Schur-concave in . A number of corollaries are obtained, including upper bounds on generalized moments and tail probabilities of (super)martingales with differences of bounded asymmetry, and also upper bounds on the maximal function of such (super)martingales. Applications to generalized self-normalized sums and t-statistics are given.      

Supremizers of inner <Emphasis Type="Italic">γ</Emphasis>-convex functions

A real-valued function f defined on a convex subset D of some normed linear space is said to be inner γ-convex w.r.t. some fixed roughness degree γ > 0 if there is a such that holds for all satisfying ||x ₀ − x ₁|| = νγ and . This kind of roughly generalized convex functions is introduced in order to get some properties similar to those of convex functions relative to their supremum. In this paper, numerous properties of their supremizers are given, i.e., of such satisfying lim . For instance, if an upper bounded and inner γ-convex function, which is defined on a convex and bounded subset D of some inner product space, has supremizers, then there exists a supremizer lying on the boundary of D relative to aff D or at a γ-extreme point of D, and if D is open relative to aff D or if dim D ≤ 2 then there is certainly a supremizer at a γ-extreme point of D. Another example is: if D is an affine set and is inner γ-convex and bounded above, then for all , and if 2 ≤ dim D < ∞ then each is a supremizer of f.      

Banach-Steinhaus properties of strictly $$ \mathcal{N} $$-locally convex spaces based on the principle of uniform boundedness

Using the principle of uniform boundedness in a strictly -locally convex spaces, we establish a Banach-Steinhaus-type result for sequentially continuous linear operators.      

On the Structure and Symmetry Properties of Almost $$\cal{S}$$-manifolds

We prove that any simply connected -manifold of CR-codimension s 2 is noncompact by showing that the complete, simply connected -manifolds are all the CR products N × ^{s-1} with N Sasakian, endowed with a suitable product metric. N is a Sasakian -symmetric space if and only if M is CR-symmetric. The locally CR-symmetric -manifolds are characterized by

On the Circumference of 2-Connected $$\mathcal{P}_{3}$$-Dominated Graphs

Let G be a connected graph. For at distance 2, we define , and , if then . G is quasi-claw-free if it satisfies , and G is P ₃-dominated() if it satisfies , for every pair (x, y) of vertices at distance 2. Certainly contains as a subclass. In this paper, we prove that the circumference of a 2-connected P ₃-dominated graph G on n vertices is at least min or , moreover if then G is hamiltonian or , where is a class of 2-connected nonhamiltonian graphs.     

CR-Admissible $$\mathbb{{Z}}_{2}$$-gradations and CR-symmetries

Complementing the results of (Lotta and Nacinovich, Adv. Math. 191(1): 114–146, 2005), we show that the minimal orbit M of a real form G of a semisimple complex Lie group in a flag manifold is CR-symmetric (see (Kaup and Zaitsev Adv. Math. 149(2):145–181, 2000)) if and only if the corresponding CR algebra admits a gradation compatible with the CR structure.