A Simple Primal-Dual Feasible Interior-Point Method for Nonlinear Programming with Monotone Descent

We propose and analyze a primal-dual interior point method of the feasible type, with the additional property that the objective function decreases at each iteration. A distinctive feature of the method is the use of different barrier parameter values for each constraint, with the purpose of better steering the constructed sequence away from non-KKT stationary points. Assets of the proposed scheme include relative simplicity of the algorithm and of the convergence analysis, strong global and local convergence properties, and good performance in preliminary tests. In addition, the initial point is allowed to lie on the boundary of the feasible set.     

非线性规划的摄动可行方向法

本文提出了二类新的摄动可行方向法,发展和完善了这类方法.新方法形式简单而且不必用Polak程序.适当选择算法中有关参数可减少计算量,还可加快算法的收敛速度.     

两类解非线性约束问题的超记忆可行方向法

本文将无约束超记忆梯度法推广到非线性不等式约束优化问题上来,给出了两类形式很一般的超记忆可行方向法,并在非退化及连续可微等较弱的假设下证明了其全局收敛性.适当选取算法中的参量及记忆方向,不仅可得到一些已知的方法及新方法,而且还可能加快算法的收敛速度.     

An Interior-Point Algorithm for Nonconvex Nonlinear Programming

The paper describes an interior-point algorithm for nonconvex nonlinear programming which is a direct extension of interior-point methods for linear and quadratic programming. Major modifications include a merit function and an altered search direction to ensure that a descent direction for the merit function is obtained. Preliminary numerical testing indicates that the method is robust. Further, numerical comparisons with MINOS and LANCELOT show that the method is efficient, and has the promise of greatly reducing solution times on at least some classes of models.     

Global Convergence Analysis of Line Search Interior-Point Methods for Nonlinear Programming without Regularity Assumptions

As noted by Wächter and Biegler (Ref. 1), a number of interior-point methods for nonlinear programming based on line-search strategy may generate a sequence converging to an infeasible point. We show that, by adopting a suitable merit function, a modified primal-dual equation, and a proper line-search procedure, a class of interior-point methods of line-search type will generate a sequence such that either all the limit points of the sequence are KKT points, or one of the limit points is a Fritz John point, or one of the limit points is an infeasible point that is a stationary point minimizing a function measuring the extent of violation to the constraint system. The analysis does not depend on the regularity assumptions on the problem. Instead, it uses a set of satisfiable conditions on the algorithm implementation to derive the desired convergence property.Communicated by Z. Q. LuoThis research was partially supported by Grant R-314-000-026/042/057-112 of National University of Singapore and Singapore-MIT Alliance. We thank Professor Khoo Boo Cheong, Cochair of the High Performance Computation Program of Singapore-MIT Alliance, for his support     

Globally Convergent Interior-Point Algorithm for Nonlinear Programming

This paper presents a primal-dual interior-point algorithm for solving general constrained nonlinear programming problems. The inequality constraints are incorporated into the objective function by means of a logarithmic barrier function. Also, satisfaction of the equality constraints is enforced through the use of an adaptive quadratic penalty function. The penalty parameter is determined using a strategy that ensures a descent property for a merit function. Global convergence of the algorithm is achieved through the monotonic decrease of a merit function. Finally, extensive computational results show that the algorithm can solve large and difficult problems in an efficient and robust way.Communicated by L. C. W. DixonThe research reported in this paper was done while the first author was at Imperial College. The authors gratefully acknowledge constructive comments from Professor L. C. W. Dixon and an anonymous referee. They are also grateful to Dr. Stanislav Zakovic for helpful suggestions and comments. Financial support was provided by EPSRC Grants M16016 and GR/G51377/01.     

Feasible direction method for large-scale nonconvex programs: Decomposition approach

In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by dual decomposition. Results are extended for dynamical problems which include distributed delays and constraints both in state and control variables. The approach is compared with other feasible-direction approaches, and the method is applied to a power generation problem. Some computational results are included.This work was supported by the Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, Brasilia, Brasil, and by the Fundaçao de Amparo a Pesquisa do Estado de Sao Paulo, Sao Paulo, Brazil.On leave from UNICAMP, Campinas, Brazil.     

Interior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions

