A weighted least squaes study of robustness in interior point linear programming

This paper studies the robustness of interior point linear programming algorthims with respect to initial iterates that are too close to the boundary. Weighted least squares analysis is used in studying the near-boundary behavior of the affine scaling and Newton centering directions, which are often combined by interior point methods. This analysis leads to the develoment of a modified Newton centering direction exhibiting better near-boundary behavior than the two directions. Theoretical and computational results from the NETLIB test set are presented indicating that an approach which uses the modified newton direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.     

Determination of optimal vertices from feasible solutions in unimodular linear programming

In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088.     

Regularization techniques in interior point methods

Regularization techniques, i.e., modifications on the diagonal elements of the scaling matrix, are considered to be important methods in interior point implementations. So far, regularization in interior point methods has been described for linear programming problems, in which case the scaling matrix is diagonal. It was shown that by regularization, free variables can be handled in a numerically stable way by avoiding column splitting that makes the set of optimal solutions unbounded. Regularization also proved to be efficient for increasing the numerical stability of the computations during the solutions of ill-posed linear programming problems. In this paper, we study the factorization of the augmented system arising in interior point methods. In our investigation, we generalize the methods developed and used in linear programming to the case when the scaling matrix is positive semidefinite, but not diagonal. We show that regularization techniques may be applied beyond the linear programming case.     

一类非单调线性互补问题的高阶仿射尺度算法

In this paper, a new interior point algorithm-high-order atone scaling for a class of nonmonotonic linear complementary problems is developed. On the basis of idea of primal-dual affine scaling method for linear programming , the search direction of our algorithm is obtained by a linear system of equation at each step . We show that, by appropriately choosing the step size, the algorithm has polynomial time complexity. We also give the numberical results of the algorithm for two test problems.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

A primal projective interior point method for linear programming

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

具有跳跃的随机神经网络的均方稳定性

研究了一类新的具有脉冲跳跃的Hopfield神经网络系统模型,其中脉冲时刻的跳跃是由一般的随机序列所引起,通过运用Lyapunov函数方法,获取了一些新的均方稳定性结果.由于脉冲的跳跃使得不稳定的神经网络变成稳定,因而所得的结果也可以运用到其他相关领域.     

Neural Approach for Solving Several Types of Optimization Problems

Neural networks consist of highly interconnected and parallel nonlinear processing elements that are shown to be extremely effective in computation. This paper presents an architecture of recurrent neural net-works that can be used to solve several classes of optimization problems. More specifically, a modified Hopfield network is developed and its inter-nal parameters are computed explicitly using the valid-subspace technique. These parameters guarantee the convergence of the network to the equilibrium points, which represent a solution of the problem considered. The problems that can be treated by the proposed approach include combinatorial optimiza-tion problems, dynamic programming problems, and nonlinear optimization problems.Communicated by L. C. W. Dixon     

Interior point methods 25 years later

Interior point methods for optimization have been around for more than 25 years now. Their presence has shaken up the field of optimization. Interior point methods for linear and (convex) quadratic programming display several features which make them particularly attractive for very large scale optimization. Among the most impressive of them are their low-degree polynomial worst-case complexity and an unrivalled ability to deliver optimal solutions in an almost constant number of iterations which depends very little, if at all, on the problem dimension. Interior point methods are competitive when dealing with small problems of dimensions below one million constraints and variables and are beyond competition when applied to large problems of dimensions going into millions of constraints and variables.In this survey we will discuss several issues related to interior point methods including the proof of the worst-case complexity result, the reasons for their amazingly fast practical convergence and the features responsible for their ability to solve very large problems. The ever-growing sizes of optimization problems impose new requirements on optimization methods and software. In the final part of this paper we will therefore address a redesign of interior point methods to allow them to work in a matrix-free regime and to make them well-suited to solving even larger problems.     

神经网络平衡点存在唯一的充要条件

针对一类广泛的激活函数 ,利用矩阵理论 ,建立了相应的Hopfield神经网络平衡点存在唯一的充要条件 .同时 ,也给出相应的离散神经网络平衡点存在唯一的充要条件 .比较现有的文献 ,本文的结果适用范围更为广泛     

