Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method

This paper analyzes the introduction of multiple central cuts in a conic formulation of the analytic center cutting plane method (in short ACCPM). This work extends earlier work on the homogeneous ACCPM, and parallels the analysis of the multiple cut process in the standard ACCPM. The main issue is the calculation of a direction that restores feasibility after introducing p new cutting planes at the query point. We prove that the new analytic center can be recovered in O(p log p) damped Newton iterations, where is a parameter depending of the data. We also present two special cases where the complexity can be decreased to O (p log p). Finally, we show that the number of calls to the oracle is the same as in the single cut case, up to a factor .     

A Cutting Plane Method for Solving Quasimonotone Variational Inequalities

We present an iterative algorithm for solving variational inequalities under the weakest monotonicity condition proposed so far. The method relies on a new cutting plane and on analytic centers.     

A Long-Step, Cutting Plane Algorithm for Linear and Convex Programming

A cutting plane method for linear programming is described. This method is an extension of Atkinson and Vaidya's algorithm, and uses the central trajectory. The logarithmic barrier function is used explicitly, motivated partly by the successful implementation of such algorithms. This makes it possible to maintain primal and dual iterates, thus allowing termination at will, instead of having to solve to completion. This algorithm has the same complexity (O(nL ²) iterations) as Atkinson and Vaidya's algorithm, but improves upon it in that it is a long-step version, while theirs is a short-step one in some sense. For this reason, this algorithm is computationally much more promising as well. This algorithm can be of use in solving combinatorial optimization problems with large numbers of constraints, such as the Traveling Salesman Problem.     

On a Primal-Dual Analytic Center Cutting Plane Method for Variational Inequalities

We present an algorithm for variational inequalities VI( , Y) that uses a primal-dual version of the Analytic Center Cutting Plane Method. The point-to-set mapping is assumed to be monotone, or pseudomonotone. Each computation of a new analytic center requires at most four Newton iterations, in theory, and in practice one or sometimes two. Linear equalities that may be included in the definition of the set Y are taken explicitly into account.We report numerical experiments on several well—known variational inequality problems as well as on one where the functional results from the solution of large subproblems. The method is robust and competitive with algorithms which use the same information as this one.     

The Application of Preprocessing and Cutting Plane Techniques for a Class of Production Planning Problems

This paper investigates properties of integer programming models for a class of production planning problems. The models are developed within a decision support system to advise a sales team of the products on which to focus their efforts in gaining new orders in the short term. The products generally require processing on several manufacturing cells and involve precedence relationships. The cells are already (partially) committed with products for stock and to satisfy existing orders and therefore only the residual capacities of each cell in each time period of the planning horizon are considered. The determination of production recommendations to the sales team that make use of residual capacities is a nontrivial optimization problem. Solving such models is computationally demanding and techniques for speeding up solution times are highly desirable. An integer programming model is developed and various preprocessing techniques are investigated and evaluated. In addition, a number of cutting plane approaches have been applied. The performance of these approaches which are both general and application specific is examined.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

带一个插值点的回归模型的参数分析

一般的回归模型中认为所有的数据点的重要程度是相同的,但有的实际问题中可能由于种种原因,其中有某个数据特别重要,针对这种情况,提出一种带一个插值点的回归模型,并得到这种回归模型三个参数的最大似然估计.     

A Hybrid Algorithm for the Non-Guillotine Cutting Problem

In this article, a meta-heuristic method to solve the non-guillotine cutting stock problem is proposed. The method is based on a combination between the basic principles of the constructive and evolutive methods. With an adequate management of the parameters involved, the method allows regulation of the solution quality to computational effort relationship. This method is applied to a particular case of cutting problems, with which the computational behaviors is evaluated. In fact, 1000 instances of the problem have been classified according to their combinatorial degree and then the efficiency and robustness of the method have been tested. The final results conclude that the proposed method generates an average error close to 2.18% with respect to optimal solutions. It has also been verified that the method yields solutions for all of the instances examined; something that has not been achieved with an exact constructive method, which was also implemented. Comparison of the running times demonstrates the superiority of the proposed method as compared with the exact method.     

求解标准二次优化问题的割平面算法

标准的二次优化问题是NP-hard问题,把该问题转化为半不定的线性规划问题,且提出了一个线性规划的割平面算法来求解这个半不定的线性规划问题,并给出了该算法的收敛性证明.     

A Cutting Plane Algorithm for Linear Reverse Convex Programs

In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.     

参数θ的函数f(θ)的极大似然估计

在微积分范围内给出了参数θ的函数f(θ)的极大似然估计.     

Efficient Algorithm for Computing Maximum Likelihood Estimates in Linear Transformation Models