Recently, Fletcher and Leyffer proposed using filter methods instead of a merit function to control steplengths in a sequential quadratic programming algorithm. In this paper, we analyze possible ways to implement a filter-based approach in an interior-point algorithm. Extensive numerical testing shows that such an approach is more efficient than using a merit function alone.     

Feasible Interior Methods Using Slacks for Nonlinear Optimization

A slack-based feasible interior point method is described which can be derived as a modification of infeasible methods. The modification is minor for most line search methods, but trust region methods require special attention. It is shown how the Cauchy point, which is often computed in trust region methods, must be modified so that the feasible method is effective for problems containing both equality and inequality constraints. The relationship between slack-based methods and traditional feasible methods is discussed. Numerical results using the KNITRO package show the relative performance of feasible versus infeasible interior point methods.     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

非线性最优化一个可行序列等式约束二次规划算法

本文针对非线性不等式约束优化问题,提出了一个新的可行序列等式约束二次规划算法．在每次迭代中,该算法只需求解三个相同规模且仅含等式约束的二次规划(必要时求解一个辅助的线性规划),因而其计算工作量较小．在一般的条件下,证明了算法具有全局收敛及超线性收敛性．数值实验表明算法是有效的．     

Primal-Dual Newton-Type Interior-Point Method for Topology Optimization

We consider the problem of minimization of energy dissipation in a conductive electromagnetic medium with a fixed geometry and a priori given lower and upper bounds for the conductivity. The nonlinear optimization problem is analyzed by using the primal-dual Newton interior-point method. The elliptic differential equation for the electric potential is considered as an equality constraint. Transforming iterations for the null space decomposition of the condensed primal-dual system are applied to find the search direction. The numerical experiments treat two-dimensional isotropic systems.     

On the Newton Interior-Point Method for Nonlinear Programming Problems

Interior-point methods have been developed largely for nonlinear programming problems. In this paper, we generalize the global Newton interior-point method introduced in Ref. 1 and we establish a global convergence theory for it, under the same assumptions as those stated in Ref. 1. The generalized algorithm gives the possibility of choosing different descent directions for a merit function so that difficulties due to small steplength for the perturbed Newton direction can be avoided. The particular choice of the perturbation enables us to interpret the generalized method as an inexact Newton method. Also, we suggest a more general criterion for backtracking, which is useful when the perturbed Newton system is not solved exactly. We include numerical experimentation on discrete optimal control problems.     

Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J. Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximities for linear optimization (LO) problems. They also extended the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this kernel function, both with large- and small-updates. The complexity bounds are and , respectively, which are as good as those in the linear case. Mathematics Subject Classifications (2000) 90C22, 90C31.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

Local Convergence of the Affine-Scaling Interior-Point Algorithm for Nonlinear Programming

This paper addresses the local convergence properties of the affine-scaling interior-point algorithm for nonlinear programming. The analysis of local convergence is developed in terms of parameters that control the interior-point scheme and the size of the residual of the linear system that provides the step direction. The analysis follows the classical theory for quasi-Newton methods and addresses q-linear, q-superlinear, and q-quadratic rates of convergence.     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

On the Global Convergence of a Modified Augmented Lagrangian Linesearch Interior-Point Newton Method for Nonlinear Programming

We consider a linesearch globalization of the local primal-dual interior-point Newton method for nonlinear programming introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. The linesearch uses a new merit function that incorporates a modification of the standard augmented Lagrangian function and a weak notion of centrality. We establish a global convergence theory and present promising numerical experimentation.     

图的最大二等分问题的低秩可行方向算法

基于图的最大二等分问题的半定规划松弛模型,利用矩阵的低秩分解技巧,给出了该问题的半定规划松弛的一种低秩可行方向算法.在一定的条件下,证明了算法的收敛性.结合0.699随机扰动方法得到原问题的近似最优解.数值实验表明该方法能有效地求解图的最大二等分问题.     

Stabilization of Interior-Point Methods for Linear Programming

The paper studies numerical stability problems arising in the application of interior-point methods to primal degenerate linear programs. A stabilization procedure based on Gaussian elimination is proposed and it is shown that it stabilizes all path following methods, original and modified Dikin's method, Karmarkar's method, etc.