A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints

A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence. Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.     

Global exponential stability and global attractivity of impulsive Hopfield neural networks with time delays

In this paper, by means of constructing the extended impulsive delayed Halanay inequality and by Lyapunov functional methods, we analyze the global exponential stability and global attractivity of impulsive Hopfield neural networks with time delays. Some new sufficient conditions ensuring exponential stability of the unique equilibrium point of impulsive Hopfield neural networks with time delays are obtained. Those conditions are more feasible than that given in the earlier references to some extent. Some numerical examples are also discussed in this work to illustrate the advantage of the results we obtained.     

Exponential stability of reaction-diffusion high-order Markovian jump Hopfield neural networks with time-varying delays

This paper studies the problems of global exponential stability of reaction-diffusion high-order Markovian jump Hopfield neural networks with time-varying delays. By employing a new Lyapunov-Krasovskii functional and linear matrix inequality, some criteria of global exponential stability in the mean square for the reaction-diffusion high-order neural networks are established, which are easily verifiable and have a wider adaptive. An example is also discussed to illustrate our results.     

Stationary oscillation for high-order Hopfield neural networks with time delays and impulses

We investigate stationary oscillation for high-order Hopfield neural networks with time delays and impulses. In a recent paper [J. Zhang, Z. J. Gui, Existence and stability of periodic solutions of high-order Hopfield neural networks with impulses and delays, Journal of Computational and Applied Mathematics 224 (2008) 602-613], the authors claim that they obtain a criterion of existence, uniqueness, and global exponential stability of periodic solution (i.e. stationary oscillation) for high-order Hopfield neural networks with time delays and impulses. In this paper, we point out that the main result of the recent paper is unture, and present a new sufficient condition of stationary oscillation for the neural networks. A numerical example is given to illustrate the effectiveness of the obtained result.     

GLOBAL ROBUST STABILITY OF INTERVAL HOPFIELD NEURAL NETWORKS WITH CONTINUOUSLY DISTRIBUTED DELAYS

In this paper,we implement topological degree theory and Lyapunov-functional methods to obtain the existence and uniqueness of the equilibrium point and its global robust stability for interval Hopfield neural networks with continuously distributed delays.Moreover,the methods used in judging the robust stability are proven practical and easily verifiable.     

LMI-based criteria for stability of high-order neural networks with time-varying delay

This paper investigates the stability of a class of high-order neural networks with time-varying delay, which can be considered as an expansion of Hopfield neural networks and is seldom considered in the literature. Based on the Lyapunov stability theory and linear matrix inequality (LMI) technique, sufficient conditions guaranteeing the global exponential stability of the equilibrium point are presented. Two examples are given to show the effectiveness of the proposed conditions. The obtained results are also shown to be different from and more general than existing ones.     

Using groups in the splitting preconditioner computation for interior point methods

Interior point methods usually rely on iterative methods to solve the linear systems of large scale problems. The paper proposes a hybrid strategy using groups for the preconditioning of these iterative methods. The objective is to solve large scale linear programming problems more efficiently by a faster and robust computation of the preconditioner. In these problems, the coefficient matrix of the linear system becomes ill conditioned during the interior point iterations, causing numerical difficulties to find a solution, mainly with iterative methods. Therefore, the use of preconditioners is a mandatory requirement to achieve successful results. The paper proposes the use of a new columns ordering for the splitting preconditioner computation, exploring the sparsity of the original matrix and the concepts of groups. This new preconditioner is designed specially for the final interior point iterations; a hybrid approach with the controlled Cholesky factorization preconditioner is adopted. Case studies show that the proposed methodology reduces the computational times with the same quality of solutions when compared to previous reference approaches. Furthermore, the benefits are obtained while preserving the sparse structure of the systems. These results highlight the suitability of the proposed approach for large scale problems.     

连续型BAM神经网络的指数稳定性

首先将连续型双向联想记忆神经网络转化成一个特殊的Hopfield网络模型.在此基础上,对连续BAM神经网络的指数稳定性进行了新的分析,证明了神经网络连接权矩阵在给定的约束条件下有唯一平衡点.所做的分析可以用于设计全局指数稳定的神经网络.