Penalty methods for mathematical programming inE nwith general constraint sets

This paper extends the principal supporting results and the general convergence theorems for penalty methods, obtained by Fiacco and McCormick (Ref. 1) for the continuous mathematical programming problem, to the problem of minimizing a mildly regulated objective function over any nonempty subset ofE ⁿ.The constraint set need not be defined through a collection of inequalities. A general auxiliary function is defined, and the desired minimizing sequence is shown to exist, without additional assumptions (i.e., assumptions other than those invoked in the principal convergence theorem of Ref. 1). A particularly interesting consequence is the fact that a discrete (e.g., integer) programming problem can be solved by asingle unconstrained minimization of the auxiliary function.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

On a Lagrangian penalty function method for nonlinear programming problems

We modify a Lagrangian penalty function method proposed in [4] for constrained convex mathematical programming problems in order to obtain a geometric rate of convergence. For nonconvex problems we show that a special case of the algorithm in the above paper is still convergent without coercivity and convexity assumptions.On leave from the Institute of Mathematics, Hanoi, by a grant from Alexander-von-Humboldt-Stiftung.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.     

Exact penalty functions method for mathematical programming problems involving invex functions

In this paper, some new results on the exact penalty function method are presented. Simple optimality characterizations are given for the differentiable nonconvex optimization problems with both inequality and equality constraints via exact penalty function method. The equivalence between sets of optimal solutions in the original mathematical programming problem and its associated exact penalized optimization problem is established under suitable invexity assumption. Furthermore, the equivalence between a saddle point in the invex mathematical programming problem and an optimal point in its exact penalized optimization problem is also proved.     

Enlarging the region of convergence of Newton's method for constrained optimization

In this paper, we consider Newton's method for solving the system of necessary optimality conditions of optimization problems with equality and inequality constraints. The principal drawbacks of the method are the need for a good starting point, the inability to distinguish between local maxima and local minima, and, when inequality constraints are present, the necessity to solve a quadratic programming problem at each iteration. We show that all these drawbacks can be overcome to a great extent without sacrificing the superlinear convergence rate by making use of exact differentiable penalty functions introduced by Di Pillo and Grippo (Ref. 1). We also show that there is a close relationship between the class of penalty functions of Di Pillo and Grippo and the class of Fletcher (Ref. 2), and that the region of convergence of a variation of Newton's method can be enlarged by making use of one of Fletcher's penalty functions.This work was supported by the National Science Foundation, Grant No. ENG-79-06332.     

A NEW SQP-FILTER METHOD PROGRAMMING FOR SOLVING NONLINEAR PROBLEMS

In [4], Fletcher and Leyffer present a new method that solves nonlinear programming problems without a penalty function by SQP-Filter algorithm. It has attracted much attention due to its good numerical results. In this paper we propose a new SQP-Filter method which can overcome Maratos effect more effectively. We give stricter acceptant criteria when the iterative points are far from the optimal points and looser ones vice-versa. About this new method, the proof of global convergence is also presented under standard assumptions. Numerical results show that our method is efficient.     

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.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

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.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

On the Existence of Solutions to Stochastic Mathematical Programs with Equilibrium Constraints

We generalize stochastic mathematical programs with equilibrium constraints (SMPEC) introduced by Patriksson and Wynter (Ref. 1) to allow for the inclusion of joint upper-level constraints and to change the continuity assumptions with respect to the uncertainty parameters assumed before by measurability assumptions. For this problem, we prove the existence of solutions. We discuss also algorithmic aspects of the problem, in particular the construction of an inexact penalty function for the SMPEC problem. We apply the theory to the problem of structural topology optimization.     

An application of Neustadt's abstract maximum principle to probability kinematics

An important class of problems in philosophy can be formulated as mathematical programming problems in an infinite-dimensional vector space. One such problem is that of probability kinematics: the study of how an individual ought to adjust his degree-of-belief function in response to new information. Much work has recently been done to establish maximum principles for these generalized programming problems (Refs. 3–4). Perhaps, the most general treatment of the problem presented to date is that by Neustadt (Ref. 1). In this paper, the problem of probability kinematics is formulated as a generalized mathematical programming problem and necessary conditions for the optimal revised degree-of-belief function are derived from an abstract maximum principle contained in Neustadt's paper.This work was supported by the National Research Council of Canada.The author is grateful to G. J. Lastman and J. A. Baker of the University of Waterloo for numerous suggestions made for improvement of this paper. The problem of probability kinematics was brought to the author's attention by W. L. Harper of the University of Western Ontario.     

Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints

