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.     

Characterizing an optimal input in perturbed convex programming

When every feasible stable perturbation of data results in a non-improvement of the optimal value function, then we talk about an ‘optimal input’ or an ‘optimal selection of data”. In this paper we describe such data for convex programs using perturbed saddle points. Research partly supported by Natural Sciences and Engineering Council of Canada and le Ministère de l'Education du Québec (F.C.A.C.). Presented in part at the Third Symposium on Mathematical Programming with Data Perturbations, The George Washington University, Washington, D.C. (May 21–22, 1981).     

Nondifferentiable optimization in banach space

Necessary optimality conditions for nondifferentiable optimization problems in Banach spaces with its objective function and constraint function valued in a partial ordered vector space are given. The main results are obtained with the help of several Farkas type alternative theorems, one of them is proven in the paper for the first time only under a strict separation axiom of convex sets.     

Refinement of Lagrangian bounds in optimization problems

Lagrangian constraint relaxation and the corresponding bounds for the optimal value of an original optimization problem are examined. Techniques for the refinement of the classical Lagrangian bounds are investigated in the case where the complementary slackness conditions are not fulfilled because either the original formulation is nonconvex or the Lagrange multipliers are nonoptimal. Examples are given of integer and convex problems for which the modified bounds improve the classical Lagrangian bounds.     

First and second order conditions for a class of nondifferentiable optimization problems

This paper gives first and in particular second order necessary and sufficient conditions for a class of nondifferentiable optimization problems in which there are both objective and constraint functions defined in terms of a norm. The conditions are expressed in terms of a Lagrangian function and its derivatives, and use the ideas of feasible directional sequence and subgradients. Certain regularity assumptions are required and for the second order necessary conditions it is shown that the assumption is realistic for polyhedral norms. Illustrative examples are discussed.     

A new augmented Lagrangian function for inequality constraints in nonlinear programming problems

In this paper, a new augmented Lagrangian function is introduced for solving nonlinear programming problems with inequality constraints. The relevant feature of the proposed approach is that, under suitable assumptions, it enables one to obtain the solution of the constrained problem by a single unconstrained minimization of a continuously differentiable function, so that standard unconstrained minimization techniques can be employed. Numerical examples are reported.     

On the theory of Lagrangian duality

It is shown that a general Lagrangian duality theory for constrained extremum problems can be drawn from a separation scheme in the Image Space, namely in the space where the functions of the given problem run.     

On the Geometry of Lagrangian Submanifolds

We prove that a Lagrangian submanifold passes through each point of a symplectic manifold in the direction of arbitrary Lagrangian plane at this point. Generally speaking, such a Lagrangian submanifold is not unique; nevertheless, the set of all such submanifolds in Hermitian extension of a symplectic manifold of dimension greater than 4 for arbitrary initial data contains a totally geodesic submanifold (which we call the s-Lagrangian submanifold) iff this symplectic manifold is a complex space form. We show that each Lagrangian submanifold in a complex space form of holomorphic sectional curvature equal to c is a space of constant curvature c/4. We apply these results to the geometry of principal toroidal bundles.     

On the equality of quasi-arithmetic and Lagrangian means

The paper deals with the equality problem of quasi-arithmetic and Lagrangian means which is to determine all pairs of continuous strictly monotone functions φ,ψ:I→R such that, for all x,y∈I,

     

Generalization of some duality theorems in nonlinear programming

Pseudoconvexity of a function on one set with respect to some other set is defined and duality theorems are proved for nonlinear programming problems by assuming a certain kind of convexity property for a particular linear combination of functions involved in the problem rather than assuming the convexity property for the individual functions as is usually done. This approach generalizes some of the well-known duality theorems and gives some additional strict converse duality theorems which are not comparable with the earlier duality results of this type. Further it is shown that the duality theory for nonlinear fractional programming problems follows as a particular case of the results established here.     

Lagrangian Spheres in the Complex Euclidean Space Satisfying a Geometric Equality

For a Lagrangian submanifold of Cⁿ with scalar curvature and mean curvature vector H, the inequality ( n²(n-1)/n+2 |H|²) holds, and the equality is given only in open sets of the Lagrangian subspaces of ⁿ or of the Whitney sphere (cf. [RU] and also [BCM]). In this paper, a one-parameter family of Lagrangian spheres including the Whitney sphere is constructed. They satisfy a geometric equality of type = |H|², with >0, and they are globally characterized inside the family of compact Lagrangian submanifolds with null first Betti number in Cⁿ.     

On a primal-proximal heuristic in discrete optimization

Lagrangian relaxation is useful to bound the optimal value of a given optimization problem, and also to obtain relaxed solutions. To obtain primal solutions, it is conceivable to use a convexification procedure suggested by D.P. Bertsekas in 1979, based on the proximal algorithm in the primal space.The present paper studies the theory assessing the approach in the framework of combinatorial optimization. Our results indicate that very little can be expected in theory, even though fairly good practical results have been obtained for the unit-commitment problem.     

On the efficiency of multiplier methods for nonlinear network problems with nonlinear constraints

The minimization of network flow problems with linear/nonlinearside constraints can be performed by minimizing an augmentedLagrangian function, including only the side constraints. Thismethod gives rise to an algorithm that combines first- and superlinear-orderestimators of the multipliers of the side constraints. The codePFNRN03 is the implementation of this algorithm in Fortran 77.The main aim of this work is to compare the efficiency of thiscode on two sets of (industrial, artificial) test problems withthat of the general-purpose solvers MINOS, SNOPT, LANCELOT andLOQO. Numerical results of these four codes are obtained bythe NEOS server with AMPL input. The comparison indicates thatPFNRN03 may be effective on current large-scale network flowproblems with nonlinear side constraints.     

On uniqueness of Kuhn-Tucker multipliers in nonlinear programming

Recently Fujiwara, Han and Mangasarian introduced a new constraint qualification which is a slight tightening of the well-known Mangasarian—Fromovitz constraint qualification. We show that this new qualification is a necessary and sufficient condition for the uniqueness of Kuhn—Tucker multipliers. We also show that it implies the satisfaction of second order necessary optimality conditions at a local minimum.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

The fundamental continuity theory of optimization on a compact space. I

Optimizers on a compact feasible region are abstractly specified and, as set-valued mappings, are studied for sufficient conditions yielding them (as well as certain associated maps and certain restrictions of all these) continuous, using function space methods. In particular, the study concerns the continuity of the set of optimal solutions as a function of the three arguments: (i) objective function used, (ii) an incentive (or penalty/reward) function imposed, and (iii) an abstract parameter. An interpretation of the mathematical apparatus is suggested and a brief game-theoretic illustration is given.     

Image of a parametric optimization problem and continuity of the perturbation function

In this note, we consider the notion of the image of a parametric optimization problem and show that the lower semicontinuity and upper semicontinuity properties of its marginal function can be equivalently expressed as two geometric relations in the image space. These results generalize some existing statements in the literature.