Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

Saddle point and exact penalty representation for generalized proximal Lagrangians

In this paper, we introduce a generalized proximal Lagrangian function for the constrained nonlinear programming problem and discuss existence of its saddle points. In particular, the local saddle point is obtained by using the second-order sufficient conditions, and the global saddle point is given without requiring compactness of constraint set and uniqueness of the optimal solution. Finally, we establish equivalent relationship between global saddle points and exact penalty representations.     

Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming

This paper aims at showing that the class of augmented Lagrangian functions for nonlinear semidefinite programming problems can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem. By means of the image space analysis, a global saddle point condition for the augmented Lagrangian function is investigated. It is shown that the existence of a saddle point is equivalent to a regular nonlinear separation of two suitable subsets of the image space. Without requiring the strict complementarity, it is proved that, under second order sufficiency conditions, the augmented Lagrangian function admits a local saddle point. The existence of global saddle points is then obtained under additional assumptions that do not require the compactness of the feasible set. Motivated by the result on global saddle points, we propose two modified primal-dual methods based on the augmented Lagrangian using different strategies and prove their convergence to a global solution and the optimal value of the original problem without requiring the boundedness condition of the multiplier sequence.     

Saddle points of general augmented Lagrangians for constrained nonconvex optimization

Local and global saddle point conditions for a general augmented Lagrangian function proposed by Mangasarian are investigated in the paper for inequality and equality constrained nonconvex optimization problems. Under second order sufficiency conditions, it is proved that the augmented Lagrangian admits a local saddle point, but without requiring the strict complementarity condition. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the original problem.     

(p,r)-不变凸函数规划问题的鞍点定理

本文首先介绍了一个广义Lagrange向量函数L(x,u),并利用一类新的广义 凸函数:(p,r)——不变凸函数讨论了多目标分式规划问题的鞍点最优性条件．     

区间规划问题的最优性条件

区间规划是带有区间参数的规划问题,是一种更易于求解实际问题的柔性规划。它是确定性优化问题的延伸,有区间线性规划和区间非线性规划两种形式。本文讨论了目标函数是区间函数的区间非线性问题。给出了区间规划问题最优性必要条件的较简单证明方法,并利用LU最优解的概念,在一类广义凸函数－(p,r)－ρ－(η,θ)－不变凸函数定义下讨论了最优性充分条件。     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

Interior penalty functions and duality in linear programming

Logarithmic additive terms of barrier type with a penalty parameter are included in the Lagrange function of a linear programming problem. As a result, the problem of searching for saddle points of the modified Lagrangian becomes unconstrained (the saddle point is sought with respect to the whole space of primal and dual variables). Theorems on the asymptotic convergence to the desired solution and analogs of the duality theorems for the arising optimization minimax and maximin problems are formulated.     

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.     

Separation Approach for Augmented Lagrangians in Constrained Nonconvex Optimization

This paper aims at showing that the class of augmented Lagrangian functions, introduced by Rockafellar and Wets, can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem; hence, it is part of a more general theory. By means of the image space analysis, local and global saddle-point conditions for the augmented Lagrangian function are investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Under second-order sufficiency conditions in the image space, it is proved that the augmented Lagrangian admits a local saddle point. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set.     

On optimality and duality theorems of nonlinear disjunctive fractional minmax programs

This paper is concerned with the study of optimality conditions for disjunctive fractional minmax programming problems in which the decision set can be considered as a union of a family of convex sets. Dinkelbach’s global optimization approach for finding the global maximum of the fractional programming problem is discussed. Using the Lagrangian function definition for this type of problem, the Kuhn–Tucker saddle point and stationary-point problems are established. In addition, via the concepts of Mond–Weir type duality and Schaible type duality, a general dual problem is formulated and some weak, strong and converse duality theorems are proven.     

广义不变凸多目标半无限规划的鞍点条件

利用广义代数运算,定义了一类不变凸函数和不完全向量值Lagrange函数的鞍点,研究了涉及此类函数的多目标半无限规划问题,得到了广义鞍点的必要性和充分性条件.在更弱的凸性条件下,得到了几个重要结果.     

Convergence results for a self-dual regularization of convex problems