Linear transformation models, which have been extensively studied in survival analysis, include the two special cases: the proportional hazards model and the proportional odds model. Nonparametric maximum likelihood estimation is usually used to derive the efficient estimators. However, due to the large number of nuisance parameters, calculation of the nonparametric maximum likelihood estimator is difficult in practice, except for the proportional hazards model. We propose an efficient algorithm for computing the maximum likelihood estimates, where the dimensionality of the parameter space is dramatically reduced so that only a finite number of equations need to be solved. Moreover, the asymptotic variance is automatically estimated in the computing procedure. Extensive simulation studies indicate that the proposed algorithm works very well for linear transformation models. A real example is presented for an illustration of the new methodology.     

交替迭代最大似然估计量的偏倚校正

In this paper, we give a definition of the alternating iterative maximum likelihood estimator (AIMLE) which is a biased estimator. Furthermore we adjust the AIMLE to result in asymptotically unbiased and consistent estimators by using a bootstrap iterative bias correction method as in Kuk (1995). Two examples and simulation results reported illustrate the performance of the bias correction for AIMLE.     

一种求解线性二层规划的割平面方法

以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的.     

Approximate Maximum Likelihood Estimation of Circle Parameters

The estimation of a circles centre and radius from a set of noisy measurements of its circumference has many applications. It is a problem of fitting a circle to the measurements and the fit can be in algebraic or geometric distances. The former gives linear equations, while the latter yields nonlinear equations. Starting from estimation theory, this paper first proves that the maximum likelihood (ML), i.e., the optimal estimation of the circle parameters, is equivalent to the minimization of the geometric distances. It then derives a pseudolinear set of ML equations whose coefficients are functions of the unknowns. An approximate ML algorithm updates the coefficients from the previous solution and selects the solution that gives the minimum cost. Simulation results show that the ML algorithm attains the Cramer-Rao lower bound (CRLB) for arc sizes as small as 90°. For arc sizes of 15° and 5° the ML algorithm errors are slightly above the CRLB, but lower than those of other linear estimators.Communicated by L. C. W. Dixon     

A Functional EM Algorithm for Mixing Density Estimation via Nonparametric Penalized Likelihood Maximization

When the true mixing density is known to be continuous, the maximum likelihood estimate of the mixing density does not provide a satisfying answer due to its degeneracy. Estimation of mixing densities is a well-known ill-posed indirect problem. In this article, we propose to estimate the mixing density by maximizing a penalized likelihood and call the resulting estimate the nonparametric maximum penalized likelihood estimate (NPMPLE). Using theory and methods from the calculus of variations and differential equations, a new functional EM algorithm is derived for computing the NPMPLE of the mixing density. In the algorithm, maximizers in M-steps are found by solving an ordinary differential equation with boundary conditions numerically. Simulation studies show the algorithm outperforms other existing methods such as the popular EMS algorithm. Some theoretical properties of the NPMPLE and the algorithm are also discussed. Computer code used in this article is available online.     

A Cautionary Note on Likelihood Ratio Tests in Mixture Models

We show that iterative methods for maximizing the likelihood in a mixture of exponentials model depend strongly on their particular implementation. Different starting strategies and stopping rules yield completely different estimators of the parameters. This is demonstrated for the likelihood ratio test of homogeneity against two-component exponential mixtures, when the test statistic is calculated by the EM algorithm.     

Maximum Likelihood Estimation of Isotonic Normal Means with Unknown Variances

To analyze the isotonic regression problem for normal means, it is usual to assume that all variances are known or unknown but equal. This paper then studies this problem in the case that there are no conditions imposed on the variances. Suppose that we have data drawn fromkindependent normal populations with unknown meansμ_i's and unknown variancesσ²_i's, in which the means are restricted by a given partial ordering. This paper discusses some properties of the maximum likelihood estimates ofμ_i's andσ²_i's under the restriction and proposes an algorithm for obtaining the estimates.     

有关顺序统计量的极大似然估计

讨论了一类参数空间受样本限制的极大似然估计问题.分析了随机变量分布的非零区域与似然函数定义域的对应关系,提出如果分布的非零区域受参数限制,则无论似然方程是否可解,参数的极大似然估计必然与样本顺序统计量X_((n))或X_((1))有关,并具体分析了似然估计一定等于、一定不等于和可能等于顺序统计量X_((n))(X_((1)))的三种情形,并给出了相应的判别条件.最后分析得出在第三种判别条件之下,似然估计是否取值于x_((n))(x_((1)))视具体的样本观测值决定.     

一类零膨胀广义线性模型极大似然估计的相合性与渐近正态性

讨论了响应变量为单参数指数族且在零点处膨胀的广义线性模型的大样本性质,对其参数进行了极大似然估计,给出了一些正则条件.基于所提出的正则条件,证明了模型参数极大似然估计的相合性与渐近正态性.