Smooth exact penalty functions II: a reduction to standard exact penalty functions

A new class of smooth exact penalty functions was recently introduced by Huyer and Neumaier. In this paper, we prove that the new smooth penalty function for a constrained optimization problem is exact if and only if the standard nonsmooth penalty function for this problem is exact. We also provide some estimates of the exact penalty parameter of the smooth penalty function, and, in particular, show that it asymptotically behaves as the square of the exact penalty parameter of the standard \(\ell _1\) penalty function. We briefly discuss a simple way to reduce the exact penalty parameter of the smooth penalty function, and study the effect of nonlinear terms on the exactness of this function.     

Existence of augmented Lagrange multipliers for cone constrained optimization problems

In this paper, by using an augmented Lagrangian approach, we obtain several sufficient conditions for the existence of augmented Lagrange multipliers of a cone constrained optimization problem in Banach spaces, where the corresponding augmenting function is assumed to have a valley at zero. Furthermore, we deal with the relationship of saddle points, augmented Lagrange multipliers, and zero duality gap property between the cone constrained optimization problem and its augmented Lagrangian dual problem.     

A new class of exact penalty functions and penalty algorithms

For nonlinear programming problems, we propose a new class of smooth exact penalty functions, which includes both barrier-type and exterior-type penalty functions as special cases. We develop necessary and sufficient conditions for exact penalty property and inverse proposition of exact penalization, respectively. Furthermore, we establish the equivalent relationship between these penalty functions and classical simple exact penalty functions in the sense of exactness property. In addition, a feasible penalty function algorithm is proposed. The convergence analysis of the algorithm is presented, including the global convergence property and finite termination property. Finally, numerical results are reported.     

Smooth exact penalty functions: a general approach

In the article, we present a new perspective on the method of smooth exact penalty functions that is becoming more and more popular tool for solving constrained optimization problems. In particular, our approach to smooth exact penalty functions allows one to apply previously unused tools (namely, parametric optimization) to the study of these functions. We give a new simple proof of local exactness of smooth penalty functions that significantly generalizes all similar results existing in the literature. We also provide new necessary and sufficient conditions for a smooth penalty function to be globally exact.     

Existence of optimal Lagrange multipliers for certain nonconvex allocation problems

The use of Lagrange multipliers for decentralization of large resource allocation problems is well known. However, these dual techniques may suffer from the drawback ofduality gaps, to guarantee the absence of which various functions are required to be convex. This limits greatly the applicability of the decentralized approach. We show that less restrictive conditions can be formulated for a certain class of allocation problems, which we call resource management problems, which typically occur in large operational systems. We present a theorem for the existence of optimal multipliers, while placing almost no restrictions on the forms of the resource usage functions or the domains of the decision variables. Efficient solution algorithms, with provable convergence properties, have been given in a companion paper. Our results justify the application of dual methods to this class ofreal-world problems.The author is indebted to Mr. G. Karady and Professor Y. C. Ho of Harvard University for their valuable comments, and also to the referees for their helpful suggestions. This research was partially supported by the Office of Naval Research, under the Joint Services Electronic Program, Contract No. N0001475-C-0648, and by the National Science Foundation, Grant No. ENG-78-15231.     

Lagrange multipliers and generalized differentiable functions in vector extremum problems

In this paper, we establish a necessary optimality condition for a nondifferentiable vector extremum problem which involves a generalized vector-valued Lagrangian function. Such a condition is stated for a wide class of functions, which embraces the differentiable ones and a subclass of locally Lipschitzian functions. The condition embodies the classic theorem of F. John in multiobjective optimization.This research was partially supported by the Ministry of Public Education, Rome, Italy.     

An approach to constrained global optimization based on exact penalty functions

In the field of global optimization many efforts have been devoted to solve unconstrained global optimization problems. The aim of this paper is to show that unconstrained global optimization methods can be used also for solving constrained optimization problems, by resorting to an exact penalty approach. In particular, we make use of a non-differentiable exact penalty function ${P_q(x;\varepsilon)}$ . We show that, under weak assumptions, there exists a threshold value ${\bar \varepsilon >0 }$ of the penalty parameter ${\varepsilon}$ such that, for any ${\varepsilon \in (0, \bar \varepsilon]}$ , any global minimizer of P _q is a global solution of the related constrained problem and conversely. On these bases, we describe an algorithm that, by combining an unconstrained global minimization technique for minimizing P _q for given values of the penalty parameter ${\varepsilon}$ and an automatic updating of ${\varepsilon}$ that occurs only a finite number of times, produces a sequence {x ^k } such that any limit point of the sequence is a global solution of the related constrained problem. In the algorithm any efficient unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. Some numerical experimentation confirms the effectiveness of the approach.     

