A generalized Lagrangian function and multiplier method

As is well known, a saddle point for the Lagrangian function, if it exists, provides a solution to a convex programming problem; then, the values of the optimal primal and dual objective functions are equal. However, these results are not valid for nonconvex problems.In this paper, several results are presented on the theory of the generalized Lagrangian function, extended from the classical Lagrangian and the generalized duality program. Theoretical results for convex problems also hold for nonconvex problems by extension of the Lagrangian function. The concept of supporting hypersurfaces is useful to add a geometric interpretation to computational algorithms. This provides a basis to develop a new algorithm.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

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.     

A combined penalty function and gradient projection method for nonlinear programming

A new programming algorithm for nonlinear constrained optimization problems is proposed. The method is based on the penalty function approach and thereby circumyents the necessity to maintain feasibility at each iteration, but it also behaves much like the gradient projection method. Although only first-order information is used, the algorithm converges asymptotically at a rate which is independent of the magnitude of the penalty term; hence, unlike the simple gradient method, the asymptotic rate of the proposed method is not affected by the ill-conditioning associated with the introduction of the penalty term. It is shown that the asymptotic rate of convergence of the proposed method is identical with that of the gradient projection method.Dedicated to Professor M. R. HestenesThis research was supported by the National Science Foundation, Grant No. GK-16125.     

Quadratic multiplier method convergence

In a recent paper (Ref. 1), the author briefly mentioned a variant of Hestenes' method of multipliers which would converge quadratically. This note examines that method in detail and provides some examples. In the quadratic-linear case, this algorithm converges in one iteration.     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

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.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.     

A globally convergent,implementable multiplier method with automatic penalty limitation

This paper deals with penalty function and multiplier methods for the solution of constrained nonconvex nonlinear programming problems. Starting from an idea introduced several years ago by Polak, we develop a class of implementable methods which, under suitable assumptions, produce a sequence of points converging to a strong local minimum for the problem, regardless of the location of the initial guess. In addition, for sequential minimization type multiplier methods, we make use of a rate of convergence result due to Bertsekas and Polyak, to develop a test for limiting the growth of the penalty parameter and thereby prevent ill-conditioning in the resulting sequence of unconstrained optimization problems.Research sponsored by the National Science Foundation (RANN) Grant ENV76-04264 and the Joint Services Electronics Research Program Contract F44620-76-C-0100.     

The role of the multipliers in the multiplier method

The paper studies the role of the multipliers when the multiplier method is applied as a computational technique for minimizing penalized cost functionals for optimal control problems characterized by linear systems and integral quadratic costs.Theauthor would like to gratefully thank two anonymous referees for many helpful suggestions which led to a major improvement in both the quality and clarity of the paper, and to Professor Angelo Miele for his encouragement.     

Inner solvers for interior point methods for large scale nonlinear programming

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported. This research was supported by the Italian Ministry for Education, University and Research (MIUR) projects: FIRB Project: “Parallel Nonlinear Numerical Optimization PN ² O” (grant n. RBAU01JYPN, ) and COFIN/PRIN04 Project “Numerical Methods and Mathematical Software for Applications” (grant n. 2004012559, ).     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

A class of generalized variable penalty methods for nonlinear programming

A class of generalized variable penalty formulations for solving nonlinear programming problems is presented. The method poses a sequence of unconstrained optimization problems with mechanisms to control the quality of the approximation for the Hessian matrix, which is expressed in terms of the constraint functions and their first derivatives. The unconstrained problems are solved using a modified Newton's algorithm. The method is particularly applicable to solution techniques where an approximate analysis step has to be used (e.g., constraint approximations, etc.), which often results in the violation of the constraints. The generalized penalty formulation contains two floating parameters, which are used to meet the penalty requirements and to control the errors in the approximation of the Hessian matrix. A third parameter is used to vary the class of standard barrier or quasibarrier functions, forming a branch of the variable penalty formulation. Several possibilities for choosing such floating parameters are discussed. The numerical effectiveness of this algorithm is demonstrated on a relatively large set of test examples.The author is thankful for the constructive suggestions of the referees.     

线性与非线性规划算法与理论

