Augmented Lagrangian method for distributed optimal control problems with state constraints

We consider state-constrained optimal control problems governed by elliptic equations. Doing Slater-like assumptions, we know that Lagrange multipliers exist for such problems, and we propose a decoupled augmented Lagrangian method. We present the algorithm with a simple example of a distributed control problem.     

Unified Nonlinear Lagrangian Approach to Duality and Optimal Paths

In the context of an inequality constrained optimization problem, we present a unified nonlinear Lagrangian dual scheme and establish necessary and sufficient conditions for the zero duality gap property. From these results, we derive necessary and sufficient conditions for four classes of zero duality gap properties and establish the equivalence among them. Finally, we obtain the convergence of an optimal path for the unified scheme and present a sufficient condition for the finite termination of the optimal path. This research was partially supported by the Research Grants Council of Hong Kong Grant PolyU 5250/03E, the National Natural Science Foundation of China Grants 10471159 and 10571106, NCET, and the Natural Science Foundation of Chongqing     

Properties of the Augmented Lagrangian in Nonlinear Semidefinite Optimization

We study the properties of the augmented Lagrangian function for nonlinear semidefinite programming. It is shown that, under a set of sufficient conditions, the augmented Lagrangian algorithm is locally convergent when the penalty parameter is larger than a certain threshold. An error estimate of the solution, depending on the penalty parameter, is also established.The first author was partially supported by Singapore-MIT Alliance and by the National University of Singapore under Grants RP314000-028/042/057-112. The second author was partially supported by the Funds of the Ministry of Education of China for PhD Units under Grant 20020141013 and the National Natural Science Foundation of China under Grant 10471015.     

Use of Augmented Lagrangian Methods for the Optimal Control of Obstacle Problems

We investigate optimal control problems governed by variational inequalities involving constraints on the control, and more precisely the example of the obstacle problem. In this paper, we discuss some augmented Lagrangian algorithms to compute the solution.     

A limiting Lagrangian for infinitely constrained convex optimization inR n

For convex optimization inR ⁿ,we show how a minor modification of the usual Lagrangian function (unlike that of the augmented Lagrangians), plus a limiting operation, allows one to close duality gaps even in the absence of a Kuhn-Tucker vector [see the introductory discussion, and see the discussion in Section 4 regarding Eq. (2)]. The cardinality of the convex constraining functions can be arbitrary (finite, countable, or uncountable).In fact, our main result (Theorem 4.3) reveals much finer detail concerning our limiting Lagrangian. There are affine minorants (for any value 0<1 of the limiting parameter ) of the given convex functions, plus an affine form nonpositive onK, for which a general linear inequality holds onR ⁿAfter substantial weakening, this inequality leads to the conclusions of the previous paragraph.This work is motivated by, and is a direct outgrowth of, research carried out jointly with R. J. Duffin.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR-047-048. This paper was presented at Constructive Approaches to Mathematical Models, a symposium in honor of R. J. Duffin, Pittsburgh, Pennsylvania, 1978. The author is grateful to Professor Duffin for discussions relating to the work reported here.The author wishes to thank R. J. Duffin for reading an earlier version of this paper and making numerous suggestions for improving it, which are incorporated here. Our exposition and proofs have profited from comments of C. E. Blair and J. Borwein.     

Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function

An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported.     

Separable Augmented Lagrangian Algorithm with Multidimensional Scaling for Monotropic Programming

We analyze a new decomposition approach for convex structured programs based on augmented Lagrangian functions with multiple scaling parameters. We obtain global convergence results with weak hypotheses. Numerical results are presented on a class of multicommodity flow problems; empirical choices of the scaling parameters updates are discussed. The authors gratefully acknowledge the help of J.-P. Crouzeix in simplifying the proof of the main convergence result.     

Validation of an Augmented Lagrangian Algorithm with a Gauss-Newton Hessian Approximation Using a Set of Hard-Spheres Problems

