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.     

Convex relaxation for solving posynomial programs

Convex underestimation techniques for nonlinear functions are an essential part of global optimization. These techniques usually involve the addition of new variables and constraints. In the case of posynomial functions \({x_1^{\alpha _1 } x_2^{\alpha _2 }\ldots x_n^{\alpha _n } ,}\) logarithmic transformations (Maranas and Floudas, Comput. Chem. Eng. 21:351–370, 1997) are typically used. This study develops an effective method for finding a tight relaxation of a posynomial function by introducing variables y _j and positive parameters β _j , for all α _j > 0, such that \({y_j =x_j^{-\beta _j }}\) . By specifying β _j carefully, we can find a tighter underestimation than the current methods.     

Convex spectral functions

In this paper we characterize all convex functionals defined on certain convex sets of hermitian matrices and which depend only on the eigenvalues of matrices. We extend these results to certain classes of non-negative matrices. This is done by formulating some new characterizations for the spectral radius of non-negative matrices, which are of independent interest.     

Popoviciu's inequality for functions of several variables

T. Popoviciu (1965) [13] has proved an interesting characterization of the convex functions of one real variable, based on an inequality relating the values at any three points x₁,x₂,x₃, with the values at their means of different orders: (x₁+x₂)/2, (x₂+x₃)/2, (x₃+x₁)/2 and (x₁+x₂+x₃)/3. The aim of our paper is to develop a higher dimensional analogue of the usual convexity based on his characterization.     

Superquadratic functions in several variables

The concept of superquadratic functions in several variables, as a generalization of the same concept in one variable is introduced. Analogous results to results obtained for convex functions in one and several variables are presented. These include refinements of Jensen's inequality and its counterpart, and of Slater-Pe?ari?'s inequality.     

Convex functions, subdifferentiability and renormings

This paper through discussing subdifferentiability and convexity of convex functions shows that a Banach space admits an equivalent uniformly [locally uniformly, strictly] convex norm if and only if there exists a continuous uniformly [locally uniformly, strictly] convex function on some nonempty open convex subset of the space and presents some characterizations of super-reflexive Banach spaces. Supported by NSFC     

Trigonometric Convex Underestimator for the Base Functions in Fourier Space

A three-parameter (a, b, x_s) convex underestimator of the functional form (x) = -a sin[k(x-x_s)] + b for the function f(x) = sin(x+s), x [x_L, x_U], is presented. The proposed method is deterministic and guarantees the existence of at least one convex underestimator of this functional form. We show that, at small k, the method approaches an asymptotic solution. We show that the maximum separation distance of the underestimator from the minimum of the function grows linearly with the domain size. The method can be applied to trigonometric polynomial functions of arbitrary dimensionality and arbitrary degree. We illustrate the features of the new trigonometric underestimator with numerical examples.Support from the National Science Foundation and the National Institutes of Health Grant R01 GM52032 is gratefully acknowledged.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

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.     

Whitney differentiability of optimal-value functions for bound-constrained convex programming problems

ABSTRACT

In the spirit of the Whitney Extension Theorem, consider a function on a compact subset of Euclidean space to be ‘Whitney-differentiable’ if it is a restriction of a continuously Fréchet-differentiable function with an open domain. Whitney-differentiable functions have been shown to have useful (yet possibly nonunique) derivatives and calculus properties even on the boundaries of their domains. This article shows that optimal-value functions for bound-constrained convex programmes with Whitney-differentiable objective functions are themselves Whitney-differentiable, even when the linear-independence constraint qualification is not satisfied. This result extends classic sensitivity results for convex programmes, and generalizes recent work. As an application, sufficient conditions are presented for generating continuously differentiable convex underestimators of nonconvex functions for use in methods for deterministic global optimization in the multivariate McCormick framework. In particular, the main result is applied to generate Whitney-differentiable convex underestimators for quotients of functions with known Whitney-differentiable relaxations.     

Convex composite minimization withC 1,1 functions

In this paper, we present second-order optimality conditions for convex composite minimization problems in which the objective function is a composition of a finite-valued or a nonfinite-valued lower semicontinuous convex function and aC ^1,1 function. The results provide optimality conditions for composite problems under reduced differentiability requirements.This paper is a revised version of the Departmental Preliminary Report AM92/32, School of Mathematics, University of New South Wales, Kensington, NSW, Australia.Research of this author was supported in part by an Australian Research Council Grant.     

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 .     

Computational Experience with a New Class of Convex Underestimators: Box-constrained NLP Problems

