Superlinear convergence of infeasible-interior-point methods for linear programming

At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 + where can be arbitrarily close to one.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Corresponding author.     

Characterization of rankings generated by linear discriminant analysis

Pairwise linear discriminant analysis can be regarded as a process to generate rankings of the populations. But in general, not all rankings are generated. We give a characterization of generated rankings. We also derive some basic properties of this model.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

New trajectory-following polynomial-time algorithm for linear programming problems

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.The author is indebted to J. Bisschop, P. C. J. M. Geven, J. H. Van Lint, J. Ponstein, and J. P. Vial for their remarks on an earlier version of this paper.     

Influence of observations on the misclassification probability in quadratic discriminant analysis

In this paper it is studied how observations in the training sample affect the misclassification probability of a quadratic discriminant rule. An approach based on partial influence functions is followed. It allows to quantify the effect of observations in the training sample on the performance of the associated classification rule. Focus is on the effect of outliers on the misclassification rate, merely than on the estimates of the parameters of the quadratic discriminant rule. The expression for the partial influence function is then used to construct a diagnostic tool for detecting influential observations. Applications on real data sets are provided.     

高阶线性微分方程解的二阶导数的不动点

研究了以整函数为系数的高阶线性微分方程解的二阶导数的不动点,得到的两个结果推广了一些相关结论.     

Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

To solve linear programming problems by interior point methods an approximately centered interior point has to be known. Such a point can be found by an algorithmic approach – a so-called phase 1 algorithm or centering algorithm. For random linear programming problems distributed according to the rotation symmetry model, especially with normal distribution, we present probabilistic results on the quality of the origin as starting point and the average number of steps of a centering algorithm.     

Identifying the anchor points in DEA using sensitivity analysis in linear programming

In this paper, the anchor points in DEA, as an important subset of the set of extreme efficient points of the production possibility set (PPS), are studied. A basic definition, utilizing the multiplier DEA models, is given. Then, two theorems are proved which provide necessary and sufficient conditions for characterization of these points. The main results of the paper lead to a new interesting connection between DEA and sensitivity analysis in linear programming theory. By utilizing the established theoretical results, a successful procedure for identification of the anchor points is presented.     

Global convergence of the affine scaling methods for degenerate linear programming problems

In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.This paper was presented at the International Symposium Interior Point Methods for Linear Programming: Theory and Practice, held on January 18–19, 1990, at the Europa Hotel, Scheveningen, the Netherlands.     

Spectral properties of Jacobi matrices by asymptotic analysis

We consider two classes of Jacobi matrix operators in l² with zero diagonals and with weights of the form n^α+c_n for 0<α1 or of the form n^α+c_nn^α−1 for α>1, where {c_n} is periodic. We study spectral properties of these operators (especially for even periods), and we find asymptotics of some of their generalized eigensolutions. This analysis is based on some discrete versions of the Levinson theorem, which are also proved in the paper and may be of independent interest.     

A primal-dual interior-point method for linear programming based on a weighted barrier function

One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391.     

Degeneracy in interior point methods for linear programming: a survey

The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming.We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.Partially supported by a research fund of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.     

Approximating Promethee II’s net flow scores by piecewise linear value functions

Promethee II is a prominent method for multi-criteria decision aid (MCDA) that builds a complete ranking on a set of potential actions by assigning each of them a so-called net flow score. However, to calculate these scores, each pair of actions has to be compared, causing the computational load to increase quadratically with the number of actions, eventually leading to prohibitive execution times for large decision problems. For some problems, however, a trade-off between the ranking’s accuracy and the required evaluation time may be acceptable. Therefore, we propose a piecewise linear model that approximates Promethee II’s net flow scores and reduces the computational complexity (with respect to the number of actions) from quadratic to linear at the cost of some wrongly ranked actions. Simulations on artificial problem instances allow us to quantify this time/quality trade-off and to provide probabilistic bounds on the problem size above which our model satisfyingly approximates Promethee II’s rankings. They show, for instance, that for decision problems of 10,000 actions evaluated on 7 criteria, the Pearson correlation coefficient between the original scores and our approximation is of at least 0.97. When put in balance with computation times that are more than 7000 times faster than for the Promethee II model, the proposed approximation model represents an interesting alternative for large problem instances.     

New results on input-to-state convergence for recurrent neural networks with variable inputs

In this paper, we study a class of recurrent neural networks (RNNs) arising from optimization problems. By constructing appropriate Lyapunov functions, we prove two new results on input-to-state convergence of RNNs with variable inputs. Numerical simulations are also given to demonstrate the convergence of the solutions.     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

New decomposition and convexification algorithm for nonconvex large-scale primal-dual optimization

A new algorithm for solving nonconvex, equality-constrained optimization problems with separable structures is proposed in the present paper. A new augmented Lagrangian function is derived, and an iterative method is presented. The new proposed Lagrangian function preserves separability when the original problem is separable, and the property of linear convergence of the new algorithm is also presented. Unlike earlier algorithms for nonconvex decomposition, the convergence ratio for this method can be made arbitrarily small. Furthermore, it is feasible to extend this method to algorithms suited for inequality-constrained optimization problems. An example is included to illustrate the method.This research was supported in part by the National Science Foundation under NSF Grant No. ECS-85-06249.     

Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems

In this paper we deal with the study of the polynomial complexity and numerical implementation for a short-step primal-dual interior point algorithm for monotone linear complementarity problems LCP. The analysis is based on a new class of search directions used by the author for convex quadratic programming (CQP) [M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics 25 (1) (2006) 97-110]. Here, we show that this algorithm enjoys the best theoretical polynomial complexity namely , iteration bound. For its numerical performances some strategies are used. Finally, we have tested this algorithm on some monotone linear complementarity problems.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.