An Augmented Lagrangian algorithm that uses Gauss-Newton approximations of the Hessian at each inner iteration is introduced and tested using a family of Hard-Spheres problems. The Gauss-Newton model convexifies the quadratic approximations of the Augmented Lagrangian function thus increasing the efficiency of the iterative quadratic solver. The resulting method is considerably more efficient than the corresponding algorithm that uses true Hessians. A comparative study using the well-known package LANCELOT is presented.     

On the twice differentiable cubic augmented Lagrangian

Rockafellar's quadratic augmented Lagrangian for inequality constrained minimization is not twice differentiable. To eliminate this drawback, several quite complicated Lagrangians have been proposed. We exhibit a simple cubic Lagrangian that is twice differentiable. It stems from the recent work of Eckstein and Teboulle on Bregmanrelated Lagrangians.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

A convex-like duality scheme for quasi-convex programs

This paper describes a symmetric duality relation for quasi-convex programs. We are able to strengthen previous results and to define necessary and sufficient conditions for the absence of duality gap. In the present scheme one can generate quasi-convex quasi-concave Lagrangians and discuss the correspondence between saddle points of the Lagrangians and the solutions to the dual and primal programs. The present scheme is very similar to Rockafellar's scheme for convex programs and in this sense it may be viewed as a unified approach. Several examples are also given.     

Updating the Multipliers Associated with Inequality Constraints in an Augmented Lagrangian Multiplier Method

This paper contributes to the development of the field of augmented Lagrangian multiplier methods for general nonlinear programming by introducing a new update for the multipliers corresponding to inequality constraints. The update maintains naturally the nonnegativity of the multipliers without the need for a positive-orthant projection, as a result of the verification of the first-order necessary conditions for the minimization of a modified augmented Lagrangian penalty function.In the new multiplier method, the roles of the multipliers are interchanged: the multipliers corresponding to the inequality constraints are updated explicitly, whereas the multipliers corresponding to the equality constraints are approximated implicitly. It is shown that the basic properties of local convergence of the traditional multiplier method are valid also for the proposed method.     

The limiting Lagrangian as a consequence of Helly's theorem

The perturbational Lagrangian equation established by Jeroslow in convex semi-infinite programming is derived from Helly's theorem and some prior results on one-dimensional perturbations of convex programs.This research was partially supported by NRC, Grant No. A-4493.     

Sufficient conditions for duality in homogeneous programming

A symmetric duality theory for programming problems with homogeneous objective functions was published in 1961 by Eisenberg and has been used by a number of authors since in establishing duality theorems for specific problems. In this paper, we study a generalization of Eisenberg's problem from the viewpoint of Rockafellar's very general perturbation theory of duality. The extension of Eisenberg's sufficient conditions appears as a special case of a much more general criterion for the existence of optimal vectors and lack of a duality gap. We give examples where Eisenberg's sufficient condition is not satisfied, yet optimal vectors exist, and primal and dual problems have the same value.     

Approximate optimality conditions for minimax programming problems

In this article we study non-smooth Lipschitz programming problems with set inclusion and abstract constraints. Our aim is to develop approximate optimality conditions for minimax programming problems in absence of any constraint qualification. The optimality conditions are worked out not exactly at the optimal solution but at some points in a neighbourhood of the optimal solution. For this reason, we call the conditions as approximate optimality conditions. Later we extend the results in terms of the limiting subdifferentials in presence of an appropriate constraint qualification thereby leading to the optimality conditions at the exact optimal point.     

Limiting Lagrangians: A primal approach