We adapt the convergence analysis of the smoothing (Ref. 1) and regularization (Ref. 2) methods to a penalty framework for mathematical programs with complementarity constraints (MPCC); we show that the penalty framework shares convergence properties similar to those of these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to a B-stationary point of the MPCC.     

The Classical Average-Cost Inventory Models of Iglehart and Veinott–Wagner Revisited

This paper revisits the classical papers of Iglehart (Ref. 1) and Veinott and Wagner (Ref. 2) devoted to stochastic inventory problems with the criterion of long-run average cost minimization. We indicate some of the assumptions that are used implicitly without verification in their stationary distribution approach to the problems and provide the missing (nontrivial) verification. In addition to completing their analysis, we examine the relationship between the stationary distribution approach and the dynamic programming approach to the average-cost stochastic inventory problems.     

Saddle-Point Criteria in an η-Approximation Method for Nonlinear Mathematical Programming Problems Involving Invex Functions

In this paper, the η-approximation method introduced by Antczak (Ref. 1) for solving a nonlinear constrained mathematical programming problem involving invex functions with respect to the same function η is extended. In this method, a so-called η-approximated optimization problem associated with the original mathematical programming problems is constructed; moreover, an η-saddle point and an η-Lagrange function are defined. By the help of the constructed η-approximated optimization problem, saddle-point criteria are obtained for the original mathematical programming problem. The equivalence between an η-saddle point of the η-Lagrangian of the associated η-approximated optimization problem and an optimal solution in the original mathematical programming problem is established.     

Partial Exact Penalty for Mathematical Programs with Equilibrium Constraints

It is well known that mathematical programs with equilibrium constraints (MPEC) violate the standard constraint qualifications such as Mangasarian–Fromovitz constraint qualification (MFCQ) and hence the usual Karush–Kuhn–Tucker conditions cannot be used as stationary conditions unless relatively strong assumptions are satisfied. This observation has led to a number of weaker stationary conditions, with Mordukhovich stationary (M-stationary) condition being the strongest among the weaker conditions. In nonlinear programming, it is known that MFCQ leads to an exact penalization. In this paper we show that MPEC GMFCQ, an MPEC variant of MFCQ, leads to a partial exact penalty where all the constraints except a simple linear complementarity constraint are moved to the objective function. The partial exact penalty function, however, is nonsmooth. By smoothing the partial exact penalty function, we design an algorithm which is shown to be globally convergent to an M-stationary point under an extended version of the MPEC GMFCQ.     

An elementary proof of the maximum principle for optimal control problems governed by a Volterra integral equation

An elementary proof of the maximum principle for optimal control problems whose states are governed by Volterra integral equations is given. Our proof is motivated by the work of Michel (Ref. 7) and utilizes only elementary results from analysis and mathematical programming. By appealing to Pontryagin-type perturbations of the controls, the above optimal control problem is effectively reduced to a mathematical programming problem. The results are then obtained by appealing to well-known mathematical programming results.     

Devising a Cooperation Policy for Emergency Networks

A mathematical programming model is proposed to select an optimal cooperation policy between autonomous service networks for dispatching purposes. In addition to traditional characteristics such as network topology and station location, this model takes into account 'political' constraints on minimum response-time in certain subzones. Such constraints are translated into performance requirements, which are imposed on the cooperation policy. Testing the model under different assumptions can be useful for analysing various cooperation policies. The paper formulates a mathematical programming model, derives example policies for various circumstances, and tests the sensitivity of the resultant policies to some parameters, such as the penalty for not providing service, and distances between adjacent networks. The paper suggests also a less constrained approach, which entails a linear programming model. A comparison between the two approaches is presented.     

An exact penalty method for solving optimal control problems

This paper discusses an algorithm for solving optimal control problems. An optimal control problem is presented where the final time is unknown. The algorithm consists of an integrator and a minimizer; the latter is an exact penalty function used to solve constrained nonlinear programming problems. Essentially, the optimal control problem is converted to a mathematical programming problem such that a point satisfying the differential equations via the integrator is provided to the minimizer, a lower performance index is obtained, the integrator is reinitiated, etc., until a suitable stopping criterion is satisfied.