A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

Solving variational inequalities defined on a domain with infinitely many linear constraints

We study a variational inequality problem whose domain is defined by infinitely many linear inequalities. A discretization method and an analytic center based inexact cutting plane method are proposed. Under proper assumptions, the convergence results for both methods are given. We also provide numerical examples to illustrate the proposed methods. The work of S. Wu was partially supported by the National Science Council, Taiwan, ROC (Grant No. 19731001). S.-C. Fang’s research has been supported by the US Army Research Office (Grant No. W911NF-04-D-0003) and National Science Foundation (Grant No. DMI-0553310).     

An outer approximations algorithm for computer-aided design problems

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.This research was sponsored by the National Science Foundation, Grant No. ENG73-08214A01, and the National Science Foundation (RANN), Grant No. ENV76-04264.     

The behavior of a multiplicity independent root-finding scheme in the presence of error

King and Kioustelidis independently proposed a derivative free scheme that permits root finding methods, such as the secant method to preserve high order convergence when the root in question is multiple. In this note it is shown that the scheme can fail to achieve the maximum accuracy that is attainable at a fixed precision of computation.This work was supported in part by the Office of Naval Research under contract No. N00014-76-C-0391.     

The Substitution Secant/Finite Difference Method for Large Scale Sparse Unconstrained Optimization

This paper studies a substitution secant/finite difference （SSFD） method for solving large scale sparse unconstrained optimization problems. This method is a combination of a secant method and a finite difference method, which depends on a consistent partition of the columns of the lower triangular part of the Hessian matrix. A q-superlinear convergence result and an r-convergence rate estimate show that this method has good local convergence properties. The numerical results show that this method may be competitive with some currently used algorithms.     

Dual coordinate ascent methods for non-strictly convex minimization

We consider a dual method for solving non-strictly convex programs possessing a certain separable structure. This method may be viewed as a dual version of a block coordinate ascent method studied by Auslender [1, Section 6]. We show that the decomposition methods of Han [6, 7] and the method of multipliers may be viewed as special cases of this method. We also prove a convergence result for this method which can be applied to sharpen the available convergence results for Han's methods.The main part of this research was conducted while the author was with the Laboratory for Information and Decision Systems, M.I.T., Cambridge, with support by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171 (Center for Intelligent Control Systems) and by the National Science Foundation under Grant ECS-8519058.     

A note on the convergence of the secant method for simple and multiple roots

The secant method is one of the most popular methods for root finding. Standard text books in numerical analysis state that the secant method is superlinear: the rate of convergence is set by the gold number. Nevertheless, this property holds only for simple roots. If the multiplicity of the root is larger than one, the convergence of the secant method becomes linear. This communication includes a detailed analysis of the secant method when it is used to approximate multiple roots. Thus, a proof of the linear convergence is shown. Moreover, the values of the corresponding asymptotic convergence factors are determined and are found to be also related with the golden ratio.     

弦割法与Muller法收敛阶的新证明方法

弦割法、Muller法与牛顿法一样,都是求解非线性方程的著名算法之一.然而在目前众多优秀的数值分析教材或论著中.关于弦割法和Muller法收敛阶的证明过程都是比较复杂的,无一例外的都是借助于差分方程的求解.本文对这两个算法的收敛阶给出了一种新的简单、直接的证明方法,达到了与牛顿法收敛阶证明方法的统一,同时还能够方便地求...     

Convergence theory for the structured BFGS secant method with an application to nonlinear least squares

In 1981, Dennis and Walker developed a convergence theory for structured secant methods which included the PSB and the DFP secant methods but not the straightforward structured version of the BFGS secant method. Here, we fill this gap in the theory by establishing a convergence theory for the structured BFGS secant method. A direct application of our new theory gives the first proof of local andq-superlinear convergence of the important structured BFGS secant method for the nonlinear least-squares problem, which is used by Dennis, Gay, and Welsh in the current version of the popular and successful NL2SOL code.This research was sponsored by SDIO/IST/ARO, AFOSR-85-0243, and DOE-DEFG05-86 ER-25017.A portion of this work is contained in the second author's doctoral thesis under the supervision of the other two authors in the Department of Mathematical Sciences, Rice University. The second author would like to thank Universidad del Valle, Cali, Columbia, for support during his graduate studies.An early draft of this work was presented at the SIAM 35th Anniversary Meeting, October 12–15, 1987, Denver, Colorado.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

Implementing proximal point methods for linear programming

We describe the application of proximal point methods to the linear programming problem. Two basic methods are discussed. The first, which has been investigated by Mangasarian and others, is essentially the well-known method of multipliers. This approach gives rise at each iteration to a weakly convex quadratic program which may be solved inexactly using a point-SOR technique. The second approach is based on the proximal method of multipliers, originally proposed by Rockafellar, for which the quadratic program at each iteration is strongly convex. A number of techniques are used to solve this subproblem, the most promising of which appears to be a two-metric gradient-projection approach. Convergence results are given, and some numerical experience is reported.This research was supported by National Science Foundation, Grant Nos. ASC-87-14009 and DMS-86-19903, and by Air Force Office of Scientific Research, Grant No. AFOSR-ISSA-87-0092. Part of this work was performed at Argonne National Laboratory. Computation was partly performed at the Pittsburgh Supercomputer Center under NSF Grant No. DMS-88-0033P and at the Argonne Advanced Computing Research Facility, whose support is gratefully acknowledged. The author thanks Olvi Mangasarian and Renato DeLeone for helpful discussions, and Jorge Moré for his valuable advice on the algorithms discussed in Section 3. The contributions of a referee, who provided helpful comments on an earlier version of this paper, are also acknowledged.     

Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

Primal-dual target-following algorithms for linear programming

In this paper, we propose a method for linear programming with the property that, starting from an initial non-central point, it generates iterates that simultaneously get closer to optimality and closer to centrality. The iterates follow paths that in the limit are tangential to the central path. Together with the convergence analysis, we provide a general framework which enables us to analyze various primal-dual algorithms in the literature in a short and uniform way.This work was completed with the support of a research grant from SHELL. The first author is supported by the Dutch Organization for Scientific Research (NWO), Grant No. 611-304-028. The third author is on leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116. The fourth author is supported by the Swiss National Foundation for Scientific Research, Grant No. 12-34002.92.     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

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.     

A weak condition for secant method to solve systems of nonlinear equations

In this paper, a new weak condition for the convergence of secant method to solve the systems of nonlinear equations is proposed. A convergence ball with the center x0 is replaced by that with xl, the first approximation generated by the secant method with the initial data x-1 and x0. Under the bounded conditions of the divided difference, a convergence theorem is obtained and two examples to illustrate the weakness of convergence conditions are provided. Moreover, the secant method is applied to a system of nonlinear equations to demonstrate the viability and effectiveness of the results in the paper.     

Approximation procedures based on the method of multipliers

In this paper, we consider a method for solving certain optimization problems with constraints, nondifferentiabilities, and other ill-conditioning terms in the cost functional by approximating them by well-behaved optimization problems. The approach is based on methods of multipliers. The convergence properties of the methods proposed can be inferred from corresponding properties of multiplier methods with partial elimination of constraints. A related analysis is provided in this paper.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAB-07-72-C-0259, and by the National Science Foundation under Grant No. ENG-74-19332.