An improved general Phase-I method in linear programming

In a recent paper on general Phase-I methods in linear programming a procedure was suggested that minimizes the amount of infeasibility allowing the number of infeasibilities to increase. Though the procedure improves the overall performance of the Phase-I Simplex method by reducing the number of pivot steps, its main drawback is the extra computational effort required. In this paper it will be shown theoretically and computationally that in most cases this computational effort can be reduced significantly.     

A simple direct cosine simplex algorithm

Linear programming (LP) is the core model of constrained optimization. The Simplex method (Simplex in short) has been proven in practice to perform very well in small- or medium-sized LP problems. A new algorithm called the direct cosine Simplex algorithm (DCA) is presented here to improve upon Simplex and to solve LP problems. The proposed DCA implements a specific cosine criterion to choose the entering variable instead of the traditional most negative rule used in Simplex. Three examples are given to illustrate the implementation of the proposed DCA to improve Simplex and to serve as the optimization tool. The utility of the proposed approach is evident from the extensive computational results on test problems adapted from NETLIB. DCA reduced the number of iterations of Simplex in most cases in our computational experiment. Preliminary results for medium-sized problems are encouraging.     

Optimum beam design using finite elements

The optimum structural design of beams for several benchmark problems are considered. The penalty function method is employed to impose the inequality constraints and the Newton-Raphson algorithm has been used to solve the first-order necessary condition for optimality. The finite element procedure shows to be very effective in converging to the exact optimum solution.     

Parameter estimation of an autoregressive moving average model

Summary An estimator of the set of parameters of an autoregressive moving average model is obtained by applying the method of least squares to the log smoothed periodogram. It is shown to be asymptotically efficient and normally distributed under the normality and the circular condition of the generating process. A computational procedure is constructed by the Newton-Raphson method. Several computer simulation results are given to demonstrate the usefulness of the present procedure.     

成形过程数值模拟的非增量时一空算法*

本文针对计及几何、材料、接触摩擦等耦合作用的高度非线性的加工成形过程数值模拟和计算分析工作,建议了非增量时-空求解算法。本文的非增量算法,系在整个时间域和空间域上迭代求解,与常见的Newton-Raphson算法明显不同。本文所附算例,进一步说明了本算法的正确性和可行性。     

Simulation of Jet Flows in Ideal Fluids by Variable Finite Elements

A free-boundary problem involved in computation of the shapeof a jet of an ideal fluid exiting through an orifice is formulatedas finding a stationary point of a certain functional definedon a variable domain. The stationary point of the functionaldiscretized in terms of linear finite elements is then locatednumerically by using the Newton-Raphson procedure. This numericalapproach is much faster than the previous attempts; it can accuratelyreproduce the exact results known for planar jet flows whenthe orifice is an infinite slit; and it can easily be appliedto the computation of axisymmetric jets.     

On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

Weighted Overlap Dominance – A procedure for interactive selection on multidimensional interval data

We present an outranking procedure that supports selection of alternatives represented by multiple attributes with interval valued data. The procedure is interactive in the sense that the decision maker directs the search for preferred alternatives by providing weights of the different attributes as well as parameters related to risk attitude and weighted dominance. The outranking relation builds on pairwise comparisons between optimistic and pessimistic weighted values as well as weighted dominance relations supported by volume based measures. The suggested procedure is referred to as the Weighted Overlap Dominance procedure (WOD).     

Three nearly scaling-invariant versions of an exterior point algorithm for linear programming

In this paper, we describe three versions of a primal exterior point Simplex type algorithm for solving linear programming problems. Also, these algorithms are not affected mainly by scaling techniques. We compare their practical effectiveness versus the revised primal Simplex algorithm (our implementation) and the MATLAB’s implementations of Simplex and Interior Point Method. A computational study on randomly generated sparse linear programs is presented to establish the practical value of the proposed versions. The results are very encouraging and verify the superiority of the exterior point versions over the other algorithms either using scaling techniques or not.     

偏t正态数据下混合线性联合位置与尺度模型的参数估计

偏t正态分布是分析尖峰,厚尾数据的重要统计工具之一.研究提出了偏t正态数据下混合线性联合位置与尺度模型,通过EM算法和Newton-Raphson方法研究了该模型参数的极大似然估计.并通过随机模拟试验验证了所提出方法的有效性.最后,结合实际数据验证了该模型和方法具有实用性和可行性.     

Galerkin's procedure,quasilinearization, and nonlinear boundary-value problems

Among the popular and successful techniques for solving boundary-value problems for nonlinear, ordinary differential equations (ODE) are quasilinearization and the Galerkin procedure. In this note, it is demonstrated that utilizing the Galerkin criterion followed by the Newton-Raphson scheme results in the same iteration process as that obtained by applying quasilinearization to the nonlinear ODE and then the Galerkin criterion to each linear ODE in the resulting sequence. This equivalence holds for only the Galerkin procedure in the broad class of weighted-residual methods.This work was supported in part by the National Science Foundation, Grant No. GJ-1075.     

