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.     

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.     

An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal–dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set of linear and mixed integer programming problems. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

On differentiable exact penalty functions

In this work, we study a differentiable exact penalty function for solving twice continuously differentiable inequality constrained optimization problems. Under certain assumptions on the parameters of the penalty function, we show the equivalence of the stationary points of this function and the Kuhn-Tucker points of the restricted problem as well as their extreme points. Numerical experiments are presented that corroborate the theory, and a rule is given for choosing the parameters of the penalty function.     

等式约束优化问题的一类新的简单光滑精确罚函数

精确罚函数方法是求解优化问题的一类经典方法,传统的精确罚函数不可能既是简单的又是光滑的,这里简单的是指罚函数中不包含目标函数和约束函数的梯度信息。针对等式约束问题提出了不同与传统罚函数的一类新的简单光滑罚函数并证明了它是精确的。给出了以新的罚函数为基础的罚函数方法并用数值例子说明算法是可行的。     

Geometric approach to Fletcher's ideal penalty function

In this note, we derive a geometric formulation of an ideal penalty function for equality constrained problems. This differentiable penalty function requires no parameter estimation or adjustment, has numerical conditioning similar to that of the target function from which it is constructed, and also has the desirable property that the strict second-order constrained minima of the target function are precisely those strict second-order unconstrained minima of the penalty function which satisfy the constraints. Such a penalty function can be used to establish termination properties for algorithms which avoid ill-conditioned steps. Numerical values for the penalty function and its derivatives can be calculated efficiently using automatic differentiation techniques.     

A Class of penalty functions for optimization problema with bound constraints

In this paper we propose a new class of continuously differentiable globally exact penalty functions for the solution of minimization problems with simple bounds on some (all) of the variables. The penalty functions in this class fully exploit the structure of the problem and are easily computable. Furthermore we introduce a simple updating rule for the penalty parameter that can be used in conjunction with unconstrained minimization techniques to solve the original problem.     

On the exactness of a class of nondifferentiable penalty functions

In this paper, we consider a class of nondifferentiable penalty functions for the solution of nonlinear programming problems without convexity assumptions. Preliminarily, we introduce a notion of exactness which appears to be of relevance in connection with the solution of the constrained problem by means of unconstrained minimization methods. Then, we show that the class of penalty functions considered is exact, according to this notion. This research was partially supported by the National Research Program on “Modelli e Algoritmi per l'Ottimizzazione,” Ministero della Pubblica, Istruzione, Roma, Italy.     

非线性约束优化的光滑化平方根罚函数

介绍一种非线性约束优化的不可微平方根罚函数,为这种非光滑罚函数提出了一个新的光滑化函数和对应的罚优化问题,获得了原问题与光滑化罚优化问题目标之间的误差估计. 基于这种罚函数,提出了一个算法和收敛性证明,数值例子表明算法对解决非线性约束优化具有有效性.     

Interval goal programming for S-shaped penalty function

The approach of Jones and Tamiz (1995) [Jones, D.F., Tamiz, M., 1995. Expanding the flexibility of goal programming via preference modeling techniques. Omega 23, 41–48] has been accepted as the most efficient approach in the field of interval goal programming (IGP). Although several modifications to the original approach have been proposed recently [Vitoriano, B., Romero, C., 1999. Extended interval goal programming. Journal of the Operational Research Society 50, 1280–1283; Chang, C.-T., 2006. Mixed binary interval goal programming. Journal of the Operational Research Society 35, 389–396], all of them cannot formulate IGP with an S-shaped penalty function. In order to improve the utility of IGP, we extend the model of Chang (2006) [Chang, C.-T., 2006. Mixed binary interval goal programming. Journal of the Operational Research Society 35, 389–396] to be able to model an S-shaped penalty function. The newly formulated model is more concise and compact than the method of Li and Yu (2000) and it can easily be applied to a decision problem with the S-shaped penalty function. Finally, an illustrative example (i.e. how to build an appropriate E-learning system) is included for demonstrating the usefulness of the proposed model.     

Robust Recursive Quadratic Programming Algorithm Model with Global and Superlinear Convergence Properties

A new, robust recursive quadratic programming algorithm model based on a continuously differentiable merit function is introduced. The algorithm is globally and superlinearly convergent, uses automatic rules for choosing the penalty parameter, and can efficiently cope with the possible inconsistency of the quadratic search subproblem. The properties of the algorithm are studied under weak a priori assumptions; in particular, the superlinear convergence rate is established without requiring strict complementarity. The behavior of the algorithm is also investigated in the case where not all of the assumptions are met. The focus of the paper is on theoretical issues; nevertheless, the analysis carried out and the solutions proposed pave the way to new and more robust RQP codes than those presently available.     

A computational study on different penalty approaches for solving constrained global optimization problems with the electromagnetism-like method

In this article, the application of the electromagnetism-like method (EM) for solving constrained optimization problems is investigated. A number of penalty functions have been tested with EM in this investigation, and their merits and demerits have been discussed. We have also provided motivations for such an investigation. Finally, we have compared EM with two recent global optimization algorithms from the literature. We have shown that EM is a suitable alternative to these methods and that it has a role to play in solving constrained global optimization problems.     

On penalty methods for minimax problems

Penalty algorithms for constrained minimax problems typically involve a sequence of unconstrained approximates which is pointwise monotone in each variable. This paper generalizes convergence results for a wider class of algorithms while imposing conditions which are close to being minimal.Sponsored in part by a grant from the Norwegian Council of Scientific and Technological Research.     

An exact penalty on bilevel programs with linear vector optimization lower level

We are interested in a class of linear bilevel programs where the upper level is a linear scalar optimization problem and the lower level is a linear multi-objective optimization problem. We approach this problem via an exact penalty method. Then, we propose an algorithm illustrated by numerical examples.     

Application of penalty methods to non-stationary variational inequalities

We solve a general variational inequality problem in a finite-dimensional setting, where only approximation sequences are known instead of exact values of the cost mapping and feasible set. We suggest to utilize a sequence of solutions of auxiliary problems based on a penalty method. Its convergence is attained without concordance of penalty and approximation parameters under mild coercivity type conditions. We also show that the regularized version of the penalty method enables us to further weaken the coercivity condition.     

An economic interpretation of exact penalty functions using sensitivity analysis

It has already been demonstrated that under some assumptions, a local minimum of a constrained problem is also a local unconstrained minimum of a function which is called an exact penalty function. Here, we present the same result with a new demonstration. By using sensitivity analysis, we give an economic interpretation for exact penalty functions.     

Weak linear bilevel programming problems: existence of solutions via a penalty method

We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm.     

Nonlinear separation approach to inverse variational inequalities

In this paper, we employ the image space analysis to investigate an inverse variational inequality (for short, IVI) with a cone constraint. By virtue of the nonlinear scalarization function commonly known as the Gerstewitz function, three nonlinear weak separation functions, two nonlinear regular weak separation functions and a nonlinear strong separation function are first introduced. Then, by these nonlinear separation functions, theorems of the weak and strong alternative and some optimality conditions for IVI with a cone constraint are derived without any convexity. In particular, a global saddle-point condition for a nonlinear function is investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Finally, two gap functions and an error bound for IVI with a cone constraint are obtained.     

On generic quadratic penalty embeddings for nonlinear optimization problems

The generic character of regularity in the sense of Jongen, Jonker and Twilt is studied for a particular class of embeddings, which represents a quadratric penalty procedure. In this paper we state a suitable perturbation result (into the mentioned class) which is the main part for the proof of the genericity