In this paper, we consider a convex program with either a finite or an infinite number of constraints and its formal Lagrangian dual. We show that either the primal program satisfies a general condition which implies there is no duality gap or that there is a nonzero vectord with the following properties: First, wheneverd is added to the objective function, where is a positive number not greater than one, the resulting program satisfies the general sufficient condition cited above for no duality gap. Second, the optimal value of this perturbed program is attained and tends to the optimal value of the original program as tends to zero. Third, the optimal solutions of the perturbed programs form a minimizing sequence of the original program. As a consequence of the above, we derive the limiting Lagrangian theory of Borwein, Duffin, and Jeroslow.The authors are indebted to an unknown referee who suggested the very short and elegant proofs of Lemma 2.3 and Theorem 2.3.This work was completed while the first author was a member of the College of Management, Georgia Institute of Technology, Atlanta, Georgia.     

A generalized Lagrangian function and multiplier method

As is well known, a saddle point for the Lagrangian function, if it exists, provides a solution to a convex programming problem; then, the values of the optimal primal and dual objective functions are equal. However, these results are not valid for nonconvex problems.In this paper, several results are presented on the theory of the generalized Lagrangian function, extended from the classical Lagrangian and the generalized duality program. Theoretical results for convex problems also hold for nonconvex problems by extension of the Lagrangian function. The concept of supporting hypersurfaces is useful to add a geometric interpretation to computational algorithms. This provides a basis to develop a new algorithm.     

Two-Stage Approach for Quantitative Policy Analysis Using Bilevel Programming

Quantitative policy analysis problems with hierarchical decision-making can be modeled as bilevel mathematical programming problems. In general, the solution of these models is very difficult; however, special cases exist in which an optimal solution can be obtained by ordinary mathematical programming techniques. In this paper, a two-stage approach for the formulation, construction, solution, and usage of bilevel policy problem is presented. An outline of an example for analyzing Israel's public expenditure policy is also given.     

Augmented Lagrangian Duality and Nondifferentiable Optimization Methods in Nonconvex Programming

In this paper we present augmented Lagrangians for nonconvex minimization problems with equality constraints. We construct a dual problem with respect to the presented here Lagrangian, give the saddle point optimality conditions and obtain strong duality results. We use these results and modify the subgradient and cutting plane methods for solving the dual problem constructed. Algorithms proposed in this paper have some advantages. We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies. The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the penalty like parameter to infinity in the new methods. In both methods the value of the dual function strongly increases at each iteration. In the contrast, by using the primal-dual gap, the proposed algorithms possess a natural stopping criteria. The convergence theorem for the subgradient method is also presented.     

Perturbation Approach to Sensitivity Analysis in Mathematical Programming

This paper presents a perturbation approach for performing sensitivity analysis of mathematical programming problems. Contrary to standard methods, the active constraints are not assumed to remain active if the problem data are perturbed, nor the partial derivatives are assumed to exist. In other words, all the elements, variables, parameters, Karush–Kuhn–Tucker multipliers, and objective function values may vary provided that optimality is maintained and the general structure of a feasible perturbation (which is a polyhedral cone) is obtained. This allows determining: (a) the local sensitivities, (b) whether or not partial derivatives exist, and (c) if the directional derivative for a given direction exists. A method for the simultaneous obtention of the sensitivities of the objective function optimal value and the primal and dual variable values with respect to data is given. Three examples illustrate the concepts presented and the proposed methodology. Finally, some relevant conclusions are drawn. The authors are indebted to the Ministry of Science and Education of Spain, Projects CICYT DPI2002-04172-C04-02 and CICYT DPI2003-01362, and to the Fulbright Commission for partial support. The authors are grateful to the referees for comments improving the quality of the paper.     

Duality for Multiobjective Optimization via Nonlinear Lagrangian Functions

In this paper, a strong nonlinear Lagrangian duality result is established for an inequality constrained multiobjective optimization problem. This duality result improves and unifies existing strong nonlinear Lagrangian duality results in the literature. As a direct consequence, a strong nonlinear Lagrangian duality result for an inequality constrained scalar optimization problem is obtained. Also, a variant set of conditions is used to derive another version of the strong duality result via nonlinear Lagrangian for an inequality constrained multiobjective optimization problem.