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.     

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 relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Tight wavelet frames via semi-definite programming

In this paper we state the “oblique extension principle” as a problem of semi-definite programming. Using this optimization technique we show that the existence of a tight frame is equivalent to the existence of a certain matrix from a cone of positive semi-definite matrices, whose entries satisfy linear constraints. We also discuss how to use the optimization techniques to reduce the number of frame generators in univariate and multivariate cases. We apply our results for constructing tight frames for several subdivision schemes.     

The effect of transformations on the approximation of univariate (convex) functions with applications to Pareto curves

In the literature, methods for the construction of piecewise linear upper and lower bounds for the approximation of univariate convex functions have been proposed. We study the effect of the use of transformations on the approximation of univariate (convex) functions. In this paper, we show that these transformations can be used to construct upper and lower bounds for nonconvex functions. Moreover, we show that by using such transformations of the input variable or the output variable, we obtain tighter upper and lower bounds for the approximation of convex functions than without these approximations. We show that these transformations can be applied to the approximation of a (convex) Pareto curve that is associated with a (convex) bi-objective optimization problem.     

Maximum likelihood estimation of a multivariate linear functional relationship

Many authors have discussed maximum likelihood estimation in the simple linear functional relationship model. In this paper, we derive maximum likelihood estimators (MLEs) for parameters in a much more general model. Several special cases including the multivariate linear functional relationship model are discussed. Estimators of some of the parameters are shown to be inconsistent.     

Robust weighted orthogonal regression in the errors-in-variables model

This paper focuses on robust estimation in the structural errors-in-variables (EV) model. A new class of robust estimators, called weighted orthogonal regression estimators, is introduced. Robust estimators of the parameters of the EV model are simply derived from robust estimators of multivariate location and scatter such as the M-estimators, the S-estimators and the MCD estimator. The influence functions of the proposed estimators are calculated and shown to be bounded. Moreover, we derive the asymptotic distributions of the estimators and illustrate the results on simulated examples and on a real-data set.     

Approximation order of interpolatory nonlinear subdivision schemes

Linear interpolatory subdivision schemes of C^r smoothness have approximation order at least r+1. The present paper extends this result to nonlinear univariate schemes which are in proximity with linear schemes in a certain specific sense. The results apply to nonlinear subdivision schemes in Lie groups and in surfaces which are obtained from linear subdivision schemes. We indicate how to extend the results to the multivariate case.     

Multivariate Locally Weighted Polynomial Fitting and Partial Derivative Estimation

Nonparametric regression estimator based on locally weighted least squares fitting has been studied by Fan and Ruppert and Wand. The latter paper also studies, in the univariate case, nonparametric derivative estimators given by a locally weighted polynomial fitting. Compared with traditional kernel estimators, these estimators are often of simpler form and possess some better properties. In this paper, we develop current work on locally weighted regression and generalize locally weighted polynomial fitting to the estimation of partial derivatives in a multivariate regression context. Specifically, for both the regression and partial derivative estimators we prove joint asymptotic normality and derive explicit asymptotic expansions for their conditional bias and conditional convariance matrix (given observations of predictor variables) in each of the two important cases of local linear fit and local quadratic fit.     

Admissibilities of linear estimator in a class of linear models with a multivariate t error variable

This paper discusses admissibilities of estimators in a class of linear models,which include the following common models:the univariate and multivariate linear models,the growth curve model,the extended growth curve model,the seemingly unrelated regression equations,the variance components model,and so on.It is proved that admissible estimators of functions of the regression coefficient β in the class of linear models with multivariate t error terms,called as Model II,are also ones in the case that error terms have multivariate normal distribution under a strictly convex loss function or a matrix loss function.It is also proved under Model II that the usual estimators of β are admissible for p 2 with a quadratic loss function,and are admissible for any p with a matrix loss function,where p is the dimension of β.     

0-1多项式规划问题的SDP松弛方法(英)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.     

缺失数据下EV模型的调整最小二乘估计

该文考虑协变量缺失时的多元线性EV模型参数的估计, 其中协变量的缺失机制是Rubin(1976)提出的随机缺失(MAR). 利用加权调整最小二乘方法给出参数估计, 证明了估计的相合性和渐近正态性. 数值模拟结果表明所给的估计性态良好.     

Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs

Probabilistically constrained quadratic programming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation.     

Capturing the multivariate extremal index: bounds and interconnections

