A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

An Estimation of Exact Penalty for Infinite-Dimensional Inequality-Constrained Minimization Problems

We use the penalty approach in order to study inequality-constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property 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 consider a large class of inequality-constrained minimization problems for which a constraint is a mapping with values in a normed ordered space. For this class of problems we introduce a new type of penalty functions, establish the exact penalty property and obtain an estimation of the exact penalty. Using this exact penalty property we obtain necessary and sufficient optimality conditions for the constrained minimization problems.     

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.     

Numerical solutions of the m-membranes problem

In this paper numerical approximation for the m-membrane problem is considered. We make a change of variables that leads to a different expression of the quadratic functional that allows after discretizing the problem to reformulate it as finite dimensional bound constrained quadratic problem. To our knowledge this is the first paper on numerical approximation of the m-membrane problem. We reformulate the m-membrane problem as a bound constraint quadratic minimization problem. The bound constraint quadratic form is solved with the gradient projection method.     

Nonlinear leastpth optimization and nonlinear programming

Over the past few years a number of researchers in mathematical programming became very interested in the method of the Augmented Lagrangian to solve the nonlinear programming problem. The main reason being that the Augmented Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a new method of solving the nonlinear programming problem, which has similar characteristics to the Augmented Lagrangian method. The original nonlinear programming problem is transformed into the minimization of a leastpth objective function which under certain conditions has the same optimum as the original problem. Convergence and rate of convergence of the new method is also proved. Furthermore numerical results are presented which illustrate the usefulness of the new approach to nonlinear programming.This work was supported by the National Research Council of Canada and by the Department of Combinatorics and Optimization of the University of Waterloo.     

Necessary and sufficient conditions for a penalty method to be exact

This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The conditions are given in terms of properties of the objective and constraint functions of the problem as well as the penalty function adopted. It is shown among other things that all linear programs with finite optimal value satisfy such conditions when the penalty function is quadratic.     

An iterative algorithm for sparse and constrained recovery with applications to divergence-free current reconstructions in magneto-encephalography

We propose an iterative algorithm for the minimization of a ? ₁-norm penalized least squares functional, under additional linear constraints. The algorithm is fully explicit: it uses only matrix multiplications with the three matrices present in the problem (in the linear constraint, in the data misfit part and in the penalty term of the functional). None of the three matrices must be invertible. Convergence is proven in a finite-dimensional setting. We apply the algorithm to a synthetic problem in magneto-encephalography where it is used for the reconstruction of divergence-free current densities subject to a sparsity promoting penalty on the wavelet coefficients of the current densities. We discuss the effects of imposing zero divergence and of imposing joint sparsity (of the vector components of the current density) on the current density reconstruction.     

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.     

Application of the hypodifferential descent method to the problem of constructing an optimal control

In this paper the problem of optimal control of a nonlinear ODE system with given boundary conditions and the integral restriction on control is considered. With the help of the theory of exact penalty functions the original problem is reduced to the problem of unconstrained minimization of a nonsmooth functional. The necessary minimum conditions in terms of hypodifferentials are found. A class of problems for which these conditions are also sufficient is distinguished. On the basis of these conditions the hypodifferential descent method is applied to the considered problem. Under some additional assumptions the hypodifferential descent method converges in a certain sense.     

Linear Programming with Uncertain Data: Some Extensions to Robust Optimization

An optimization problem often has some uncertain data, and the optimum of a linear program can be very sensitive to small changes in the data. Such a problem can often be modified to a robust program, which is more stable to such changes. Various methods for this are compared, including requiring all versions of the data to be satisfied together (but they may be inconsistent), worst-case MAX?CMIN model, and various models where deviations incur penalty costs. Existing methods require substantial computation. It is shown here that smaller computations often suffice; not all cases need be considered. Other penalty methods are suggested, using different norms. Moreover, perturbations of constraint coefficients can be represented by suitable perturbations of a requirement vector.     

