Towards theory of generic Principal Component Analysis

In this paper, we consider a technique called the generic Principal Component Analysis (PCA) which is based on an extension and rigorous justification of the standard PCA. The generic PCA is treated as the best weighted linear estimator of a given rank under the condition that the associated covariance matrix is singular. As a result, the generic PCA is constructed in terms of the pseudo-inverse matrices that imply a development of the special technique. In particular, we give a solution of the new low-rank matrix approximation problem that provides a basis for the generic PCA. Theoretical aspects of the generic PCA are carefully studied.     

Method of Best Successive Approximations for Nonlinear Operators

We present a new approach to the approximation of nonlinear operators in probability spaces. The approach is based on a combination of the specific iterative procedure and the best approximation problem solution with a quadratic approximant. We show that the combination of these new techniques allow us to build a computationally efficient and flexible method. The algorithm of the method and its application to the optimal filtering of stochastic signals are given.     

Analysis of a chance-constrained new product risk model with multiple customer classes

We consider the non-convex problem of minimizing a linear deterministic cost objective subject to a probabilistic requirement on a nonlinear multivariate stochastic expression attaining, or exceeding a given threshold. The stochastic expression represents the output of a noisy system featuring the product of mutually-independent, uniform random parameters each raised to a linear function of one of the decision vector’s constituent variables. We prove a connection to (i) the probability measure on the superposition of a finite collection of uncorrelated exponential random variables, and (ii) an entropy-like affine function. Then, we determine special cases for which the optimal solution exists in closed-form, or is accessible via sequential linear programming. These special cases inspire the design of a gradient-based heuristic procedure that guarantees a feasible solution for instances failing to meet any of the special case conditions. The application motivating our study is a consumer goods firm seeking to cost-effectively manage a certain aspect of its new product risk. We test our heuristic on a real problem and compare its overall performance to that of an asymptotically optimal Monte-Carlo-based method called sample average approximation. Numerical experimentation on synthetic problem instances sheds light on the interplay between the optimal cost and various parameters including the probabilistic requirement and the required threshold.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

Optimal Recursive Estimation of Raw Data

We present a new approach to the optimal estimation of random vectors. The approach is based on a combination of a specific iterative procedure and the solution of a best approximation problem with a polynomial approximant. We show that the combination of these new techniques allow us to build a computationally effective and flexible estimator. The strict justification of the proposed technique is provided. This work was supported by the Australian Research Council under the ARC Large Grant Scheme.     

Rational approximation of vertical segments

In many applications, observations are prone to imprecise measurements. When constructing a model based on such data, an approximation rather than an interpolation approach is needed. Very often a least squares approximation is used. Here we follow a different approach. A natural way for dealing with uncertainty in the data is by means of an uncertainty interval. We assume that the uncertainty in the independent variables is negligible and that for each observation an uncertainty interval can be given which contains the (unknown) exact value. To approximate such data we look for functions which intersect all uncertainty intervals. In the past this problem has been studied for polynomials, or more generally for functions which are linear in the unknown coefficients. Here we study the problem for a particular class of functions which are nonlinear in the unknown coefficients, namely rational functions. We show how to reduce the problem to a quadratic programming problem with a strictly convex objective function, yielding a unique rational function which intersects all uncertainty intervals and satisfies some additional properties. Compared to rational least squares approximation which reduces to a nonlinear optimization problem where the objective function may have many local minima, this makes the new approach attractive.     

Asymptotic theory of simultaneous estimation of Poisson means

The Poisson distribution is often a good approximation to the underlying sampling distribution and is central to the study of categorical data. In this paper, we propose a new unified approach to an investigation of point properties of simultaneous estimations of Poisson population parameters with general quadratic loss functions. The main accent is made on the shrinkage estimation. We build a series of estimators that could be represented as a convex combination of linear statistics such as maximum likelihood estimator (benchmark estimator), restricted estimator, composite estimator, preliminary test estimator, shrinkage estimator, positive rule shrinkage estimator (James-Stein type estimator). All these estimators are represented in a general integrated estimation approach, which allows us to unify our investigation and order them with respect to the risk. A simulation study with numerical and graphical results is conducted to illustrate the properties of the investigated estimators.     

Error estimation in nonlinear optimization

Methods are developed and analyzed for estimating the distance to a local minimizer of a nonlinear programming problem. One estimate, based on the solution of a constrained convex quadratic program, can be used when strict complementary slackness and the second-order sufficient optimality conditions hold. A second estimate, based on the solution of an unconstrained nonconvex, nonsmooth optimization problem, is valid even when strict complementary slackness is violated. Both estimates are valid in a neighborhood of a local minimizer. An active set algorithm is developed for computing a stationary point of the nonsmooth error estimator. Each iteration of the algorithm requires the solution of a symmetric, positive semidefinite linear system, followed by a line search. Convergence is achieved in a finite number of iterations. The error bounds are based on stability properties for nonlinear programs. The theory is illustrated by some numerical examples.     

A posteriori estimators for nonlinear elliptic partial differential equations