Mixed algorithm in searches of mechanical system steady-state conditions for low precision of the state estimation

This paper focuses on algorithms of numerical solution of nonlinear system of equations. Analytical formulas of their nonlinear functions my not be calculated with the requested precision. Additionally, analytical formulas of the partial derivatives are unknown. They are evaluated numerically by finite differences method. It effects in erroneous estimations. Described situation is critical when steady state conditions are searched for mechanical systems. According to the precision of the numerical procedures, their dynamic equations are known with limited precision. This same stands for the system's final conditions (obtained by a numerical integration). It the actual case, the classical Newton-Raphson algorithm can be ineffective. As an alternative, a mixed search algorithm is proposed in the paper. By contrast to the classical algorithm, within the search direction defined by the Newton-Raphson indication, (potentially erroneous) a local minimum is searched. Both the algorithms are tested on analytical functions; on randomized functions and on a model of a mechanical system. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

比例优势模型在多结局区间截断数据上的应用

探索比例优势模型在临床医学中常见的多结局区间截断数据中的应用.用条件的逻辑回归方法避免讨厌参数的估计,用牛顿-拉普森算法估计回归系数,用＂夹心方差＂估计量作为参数方差的估计.通过随机模型检验模型应用的有效性.     

Monotonicity of quadratic-approximation algorithms

It is desirable that a numerical maximization algorithm monotonically increase its objective function for the sake of its stability of convergence. It is here shown how one can adjust the Newton-Raphson procedure to attain monotonicity by the use of simple bounds on the curvature of the objective function. The fundamental tool in the analysis is the geometric insight one gains by interpreting quadratic-approximation algorithms as a form of area approximation. The statistical examples discussed include maximum likelihood estimation in mixture models, logistic regression and Cox's proportional hazards regression.The second author's research was partially supported by the National Science Foundation under Grant DMS-8402735.     

A dual strategy for solving the linear programming relaxation of a driver scheduling system

A Mathematical Programming model of a driver scheduling system is described. This consists of set covering and partitioning constraints, possibly user-supplied side constraints, and two pre-emptively ordered objectives. The previous solution strategy addressed the two objectives using separate Primal Simplex optimisations; a new strategy uses a single weighted objective function and a Dual Simplex algorithm initiated by a specially developed heuristic. Computational results are reported.     

A σ-constant acceleration method in nonlinear analysis

Accelerated iterative nonlinear analysis is achieved by primarily requiring stress convergence and enforcing displacement equilibrium through the use of pseudobalancing forces after the stress convergence at the load stage. Incremental perfect-plasticity modelling of material loading characteristics is made, and this enables stresses on intermediate-yield surfaces to be held constant on such surfaces within iterations at any given load level. The procedure accelerates stress convergence in a Newton-Raphson solution modelled by the use of the initial stiffness. Emphasis has been placed on reinforced concrete, despite the generality of the formulation. An example of a beam and slab is analysed.     

The Complex Interior-Boundary method for linear and nonlinear programming with linear constraints

In this paper we develop the Complex method; an algorithm for solving linear programming (LP) problems with interior search directions. The Complex Interior-Boundary method (as the name suggests) moves in the interior of the feasible region from one boundary point to another of the feasible region bypassing several extreme points at a time. These directions of movement are guaranteed to improve the objective function. As a result, the Complex method aims to reach the optimal point faster than the Simplex method on large LP programs. The method also extends to nonlinear programming (NLP) with linear constraints as compared to the generalized-reduced gradient.The Complex method is based on a pivoting operation which is computationally efficient operation compared to some interior-point methods. In addition, our algorithm offers more flexibility in choosing the search direction than other pivoting methods (such as reduced gradient methods). The interior direction of movement aims at reducing the number of iterations and running time to obtain the optimal solution of the LP problem compared to the Simplex method. Furthermore, this method is advantageous to Simplex and other convex programs in regard to starting at a Basic Feasible Solution (BFS); i.e. the method has the ability to start at any given feasible solution.Preliminary testing shows that the reduction in the computational effort is promising compared to the Simplex method.     

A priori reduction method for solving the two-dimensional Burgers’ equations

The two-dimensional Burgers’ equations are solved here using the A Priori Reduction method. This method is based on an iterative procedure which consists in building a basis for the solution where at each iteration the basis is improved. The method is called a priori because it does not need any prior knowledge of the solution, which is not the case if the standard Karhunen-Loéve decomposition is used. The accuracy of the APR method is compared with the standard Newton-Raphson scheme and with results from the literature. The APR basis is also compared with the Karhunen-Loéve basis.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

A numerically stable form of the simplex algorithm

Standard implementations of the Simplex method have been shown to be subject to computational instabilities, which in practice often result in failure to achieve a solution to a basically well-determined problem. A numerically stable form of the Simplex method is presented with storage requirements and computational efficiency comparable with those of the standard form. The method admits non-Simplex steps and this feature enables it to be readily generalized to quadratic and nonlinear programming. Although the principal concern in this paper is not with constraints having a large number of zero elements, all necessary modification formulae are given for the extension to these cases.