A penalty approximation for a unilateral contact problem in non-linear elasticity

Using Ball's approach to non-linear elasticity, and in particular his concept of polyconvexity, we treat a unilateral three-dimensional contact problem for a hyperelastic body under volume and surface forces. Here the unilateral constraint is described by a sublinear function which can model the contact with a rigid convex cone. We obtain a solution to this generally non-convex, semicoercive Signorinin problem as a limit of solutions of related energy minimization problems involving friction normal to the contact surface where the friction coefficient goes to infinity. Thus we extend an approximation result of Duvaut and Lions for linear-elastic unilateral contact problems to finite deformations and to a class of non-linear elastic materials including the material models of Ogden and of Mooney-Rivlin for rubberlike materials. Moreover, the underlying penalty method is shown to be exact, that is a sufficiently large friction coefficient in the auxiliary energy minimization problems suffices to produce a solution of the original unilateral problem, provided a Lagrange multiplier to the unilateral constraint exists.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC ¹) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.     

A dimension-reduced method of sensitivity analysis for stochastic user equilibrium assignment model

This paper gives a new dimension-reduced method of sensitivity analysis for perturbed stochastic user equilibrium assignment (SUEA) model based on the relation between its Lagrange function and logarithmic barrier function combined with a Courant quadratic penalty term. The advantage of this method is of smaller dimension than general sensitivity analysis and reducing complexity. Firstly, it presents the dimension-reduced sensitivity results of the general nonlinear programming perturbation problem and the improved results when the objective or constraint functions are not twice continuously differentiable. Then it proves the corresponding conclusion of SUEA with smooth or non-smooth cost functions by the method of converting constraint conditions and decision variables. Finally, two corresponding examples (smooth and non-smooth) are given to illustrate the feasibility of this method.     

On the application of the residual method for the correction of inconsistent problems of convex programming

For the correction of a convex programming problem with potentially inconsistent constraint system (an improper problem), we apply the residual method, which is a standard regularization procedure for ill-posed optimization models. A problem statement typical for the residual method is reduced to a minimization problem for an appropriate penalty function. We apply two classical penalty functions: the quadratic penalty function and the exact Eremin-Zangwill penalty function. For each of the approaches, we establish convergence conditions and bounds for the approximation error.     

Existence of Exact Penalty and Its Stability for Nonconvex Constrained Optimization Problems in Banach Spaces

In this paper we use the penalty approach in order to study two constrained minimization problems. A penalty function is said to have the generalized exact penalty property if there is a penalty coefficient for which approximate solutions of the unconstrained penalized problem are close enough to approximate solutions of the corresponding constrained problem. In this paper we show that the generalized exact penalty property is stable under perturbations of cost functions, constraint functions and the right-hand side of constraints.     

Penalty methods for minimal surfaces with obstacles

Summary In this paper, we discuss an approach to the obstacle problem for minimal boundaries via penalty techniques. After investigating some classes of penalized problems, a general method is introduced, based on the minimization of a suitable functional containing an extra term related to the mean curvature of the given obstacle.     

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.     

关于约束极小化问题的一个新的简单精确罚函数

针对等式及不等式约束极小化问题,通过对原问题添加一个变量,给出一个新的简单精确罚函数,即在该精确罚函数表达式中,不含有目标函数及约束函数的梯度．在满足某些约束品性的条件下,可以证明:当罚参数充分大时,所给出的罚问题的局部极小点是原问题的局部极小点．     

On the global minimum in a balanced circular packing problem

The paper considers balanced packing problem of a given family of circles into a larger circle of the minimal radius as a multiextremal nonlinear programming problem. We reduce the problem to unconstrained minimization problem of a nonsmooth function by means of nonsmooth penalty functions. We propose an efficient algorithm to search for local extrema and an algorithm for improvement of the lower bound of the global minimum value of the objective function. The algorithms employ nonsmooth optimization methods based on Shor’s r-algorithm. Computational results are given.