Many works have reported results concerning the mathematical analysis of the performance of a posteriori error estimators for the approximation error of finite element discrete solutions to linear elliptic partial differential equations. For each estimator there is a set of restrictions defined in such a way that the analysis of its performance is made possible. Usually, the available estimators may be classified into two types, i.e., the implicit estimators (based on the solution of a local problem) and the explicit estimators (based on some suitable norm of the residual in a dual space). Regarding the performance, an estimator is called asymptotically exact if it is a higher-order perturbation of a norm of the exact error. Nowadays, one may say that there is a larger understanding about the behavior of estimators for linear problems than for nonlinear problems. The situation is even worse when the nonlinearities involve the highest derivatives occurring in the PDE being considered (strongly nonlinear PDEs). In this work we establish conditions under which those estimators, originally developed for linear problems, may be used for strongly nonlinear problems, and how that could be done. We also show that, under some suitable hypothesis, the estimators will be asymptotically exact, whenever they are asymptotically exact for linear problems. Those results allow anyone to use the knowledge about estimators developed for linear problems in order to build new reliable and robust estimators for nonlinear problems.     

Dirac delta methods for Helmholtz transmission problems

In this paper we use a boundary integral method with single layer potentials to solve a class of Helmholtz transmission problems in the plane. We propose and analyze a novel and very simple quadrature method to solve numerically the equivalent system of integral equations which provides an approximation of the solution of the original problem with linear convergence (quadratic in some special cases). Furthermore, we also investigate a modified quadrature approximation based on the ideas of qualocation methods. This new scheme is again extremely simple to implement and has order three in weak norms.      

Positive shrinkage, improved pretest and absolute penalty estimators in partially linear models

Shrinkage estimators of a partially linear regression parameter vector are constructed by shrinking estimators in the direction of the estimate which is appropriate when the regression parameters are restricted to a linear subspace. We investigate the asymptotic properties of positive Stein-type and improved pretest semiparametric estimators under quadratic loss. Under an asymptotic distributional quadratic risk criterion, their relative dominance picture is explored analytically. It is shown that positive Stein-type semiparametric estimators perform better than the usual Stein-type and least square semiparametric estimators and that an improved pretest semiparametric estimator is superior to the usual pretest semiparametric estimator. We also consider an absolute penalty type estimator for partially linear models and give a Monte Carlo simulation comparisons of positive shrinkage, improved pretest and the absolute penalty type estimators. The comparison shows that the shrinkage method performs better than the absolute penalty type estimation method when the dimension of the parameter space is much larger than that of the linear subspace.     

Quadratic programming for portfolio optimization

Portfolio optimization is a procedure for generating a portfolio composition which yields the highest return for a given level of risk or a minimum risk for given level of return. The problem can be formulated as a quadratic programming problem. We shall present a new and efficient optimization procedure taking advantage of the special structure of the portfolio selection problem. An example of its application to the traditional mean-variance method will be shown. Formulation of the procedure shows that the solution of the problem is vector intensive and fits well with the advanced architecture of recent computers, namely the vector processor.     

Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

A new approach for solving a class of nonlinear integro-differential equations

In this paper, a new technique for solving a class of quadratic integral and integro-differential equations is introduced. The main advantage of this technique is that it can replace the nonlinear problem by an equivalent linear one or by another simpler nonlinear one. The convergence of the series solution is proved. Convergence analysis is reliable enough to estimate the maximum absolute truncated error of the series solution. Some numerical examples are introduced to verify the efficiency of the new technique.     

Minimax adjustment technique in a parameter restricted linear model

We consider an approach yielding a minimax estimator in the linear regression model with a priori information on the parameter vector, e.g., ellipsoidal restrictions. This estimator is computed directly from the loss function and can be motivated by the general Pitman nearness criterion. It turns out that this approach coincides with the projection estimator which is obtained by projecting an initial arbitrary estimate on the subset defined by the restrictions.     

Wavelet regression estimation in nonparametric mixed effect models

We show that a nonparametric estimator of a regression function, obtained as solution of a specific regularization problem is the best linear unbiased predictor in some nonparametric mixed effect model. Since this estimator is intractable from a numerical point of view, we propose a tight approximation of it easy and fast to implement. This second estimator achieves the usual optimal rate of convergence of the mean integrated squared error over a Sobolev class both for equispaced and nonequispaced design. Numerical experiments are presented both on simulated and ERP real data.     

Proximal minimizations with D-functions and the massively parallel solution of linear network programs

This paper discusses the massively parallel solution of linear network programs. It integrates the general algorithmic framework of proximal minimization with D-functions (PMD) with primal-dual row-action algorithms. Three alternative algorithmic schemes are studied: quadratic proximal point, entropic proximal point, and least 2-norm perturbations. Each is solving a linear network problem by solving a sequence of nonlinear approximations. The nonlinear subproblems decompose for massively parallel computing. The three algorithms are implemented on a Connection Machine CM-2 with up to 32K processing elements, and problems with up to 16 million variables are solved. A comparison of the three algorithms establishes their relative efficiency. Numerical experiments also establish the best internal tactics which can be used when implementing proximal minimization algorithms. Finally, the new algorithms are compared with an implementation of the network simplex algorithm executing on a CRAY Y-MP vector supercomputer.     

Linearized Models with Constraints of Type I

In nonlinear regression models with constraints a linearization of the model leads to a bias in estimators of parameters of the mean value of the observation vector. Some criteria how to recognize whether a linearization is possible is developed. In the case that they are not satisfied, it is necessary to decide whether some quadratic corrections can make the estimator better. The aim of the paper is to contribute to the solution of the problem.