We study a one-parameter regularization technique for convex optimization problems whose main feature is self-duality with respect to the Legendre–Fenchel conjugation. The self-dual technique, introduced by Goebel, can be defined for both convex and saddle functions. When applied to the latter, we show that if a saddle function has at least one saddle point, then the sequence of saddle points of the regularized saddle functions converges to the saddle point of minimal norm of the original one. For convex problems with inequality and state constraints, we apply the regularization directly on the objective and constraint functions, and show that, under suitable conditions, the associated Lagrangians of the regularized problem hypo/epi-converge to the original Lagrangian, and that the associated value functions also epi-converge to the original one. Finally, we find explicit conditions ensuring that the regularized sequence satisfies Slater's condition.     

Saddle points and scalarizing sets in multiple objective linear programming

The main purpose of this paper is to study saddle points of the vector Lagrangian function associated with a multiple objective linear programming problem. We introduce three concepts of saddle points and establish their characterizations by solving suitable systems of equalities and inequalities. We deduce dual programs and prove a relationship between saddle points and dual solutions, which enables us to obtain an explicit expression of the scalarizing set of a given saddle point in terms of normal vectors to the value set of the problem. Finally, we present an algorithm to compute saddle points associated with non-degenerate vertices and the corresponding scalarizing sets.     

Saddle Points and Pareto Points in Multiple Objective Programming

In this paper relationships between Pareto points and saddle points are studied in convex and nonconvex multiple objective programming. The analysis is based on partitioning the index sets of objectives and constraints and splitting the original problem into subproblems having a special structure. The results are based on scalarizations of multiple objective programs and related linear and augmented Lagrangian functions. In the nonconvex case, a saddle point characterization of Pareto points is possible under assumptions that guarantee existence of Pareto points and stability conditions of single objective problems. Essentially, these conditions are not stronger than those in analogous results for single objective programming.This research was partially supported by ONR Grant N00014-97-1-784AMS Subject Classification: 90C29, 90C26     

On saddle points in nonconvex semi-infinite programming

In this paper we apply two convexification procedures to the Lagrangian of a nonconvex semi-infinite programming problem. Under the reduction approach it is shown that, locally around a local minimizer, this problem can be transformed equivalently in such a way that the transformed Lagrangian fulfills saddle point optimality conditions, where for the first procedure both the original objective function and constraints (and for the second procedure only the constraints) are substituted by their pth powers with sufficiently large power p. These results allow that local duality theory and corresponding numerical methods (e.g. dual search) can be applied to a broader class of nonconvex problems.     

Another approach to multiobjective programming problems withF-convex functions

In this paper, optimality conditions for multiobjective programming problems havingF-convex objective and constraint functions are considered. An equivalent multiobjective programming problem is constructed by a modification of the objective function. Furthermore, anF—Lagrange function is introduced for a constructed multiobjective programming problem, and a new type of saddle point is introduced. Some results for the new type of a saddle point are given.     

Existence of Augmented Lagrange Multipliers for Semi-infinite Programming Problems

Using an augmented Lagrangian approach, we study the existence of augmented Lagrange multipliers of a semi-infinite programming problem and discuss their characterizations in terms of saddle points. In the case of a sharp Lagrangian, we obtain a first-order necessary condition for the existence of an augmented Lagrange multiplier for the semi-infinite programming problem and some first-order sufficient conditions by assuming inf-compactness of the data functions and the extended Mangasarian–Fromovitz constraint qualification. Using a valley at 0 augmenting function and assuming suitable second-order sufficient conditions, we obtain the existence of an augmented Lagrange multiplier for the semi-infinite programming problem.     

Duality Theory for Optimization Problems with Interval-Valued Objective Functions

A solution concept in optimization problems with interval-valued objective functions, which is essentially similar to the concept of nondominated solution in vector optimization problems, is introduced by imposing a partial ordering on the set of all closed intervals. The interval-valued Lagrangian function and interval-valued Lagrangian dual function are also proposed to formulate the dual problem of the interval-valued optimization problem. Under this setting, weak and strong duality theorems can be obtained.     

Some Results on Augmented Lagrangians in Constrained Global Optimization via Image Space Analysis

The aim of this paper is to present some results for the augmented Lagrangian function in the context of constrained global optimization by means of the image space analysis. It is first shown that a saddle point condition for the augmented Lagrangian function is equivalent to the existence of a regular nonlinear separation in the image space. Local and global sufficient optimality conditions for the exact augmented Lagrangian function are then investigated by means of second-order analysis in the image space. Local optimality result for this function is established under second-order sufficiency conditions in the image space. Global optimality result is further obtained under additional assumptions. Finally, it is proved that the exact augmented Lagrangian method converges to a global solution–Lagrange multiplier pair of the original problem under mild conditions.