生成锥内部凸-锥-类凸集值优化问题的超有效性

本文讨论生成锥内部凸-锥-类凸集值向量优化问题的超有效解.在生成锥内部凸-锥类凸假设下,建立了集值向量优化问题在超有效意义下的标量化、Lagrangian乘子和鞍点定理     

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.     

Modified Lagrangian and Least Root Approaches for General Nonlinear Optimization Problems

Abstract In this paper we study nonlinear Lagrangian methods for optimization problems with side constraints.Nonlinear Lagrangian dual problems are introduced and their relations with the original problem are established.Moreover,a least root approach is investigated for these optimization problems.     

Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

Duality in nonlinear programs using augmented Lagrangian functions

A generally nonconvex optimization problem with equality constraints is studied. The problem is introduced as an “inf sup” of a generalized augmented Lagrangian function. A dual problem is defined as the “sup inf” of the same generalized augmented Lagrangian. Sufficient conditions are derived for constructing the augmented Lagrangian function such that the extremal values of the primal and dual problems are equal. Characterization of a class of augmented Lagrangian functions which satisfy the sufficient conditions for strong duality is presented. Finally, some examples of functions and primal-dual problems in the above-mentioned class are presented.     

Duality and Exact Penalization for Vector Optimization via Augmented Lagrangian

In this paper, we introduce an augmented Lagrangian function for a multiobjective optimization problem with an extended vector-valued function. On the basis of this augmented Lagrangian, set-valued dual maps and dual optimization problems are constructed. Weak and strong duality results are obtained. Necessary and sufficient conditions for uniformly exact penalization and exact penalization are established. Finally, comparisons of saddle-point properties are made between a class of augmented Lagrangian functions and nonlinear Lagrangian functions for a constrained multiobjective optimization problem.     

Connecting orbits among Denjoy minimal sets for monotone twist map

In a Birkhoff region of instability for an exact area-preserving twist map, we construct some orbits connecting distinct Denjoy minimal sets. These sets correspond to the local, instead of global minimum of the Lagrangian action. In the earlier work, Mather constructed connecting orbits among Aubry-Mather sets and the global minimizer of the Lagrangian action.     

Computing arbitrary Lagrangian Eulerian maps for evolving surfaces

The good mesh quality of a discretized closed evolving surface is often compromised during time evolution. In recent years this phenomenon has been theoretically addressed in a few ways, one of them uses arbitrary Lagrangian Eulerian (ALE) maps. However, the numerical computation of such maps still remained an unsolved problem in the literature. An approach, using differential algebraic problems, is proposed here to numerically compute an arbitrary Lagrangian Eulerian map, which preserves the mesh properties over time. The ALE velocity is obtained by finding an equilibrium of a simple spring system, based on the connectivity of the nodes in the mesh. We also consider the algorithmic question of constructing acute surface meshes. We present various numerical experiments illustrating the good properties of the obtained meshes and the low computational cost of the proposed approach.     

Super efficiency in vector optimization with nearly convexlike set-valued maps

In this paper, we establish a scalarization theorem and a Lagrange multiplier theorem for super efficiency in vector optimization problem involving nearly convexlike set-valued maps. A dual is proposed and duality results are obtained in terms of super efficient solutions. A new type of saddle point, called super saddle point, of an appropriate set-valued Lagrangian map is introduced and is used to characterize super efficiency.     

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.     

A nonlinear augmented Lagrangian for constrained minimax problems

A novel smooth nonlinear augmented Lagrangian for solving minimax problems with inequality constraints, is proposed in this paper, which has the positive properties that the classical Lagrangian and the penalty function fail to possess. The corresponding algorithm mainly consists of minimizing the nonlinear augmented Lagrangian function and updating the Lagrange multipliers and controlling parameter. It is demonstrated that the algorithm converges Q-superlinearly when the controlling parameter is less than a threshold under the mild conditions. Furthermore, the condition number of the Hessian of the nonlinear augmented Lagrangian function is studied, which is very important for the efficiency of the algorithm. The theoretical results are validated further by the preliminary numerical experiments for several testing problems reported at last, which show that the nonlinear augmented Lagrangian is promising.     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

Geometric conditions for Kuhn–Tucker sufficiency of global optimality in mathematical programming

We present geometric criteria for a feasible point that satisfies the Kuhn–Tucker conditions to be a global minimizer of mathematical programming problems with or without bounds on the variables. The criteria apply to multi-extremal programming problems which may have several local minimizers that are not global. We establish such criteria in terms of underestimators of the Lagrangian of the problem. The underestimators are required to satisfy certain geometric property such as the convexity (or a generalized convexity) property. We show that the biconjugate of the Lagrangian can be chosen as a convex underestimator whenever the biconjugate coincides with the Lagrangian at a point. We also show how suitable underestimators can be constructed for the Lagrangian in the case where the problem has bounds on the variables. Examples are given to illustrate our results.     

An exact algorithm for the capacitated facility location problems with single sourcing

Facility location problems are often encountered in many areas such as distribution, transportation and telecommunication. We describe a new solution approach for the capacitated facility location problem in which each customer is served by a single facility. An important class of heuristic solution methods for these problems are Lagrangian heuristics which have been shown to produce high quality solutions and at the same time be quite robust. A primal heuristic, based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied, is incorporated into the Lagrangian heuristic. Finally, a branch-and-bound method, based on the Lagrangian heuristic is developed, and compared computationally to the commercial code CPLEX. The computational results indicate that the proposed method is very efficient.     

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.     

A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem

We propose a Lagrangian heuristic for facility location problems with concave cost functions and apply it to solve the plant location and technology acquisition problem. The problem is decomposed into a mixed integer subproblem and a set of trivial single-variable concave minimization subproblems. We are able to give a closed-form expression for the optimal Lagrangian multipliers such that the Lagrangian bound is obtained in a single iteration. Since the solution of the first subproblem is feasible to the original problem, a feasible solution and an upper bound are readily available. The Lagrangian heuristic can be embedded in a branch-and-bound scheme to close the optimality gap. Computational results show that the approach is capable of reaching high quality solutions efficiently. The proposed approach can be tailored to solve many concave-cost facility location problems.     

向量映射的鞍点和Lagrange对偶问题

本文研究拓扑向量空间广义锥-次类凸映射向量优化问题的鞍点最优性条件和Lagrange对偶问题,建立向量优化问题的Fritz John鞍点和Kuhn-Tucker鞍点的最优性条件及其与向量优化问题的有效解和弱有效解之间的联系。通过对偶问题和向量优化问题的标量化刻画各解之间的关系,给出目标映射是广义锥-次类凸的向量优化问题在其约束映射满足广义Slater约束规格的条件下的对偶定理。     

Lagrangian bounds in multiextremal polynomial and discrete optimization problems

Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.     

Multiplier methods for optimization problems with Lipschitzian derivatives

Optimization problems for which the objective function and the constraints have locally Lipschitzian derivatives but are not assumed to be twice differentiable are examined. For such problems, analyses of the local convergence and the convergence rate of the multiplier (or the augmented Lagrangian) method and the linearly constraint Lagrangian method are given.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.