Lagrange multipliers, (exact) regularization and error bounds for monotone variational inequalities

We examine two central regularization strategies for monotone variational inequalities, the first a direct regularization of the operative monotone mapping, and the second via regularization of the associated dual gap function. A key link in the relationship between the solution sets to these various regularized problems is the idea of exact regularization, which, in turn, is fundamentally associated with the existence of Lagrange multipliers for the regularized variational inequality. A regularization is said to be exact if a solution to the regularized problem is a solution to the unregularized problem for all parameters beyond a certain value. The Lagrange multipliers corresponding to a particular regularization of a variational inequality, on the other hand, are defined via the dual gap function. Our analysis suggests various conceptual, iteratively regularized numerical schemes, for which we provide error bounds, and hence stopping criteria, under the additional assumption that the solution set to the unregularized problem is what we call weakly sharp of order greater than one.     

An augmented mixed finite element method with Lagrange multipliers: A priori and a posteriori error analyses

In this paper, we provide a priori and a posteriori error analyses of an augmented mixed finite element method with Lagrange multipliers applied to elliptic equations in divergence form with mixed boundary conditions. The augmented scheme is obtained by including the Galerkin least-squares terms arising from the constitutive and equilibrium equations. We use the classical Babuška–Brezzi theory to show that the resulting dual-mixed variational formulation and its Galerkin scheme defined with Raviart–Thomas spaces are well posed, and also to derive the corresponding a priori error estimates and rates of convergence. Then, we develop a reliable and efficient residual-based a posteriori error estimate and a reliable and quasi-efficient Ritz projection-based one, as well. Finally, several numerical results illustrating the performance of the augmented scheme and the associated adaptive algorithms are reported.     

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.     

Slopes of shadow prices and Lagrange multipliers

Many economic models and optimization problems generate (endogenous) shadow prices—alias dual variables or Lagrange multipliers. Frequently the “slopes” of resulting price curves—that is, multiplier derivatives—are of great interest. These objects relate to the Jacobian of the optimality conditions. That particular matrix often has block structure. So, we derive explicit formulas for the inverse of such matrices and, as a consequence, for the multiplier derivatives.     

Existence of exact penalty for optimization problems with mixed constraints in Banach spaces

In this paper we use the penalty approach in order to study constrained minimization problems in a Banach space with nonsmooth nonconvex mixed constraints. A penalty function is said to have the exact penalty property [J.-B. Hiriart-Urruty, C. Lemarechal, Convex Analysis and Minimization Algorithms, Springer, Berlin, 1993] if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish sufficient conditions for the exact penalty property.     

A lower bound for the controlling parameters of the exact penalty functions

The purpose of this paper is to present new exact penalty functions and discuss their properties. A lower bound on the controlling parameters is given, for which above this value, the optimum of the exact penalty function coincides with the optimum of the nonlinear programming problem.This work was supported by the National Research Council of Canada under Grant A4414.     

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

罚函数方法是将约束优化问题转化为无约束优化问题的主要方法之一. 不包含目标函数和约束函数梯度信息的罚函数, 称为简单罚函数. 对传统精确罚函数而言, 如果它是简单的就一定是非光滑的; 如果它是光滑的, 就一定不是简单的. 针对等式约束优化问题, 提出一类新的简单罚函数, 该罚函数通过增加一个新的变量来控制罚项. 证明了此罚函数的光滑性和精确性, 并给出了一种解决等式约束优化问题的罚函数算法. 数值结果表明, 该算法对于求解等式约束优化问题是可行的.     

Lower bounds of controlling parameters of exact penalty functions in locally Lipschitz programming

In this note, lower bounds of penalty parameters of general exact penalty functions in locally Lipschitz programming are directly derived from Rosenberg's results.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

Properties of the Lagrange multipliers in the Pontryagin maximum principle for optimal control problems with state constraints

We study the Pontryagin maximum principle for an optimal control problem with state constraints. We analyze the continuity of a vector function µ (which is one of the Lagrange multipliers corresponding to an extremal by virtue of the maximum principle) at the points where the extremal trajectory meets the boundary of the set given by the state constraints. We obtain sufficient conditions for the continuity of µ in terms of the smoothness of the extremal trajectory.