In Akrotirianakis and Floudas (2004) we presented the theoretical foundations of a new class of convex underestimators for C ² nonconvex functions. In this paper, we present computational experience with those underestimators incorporated within a Branch-and-Bound algorithm for box-conatrained problems. The algorithm can be used to solve global optimization problems that involve C ² functions. We discuss several ways of incorporating the convex underestimators within a Branch-and-Bound framework. The resulting Branch-and-Bound algorithm is then used to solve a number of difficult box-constrained global optimization problems. A hybrid algorithm is also introduced, which incorporates a stochastic algorithm, the Random-Linkage method, for the solution of the nonconvex underestimating subproblems, arising within a Branch-and-Bound framework. The resulting algorithm also solves efficiently the same set of test problems.     

对数凸模糊映射

利用模糊数的表示定理,本文证明了对数凸模糊映射一些基本性质,并纠正了S.N anda和K.K ar对数凸模糊映射定义的不合理性和其证明中的错误。     

有界凸平衡域上的双全纯凸映照的判别准则

本文讨论Cn中有界强凸平衡域和凸平衡域上局部双全纯映照成为双全纯凸映照的充要条件,从而得到Reinhardt域Dp= 上双全纯凸映照的充要条件,其中Pj≥2(j=1,2,…,n).     

Tight convex underestimators for {{\mathcal C}^2}-continuous problems: I. univariate functions

A novel method for the convex underestimation of univariate functions is presented in this paper. The method is based on a piecewise application of the well-known αBB underestimator, which produces an overall underestimator that is piecewise convex. Subsequently, two algorithms are used to identify the linear segments needed for the construction of its -continuous convex envelope, which is itself a valid convex underestimator of the original function. The resulting convex underestimators are very tight, and their tightness benefits from finer partitioning of the initial domain. It is theoretically proven that there is always some finite level of partitioning for which the method yields the convex envelope of the function of interest. The method was applied on a set of univariate test functions previously presented in the literature, and the results indicate that the method produces convex underestimators of high quality in terms of both lower bound and tightness over the whole domain under consideration.     

Two Inequalities for Convex Functions

Let a ₀ < a ₁ < ··· < a _n be positive integers with sums $ {\sum\nolimits_{i = 0}^n {\varepsilon _{i} a_{i} {\left( {\varepsilon _{i} = 0,1} \right)}} } Let a ₀ < a ₁ < ··· < a _n be positive integers with sums distinct. P. Erd?s conjectured that The best known result along this line is that of Chen: Let f be any given convex decreasing function on [A, B] with α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n being real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , Then In this paper, we obtain two generalizations of the above result; each is of special interest in itself. We prove: Theorem 1 Let f and g be two given non-negative convex decreasing functions on [A, B], and α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n , α' ₀, α' ₁, ... , α' _n , β' ₀ , β' ₁ , ... , β' _n be real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , α' ₀ ≤ α' ₁ ≤ ··· ≤ α' _n , Then Theorem 2 Let f be any given convex decreasing function on [A, B] with k ₀, k ₁, ... , k _n being nonnegative real numbers and α ₀, α ₁, ... , α _n , β ₀, β ₁, ... , β _n being real numbers in [A, B] with α ₀ ≤ α ₁ ≤ ··· ≤ α _n , Then      

On Convex Class of Pairs of Convex Bodies

In this paper we introduce a quotient class of pairs of convex bodies in which every member have convex union.

     

Convex Holes Produce Lower Bounds for Coefficients

Let D denote the open unit disk and $ f:D \to \bar {{\bf C}}$ be meromorphic and injective in D . Especially, we consider such f which have an expansion $$ f(z) = z + \sum \limits_{n=2}^{\infty }a_n(\;f\,)z^n $$ in a neighbourhood of the origin and map D onto a domain whose complement with respect to $\bar {{\bf C}}$ is convex. Let the set of these functions be denoted by Co . We fix | f m 1 ( X )| for f ] Co and determine the inner and outer radius of the ring domain which is the domain of variability of a 2 ( f ) for such f . Further, it is shown that f ] Co implies that $$ \phi (z) = z+2 {f'(z) \over f''(z)}$$ is holomorphic in D and maps D into itself. This implication in turn implies the inequalities | a n ( f )| S 1 for f ] Co and n = 2,3,4. In addition, we show that | a n ( f )| S 1/2 for f ] Co and all n S 2 .     

几种凸模糊集间的转换关系

在引用扎德所定义的凸模糊集、强凸模糊集、严格凸模糊集等概念的基础上，探讨了这三种凸模糊集间的转换条件，得到凸模糊集与强凸模糊集、强凸模糊集与严格凸模糊集间的等价条件。