An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

A new penalty-free-type algorithm based on trust region techniques

In this paper, we propose a new penalty-free-type method for nonlinear equality constrained problems. The new algorithm uses trust region framework and feasibility safeguarding technique. Moreover, it has no choice of penalty parameter and penalty function as a merit function, and it does not use the filter technique to avoid the penalty function either. We analyze the global convergence of the main algorithm under the standard assumptions. The preliminary numerical tests are reported.     

Theoretical and Practical Convergence of a Self-Adaptive Penalty Algorithm for Constrained Global Optimization

This paper proposes a self-adaptive penalty function and presents a penalty-based algorithm for solving nonsmooth and nonconvex constrained optimization problems. We prove that the general constrained optimization problem is equivalent to a bound constrained problem in the sense that they have the same global solutions. The global minimizer of the penalty function subject to a set of bound constraints may be obtained by a population-based meta-heuristic. Further, a hybrid self-adaptive penalty firefly algorithm, with a local intensification search, is designed, and its convergence analysis is established. The numerical experiments and a comparison with other penalty-based approaches show the effectiveness of the new self-adaptive penalty algorithm in solving constrained global optimization problems.     

An infeasible nonmonotone SSLE algorithm for nonlinear programming

In this paper, we propose a new nonmonotone algorithm using the sequential systems of linear equations, which is an infeasible QP-free method. We use neither a penalty function nor a filter. Therefore, it is unnecessary to choose a problematic penalty parameter. The new algorithm only needs to solve three systems of linear equations with the same nonsingular coefficient matrix. Under some suitable conditions, the global convergence is established. Some numerical results are also presented.     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

General Information

In this paper, a new sequential penalty algorithm, based on the L_infin exact penalty function, is proposed for a general nonlinear constrained optimization problem. The algorithm has the following characteristics: it can start from an arbitrary initial point; the feasibility of the subproblem is guaranteed; the penalty parameter is adjusted automatically; global convergence without any regularity assumption is proved. The update formula of the penalty parameter is new. It is proved that the algorithm proposed in this paper behaves equivalently to the standard SQP method after sufficiently many iterations. Hence, the local convergence results of the standard SQP method can be applied to this algorithm. Preliminary numerical experiments show the efficiency and stability of the algorithm.     

An Approach to Finding a Global Minimization with Equality and Inequality Constraints

We give an approach for finding a global minimization with equality and inequality Constraints.Our approach is to construct an exact penalty function, and prove that the global minimal points of this exact penalty function are the primal constrained global minimal points. Thus we convert the problem of global constrained optimization into a problem of global unconstrained optimization. Furthermore, the integral approach for finding a global minimization for a class of discontinuous functions is used and an implementable algorithm is given.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.     

Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization

In a recent paper (Ref. 1), the author proposed a trust-region algorithm for solving the problem of minimizing a nonlinear function subject to a set of equality constraints. The main feature of the algorithm is that the penalty parameter in the merit function can be decreased whenever it is warranted. He studied the behavior of the penalty parameter and proved several global and local convergence results. One of these results is that there exists a subsequence of the iterates generated by the algorithm that converges to a point that satisfies the first-order necessary conditions.In the current paper, we show that, for this algorithm, there exists a subsequence of iterates that converges to a point that satisfies both the first-order and the second-order necessary conditions.This research was supported by the Rice University Center for Research on Parallel Computation, Grant R31853, and the REDI Foundation.     

化不等式约束问题为无约束的广义可微限域精确罚函数方法

本文给出了广义可微精确罚函数的概念及一类所谓广义限域可微精确罚函数.本文预先选定罚因子,将不等式约束问题化为单一的无约束问题,并给出了具全局收敛性的算法.本文的罚函数构造简单,假设条件少而且算法的构造与收敛性结果是独特的.     

一类新的罚函数与罚算法(英)

在本文中,我们提出了带不等式约束的非线性规划问题的一类新的罚函数,它的一个子类可以光滑逼近$l_1$罚函数. 基于此类新的罚函数我们给出了一种罚算法,这个算法的特点是每次迭代求出罚函数的全局精确解或非精确解. 在很弱的条件下算法总是可行的. 我们在不需要任何约束规范的情况下,证明了算法的全局收敛性. 最后给出了数值实验.     

Exactness and algorithm of an objective penalty function

Penalty function is an important tool in solving many constrained optimization problems in areas such as industrial design and management. In this paper, we study exactness and algorithm of an objective penalty function for inequality constrained optimization. In terms of exactness, this objective penalty function is at least as good as traditional exact penalty functions. Especially, in the case of a global solution, the exactness of the proposed objective penalty function shows a significant advantage. The sufficient and necessary stability condition used to determine whether the objective penalty function is exact for a global solution is proved. Based on the objective penalty function, an algorithm is developed for finding a global solution to an inequality constrained optimization problem and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the objective penalty function is proved for a local solution. An algorithm is presented in the paper in finding a local solution, with its convergence proved under some conditions. Finally, numerical experiments show that a satisfactory approximate optimal solution can be obtained by the proposed algorithm.     

On the convergence of a new trust region algorithm

Summary. In this paper we present a new trust region algorithm for general nonlinear constrained optimization problems. The algorithm is based on the exact penalty function. Under very mild conditions, global convergence results for the algorithm are given. Local convergence properties are also studied. It is shown that the penalty parameter generated by the algorithm will be eventually not less than the norm of the Lagrange multipliers at the accumulation point. It is proved that the method is equivalent to the sequential quadratic programming method for all large , hence superlinearly convergent results of the SQP method can be applied. Numerical results are also reported. Received March 21, 1993     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

A line search exact penalty method using steering rules

Line search algorithms for nonlinear programming must include safeguards to enjoy global convergence properties. This paper describes an exact penalization approach that extends the class of problems that can be solved with line search sequential quadratic programming methods. In the new algorithm, the penalty parameter is adjusted at every iteration to ensure sufficient progress in linear feasibility and to promote acceptance of the step. A trust region is used to assist in the determination of the penalty parameter, but not in the step computation. It is shown that the algorithm enjoys favorable global convergence properties. Numerical experiments illustrate the behavior of the algorithm on various difficult situations.     

A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

不等式约束优化问题的低阶精确罚函数的光滑化算法

对不等式约束优化问题提出了一个低阶精确罚函数的光滑化算法. 首先给出了光滑罚问题、非光滑罚问题及原问题的目标函数值之间的误差估计,进而在弱的假
设之下证明了光滑罚问题的全局最优解是原问题的近似全局最优解. 最后给出了一个基于光滑罚函数的求解原问题的算法,证明了算法的收敛性,并给出数值算例说明算法的可行性.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

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.     

Convergence of the Peaceman-Rachford Splitting Method for a Class of Nonconvex Programs

In this paper, we analyze the convergence of the Peaceman-Rachford splitting method (PRSM) for a type of nonconvex and nonsmooth optimization with linear constraints, whose objective function is the sum of a proper lower semicontinuous function and a strongly convex differential function. When a suitable penalty parameter is chosen and the iterative point sequence is bounded, we show the global convergence of the PRSM. Furthermore, under the assumption that the associated function satisfies the Kurdyka-Łojasiewicz property, we prove the strong convergence of the PRSM. We also provide sufficient conditions guaranteeing the boundedness of the generated sequence. Finally, we present some preliminary numerical results to show the effectiveness of the PRSM and also give a comparison with the Douglas-Rachford splitting method.