线性规划与非线性规划是数学规划中经典而重要的研究方向. 主要介绍该研究方向的背景知识,并介绍线性规划、无约束优化和约束优化的最新算法与理论以及一些前沿与热点问题. 交替方向乘子法是一类求解带结构的约束优化问题的方法,近年来倍受重视. 全局优化是一个对于应用优化领域非常重要的研究方向. 因此也试图介绍这两个方面的一些最新研究进展和问题.     

Regularized dual method for nonlinear mathematical programming

For a nonlinear programming problem with equality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. The algorithm is based on a modified dual of the original problem that is solved directly by applying Tikhonov regularization. The algorithm is designed to determine a norm-bounded minimizing sequence of feasible elements. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is given in the case of a finite fixed error in the input data.     

Generalized Lagrange multiplier technique for nonlinear programming

Our aim here is to present numerical methods for solving a general nonlinear programming problem. These methods are based on transformation of a given constrained minimization problem into an unconstrained maximin problem. This transformation is done by using a generalized Lagrange multiplier technique. Such an approach permits us to use Newton's and gradient methods for nonlinear programming. Convergence proofs are provided, and some numerical results are given.     

非线性半定规划的逐次线性化柔性惩罚法

针对非线性不等式约束半定规划问题提出一种新的逐次线性化方法, 新算法既不要求罚函数单调下降, 也不使用过滤技巧, 尝试步的接受准则仅仅依赖于目标函数和约束违反度, 罚函数中对应于成功迭代点的罚因子不需要单调增加. 新算法或者要求违反约束度量有足够改善, 或者在约束违反度的一个合理范围内要求目标函数值充分下降, 在通常假设条件下, 分析了新算法的适定性及全局收敛性. 最后, 给出了非线性半定规划问题的数值试验结果, 结果表明了新算法的有效性.     

Solving the nonlinear least square problem: Application of a general method

An algorithm for solving the general nonlinear least-square problem is developed. An estimate for the Hessian matrix is constructed as the sum of two matrices. The first matrix is the usual first-order estimate used by the Gauss method, while the second matrix is generated recursively using a rank-one formula. Test results indicate that the method is superior to the standard Gauss method and compares favorably with other methods, especially for problems with nonzero residuals at the solution.This work was supported by the US Air Force under Contract No. F04701-73-C-0074.The author expresses his appreciation to Dr. H. E. Pickett and Dr. J. L. Searcy for their continuing support in the theoretical and practical development of the algorithm. The recursive method for generating the estimate of the Hessian matrix was developed jointly with Drs. Pickett and Searcy and is included here with their permission. The author would also like to acknowledge the contribution made by the stimulating environment of an optimal control seminar held at The Aerospace Corporation since 1970. Principle members of the seminar have been H. E. Pickett, J. L. Searcy, R. W. Reid, and the author.     

On the convergence rate for a penalty function method of exponential type

Recently, Kort and Bertsekas (Ref. 1) and Hartman (Ref. 2) presented independently a new penalty function algorithm of exponential type for solving inequality-constrained minimization problems. The main purpose of this work is to give a proof on the rate of convergence of a modification of the exponential penalty method proposed by these authors. We show that the sequence of points generated by the modified algorithm converges to the solution of the original nonconvex problem linearly and that the sequence of estimates of the optimal Lagrange multiplier converges to this multiplier superlinearly. The question of convergence of the modified method is discussed. The present paper hinges on ideas of Mangasarian (Ref. 3), but the case considered here is not covered by Mangasarian's theory.     

Firefly penalty-based algorithm for bound constrained mixed-integer nonlinear programming

In this article, we aim to extend the firefly algorithm (FA) to solve bound constrained mixed-integer nonlinear programming (MINLP) problems. An exact penalty continuous formulation of the MINLP problem is used. The continuous penalty problem comes out by relaxing the integrality constraints and by adding a penalty term to the objective function that aims to penalize integrality constraint violation. Two penalty terms are proposed, one is based on the hyperbolic tangent function and the other on the inverse hyperbolic sine function. We prove that both penalties can be used to define the continuous penalty problem, in the sense that it is equivalent to the MINLP problem. The solutions of the penalty problem are obtained using a variant of the metaheuristic FA for global optimization. Numerical experiments are given on a set of benchmark problems aiming to analyze the quality of the obtained solutions and the convergence speed. We show that the firefly penalty-based algorithm compares favourably with the penalty algorithm when the deterministic DIRECT or the simulated annealing solvers are invoked, in terms of convergence speed.