一种求解不等式约束优化问题的光滑化算法

利用光滑函数建立了不等式约束优化问题KT条件的一个扰动方程组,提出了一个新的内点型算法.该算法在有限步终止时当前迭代点即为优化问题的一个精确稳定点.在一定条件下算法具有全局收敛性,数值试验表明该算法是有效的.     

Parallel Interior Point Schemes for Solving Multistage Convex Programming

The predictor–corrector interior-point path-following algorithm is promising in solving multistage convex programming problems. Among many other general good features of this algorithm, especially attractive is that the algorithm allows possibility to parallelise the major computations. The dynamic structure of the multistage problems specifies a block-tridiagonal system at each Newton step of the algorithm. A wrap-around permutation is then used to implement the parallel computation for this step.     

内点同伦方法求解更一般非凸集上的不动点问题(英文)

In this paper,we are mainly devoted to solving fixed point problems in more general nonconvex sets via an interior point homotopy method.Under suitable conditions,a constructive proof is given to prove the existence of fixed points,which can lead to an implementable globally convergent algorithm.     

求解非线性规划的原始对偶内点法(英文)

In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

Interior Point Methods for Second-Order Cone Programming and OR Applications

Interior point methods (IPM) have been developed for all types of constrained optimization problems. In this work the extension of IPM to second order cone programming (SOCP) is studied based on the work of Andersen, Roos, and Terlaky. SOCP minimizes a linear objective function over the direct product of quadratic cones, rotated quadratic cones, and an affine set. It is described in detail how to convert several application problems to SOCP. Moreover, a proof is given of the existence of the step for the infeasible long-step path-following method. Furthermore, variants are developed of both long-step path-following and of predictor-corrector algorithms. Numerical results are presented and analyzed for those variants using test cases obtained from a number of application problems.     

Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming

In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions; i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is proved.     

关于非线性规划问题的组合同伦内点法

文[1]在条件(C1)、(C2)和(C3)之下，利用组合同伦内点法讨论了非凸非线性规划问题K—K—T点的存在性，本文对条件(C2)和(C3)进行了改进和处理。     

竞争市场均衡问题的内点算法

本文应用最优化方法求解经济学中的经典问题-竞争市场均衡问题.本文对Ye的算法(Ye首先提出了解Fisher问题的原始-对偶路径跟踪算法)做了改进,分别给出了步长调整和迭代方向分解后的原始-对偶路径跟踪算法,并对算法做了理论证明和复杂性分析.最后分析了初始点的求法,做了初步的数值计算.计算结果表明算法能在有效时间内求得问题的解.     

求解一类非单调线性互补问题的宽邻域内点方法及其计算复杂性

对于一类非单调线性互补问题给出了一种新的算法——宽邻域内点算法，并讨论了其计算复杂性。     

全局收敛的凸规划的原始—对偶不可行内点算法

本对一类凸规划提出了一个原始-对偶不可行内点算法,并证明了算法的全局收敛性。     

A Study of Preconditioners for Network Interior Point Methods

We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. A computational comparison using a set of standard problems improves the understanding of the effectiveness of preconditioners in network interior point methods.     

A Class of Infeasible Interior Point Algorithms for Convex Quadratic Programming

This article proposes a class of infeasible interior point algorithms for convex quadratic programming, and analyzes its complexity. It is shown that this algorithm has the polynomial complexity. Its best complexity is O(nL).     

A Continuation Method for Solving Fixed Point Problems in Unbounded Convex Sets

In this paper, an unbounded condition is presented, under which we are able to utilize the interior point homotopy method to solve the Brouwer fixed point problem on unbounded sets. Two numerical examples in R3 are presented to illustrate the results in this paper.     

一种内点法解二次规划

二次规划（QP）为NP完全问题，本文研究了一种简单形式的二次规划。 一种基于依赖域子问题和内点法的算法被给出，其全局收敛被给出，特殊情况下，具有局部二次收敛。     

A Note on the Recursive and Parallel Structure of the Birge and Qi Factorization for Tree Structured Linear Programs

In this note, we derive the complete recursive structure of the Birge and Qi factorization for interior point methods (IPM) for tree structured linear programs as they appear in multistage stochastic programs. This recursive structure allows for an elegant implementation on parallel hardware, since multiple versions of the same program may be run on on different processors. Our preliminary computational experiment, conducted on a Beowulf cluster, demonstrates the scalability of this approach.     

半定规划的一种非精确不可行内点法

本文给出了求解半定规划的一种基于KM方向的非精确不可行内点法 ,分析了其收敛性 ,结果表明 ,该算法最多可以在O(n2 ln( 1 /ε) )步内求出半定规划的一个ε 近似解 ,与YZhang所提出的精确不可行内点法有相同的界 .     

Interior proximal point algorithm for linear programs

An interior proximal point algorithm for finding a solution of a linear program is presented. The distinguishing feature of this algorithm is the addition of a quadratic proximal term to the linear objective function. This perturbation has allowed us to obtain solutions with better feasibility. Implementation of this algorithm shows that the algorithms. We also establish global convergence and local linear convergence of the algorithm.This research was supported by National Science Foundation Grants DCR-85-21228 and CCR-87-23091 and by Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-89-0410. It was conducted while the author was a Graduate Student at the Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.     

一类线性与框式约束凸规划问题的原始-对偶内点算法

本文对一类具有线性和框式约束的凸规划问题给出了一个原始-对偶内点算法, 该算法可在任一原始-对偶可行内点启动, 并且全局收敛,当初始点靠近中心路径时, 算法成为中心路径跟踪算法。 数值实验表明, 算法对求解大型的这类问题是有效的。     

二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性

主要是将半定规划(Semidefinite Programming,简称SDP)的内点算法推广到二次半定规划(Quadratic Semidefinite Programming,简称QSDP),重点讨论了其中搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的H..K..M搜索方向,接着证明了该搜索方向的存在唯一性,最后给出了搜索方向的具体计算方法.