The multivariate extremal index function is a direction specific extension of the well-known univariate extremal index. Since statistical inference on this function is difficult it is desirable to have a broad characterization of its attributes. We extend the set of common properties of the multivariate extremal index function and derive sharp bounds for the entire function given only marginal dependence. Our results correspond to certain restrictions on the two dependence functions defining the multivariate extremal index, which are opposed to Smith and Weissman’s (1996) conjecture on arbitrary dependence functions. We show further how another popular dependence measure, the extremal coefficient, is closely related to the multivariate extremal index. Thus, given the value of the former it turns out that the above bounds may be improved substantially. Conversely, we specify improved bounds for the extremal coefficient itself that capitalize on marginal dependence, thereby approximating two views of dependence that have frequently been treated separately. Our results are completed with example processes.      

Functional equations for local normal zeta functions of nilpotent groups

We give explicit formulae for the local normal zeta functions of torsion-free, class-2-nilpotent groups, subject to conditions on the associated Pfaffian hypersurface which are generically satisfied by groups with small centre and sufficiently large abelianization. We show how the functional equations of two types of zeta functions – the Weil zeta function associated to an algebraic variety and zeta functions of algebraic groups introduced by Igusa – match up to give a functional equation for local normal zeta functions of groups. We also give explicit formulae and derive functional equations for an infinite family of class-2-nilpotent groups known as Grenham groups, confirming conjectures of du Sautoy.Received: September 2003 Revision: February 2004with Appendix by A. Beauville     

On using influence functions for testing multivariate normality

Changes in the joint distribution of influence functions for the mean vector and the covariance matrix are examined when the true probability distribution is contaminated. In particular, the formulas for influence functions of the first and second moments with respect to the above joint distribution are obtained and used to derive reasonable test statistics for multivariate normality. The formulas are extended by using the joint distribution of score functions for population parameters. An application of the extended formulas to the usual linear regression analysis leads to a measure of multivariate skewness which can be used to reduce the effect of non-normality of the response variable. Also, some relationship between the extended formulas and goodness-of-fit statistics is discussed and used to derive test statistics for multivariate normality.     

General projection-pursuit estimators for the common principal components model: influence functions and Monte Carlo study

The common principal components (CPC) model for several groups of multivariate observations assumes equal principal axes but possibly different variances along these axes among the groups. Under a CPCs model, generalized projection-pursuit estimators are defined by using score functions on the dispersion measure considered. Their partial influence functions are obtained and asymptotic variances are derived from them. When the score function is taken equal to the logarithm, it is shown that, under a proportionality model, the eigenvector estimators are optimal in the sense of minimizing the asymptotic variance of the eigenvectors, for a given scale measure.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

多元线性模型中回归系数的线性可容许估计

基于Zellner的平衡损失的思想,本文提出了矩阵形式的平衡损失函数,并在该损失函数下讨论了多元回归系数线性估计的可容许性.给出了六种不同形式的可容许定义,证明了这六种容许性在齐次和非齐次线性估计类中是一致的,且得到了其共同的可容许估计的充要条件.     

Functional-coefficient partially linear regression model

In this paper, the functional-coefficient partially linear regression (FCPLR) model is proposed by combining nonparametric and functional-coefficient regression (FCR) model. It includes the FCR model and the nonparametric regression (NPR) model as its special cases. It is also a generalization of the partially linear regression (PLR) model obtained by replacing the parameters in the PLR model with some functions of the covariates. The local linear technique and the integrated method are employed to give initial estimators of all functions in the FCPLR model. These initial estimators are asymptotically normal. The initial estimator of the constant part function shares the same bias as the local linear estimator of this function in the univariate nonparametric model, but the variance of the former is bigger than that of the latter. Similarly, initial estimators of every coefficient function share the same bias as the local linear estimates in the univariate FCR model, but the variance of the former is bigger than that of the latter. To decrease the variance of the initial estimates, a one-step back-fitting technique is used to obtain the improved estimators of all functions. The improved estimator of the constant part function has the same asymptotic normality property as the local linear nonparametric regression for univariate data. The improved estimators of the coefficient functions have the same asymptotic normality properties as the local linear estimates in FCR model. The bandwidths and the smoothing variables are selected by a data-driven method. Both simulated and real data examples related to nonlinear time series modeling are used to illustrate the applications of the FCPLR model.