Lagrangian Duality for Minimization of Nonconvex Multifunctions

Two alternative type theorems for nearly convexlike or * quasiconvex multifunctions are presented. They are used to derive Lagrangian conditions and duality results for vector optimization problems when the objectives and the constraints are nearly convexlike or * quasiconvex multifunctions.     

On the Maximization of (not necessarily) Convex Functions on Convex Sets

The global solutions of the problem of maximizing a convex function on a convex set were characterized by several authors using the Fenchel (approximate) subdifferential. When the objective function is quasiconvex it was considered the differentiable case or used the Clarke subdifferential. The aim of the present paper is to give necessary and sufficient optimality conditions using several subdifferentials adequate for quasiconvex functions. In this way we recover almost all the previous results related to such global maximization problems with simple proofs.     

Diewert-Crouzeix conjugation for general quasiconvex duality and applications

A complicated factor in quasiconvex duality is the appearance of extra parameters. In order to avoid these extra parameters, one often has to restrict the class of quasiconvex functions. In this paper, by using the Diewert-Crouzeix conjugation, we present a duality without an extra parameter for general quasiconvex minimization problem. As an application, we prove a decentralization by prices for the Von Neumann equilibrium problem.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Duality and Exact Penalization for General Augmented Lagrangians

We consider a problem of minimizing an extended real-valued function defined in a Hausdorff topological space. We study the dual problem induced by a general augmented Lagrangian function. Under a simple set of assumptions on this general augmented Lagrangian function, we obtain strong duality and existence of exact penalty parameter via an abstract convexity approach. We show that every cluster point of a sub-optimal path related to the dual problem is a primal solution. Our assumptions are more general than those recently considered in the related literature.     

A smoothing augmented Lagrangian method for solving simple bilevel programs

In this paper, we design a numerical algorithm for solving a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint. We propose to solve a combined problem where the first order condition and the value function are both present in the constraints. Since the value function is in general nonsmooth, the combined problem is in general a nonsmooth and nonconvex optimization problem. We propose a smoothing augmented Lagrangian method for solving a general class of nonsmooth and nonconvex constrained optimization problems. We show that, if the sequence of penalty parameters is bounded, then any accumulation point is a Karush-Kuch-Tucker (KKT) point of the nonsmooth optimization problem. The smoothing augmented Lagrangian method is used to solve the combined problem. Numerical experiments show that the algorithm is efficient for solving the simple bilevel program.     

无限维空间拟凸映射多目标最优化问题解集的连通性

本文在一个无限格中引入了拟凸、强拟凸和严格拟凸映射。并在约束集为紧凸条件下，证明了相应的多目标规划问题之有效解集和弱有效解集连通性结果。     

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.     

On Equivalent Equilibrium Problems

We give sufficient conditions for the equivalence between two equilibrium problems. In particular we deduce that, under suitable assumptions, an equilibrium problem has an equivalent reformulation as a generalized variational inequality. Such conditions are satisfied when the equilibrium bifunction is lower semicontinuous, coercive and quasiconvex with respect to the second variable. We also show that the equivalent generalized variational inequality inherits the same generalized monotonicity properties of the original nonconvex equilibrium problem.     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

Characterizations of the solution set for non-essentially quasiconvex programming

Characterizations of the solution set in terms of subdifferentials play an important role in research of mathematical programming. Previous characterizations are based on necessary and sufficient optimality conditions and invariance properties of subdifferentials. Recently, characterizations of the solution set for essentially quasiconvex programming in terms of Greenberg–Pierskalla subdifferential are studied by the authors. Unfortunately, there are some examples such that these characterizations do not hold for non-essentially quasiconvex programming. As far as we know, characterizations of the solution set for non-essentially quasiconvex programming have not been studied yet. In this paper, we study characterizations of the solution set in terms of subdifferentials for non-essentially quasiconvex programming. For this purpose, we use Martínez–Legaz subdifferential which is introduced by Martínez–Legaz as a special case of c-subdifferential by Moreau. We derive necessary and sufficient optimality conditions for quasiconvex programming by means of Martínez–Legaz subdifferential, and, as a consequence, investigate characterizations of the solution set in terms of Martínez–Legaz subdifferential. In addition, we compare our results with previous ones. We show an invariance property of Greenberg–Pierskalla subdifferential as a consequence of an invariance property of Martínez–Legaz subdifferential. We give characterizations of the solution set for essentially quasiconvex programming in terms of Martínez–Legaz subdifferential.     

A two-well structure and intrinsic mountain pass points

Under small dead-load perturbations, and the natural boundary value condition (Neumann problem), we establish the existence of an unstable critical point (mountain pass point) for a variational integral with a two-well structure. The integrands we consider are obtained by the quasiconvex relaxation [18] of the squared distance function and its quasiconvex lower bounds. The models are m otivated by the variational approach to material microstructure when the wells are incompatible. We show that these functions give quasimonotone gradient mappings. We introduce the weak Palais-Smale condition (weak PS) to deal with the lack of compactness in the borderline case where the integrand is . Received March 1, 1999 / Accepted March 29, 2000 / Published online December 8, 2000     

一类Lagrangian对偶问题的零对偶间隙性质及其最优路径的收敛性

针对一般的非线性规划问题,利用某些Lagrange型函数给出了一类Lagrangian对偶问题的一般模型,并证明它与原问题之间存在零对偶间隙．针对具体的一类增广La- grangian对偶问题以及几类由非线性卷积函数构成的Lagrangian对偶问题,详细讨论了零对偶间隙的存在性．进一步,讨论了在最优路径存在的前提下,最优路径的收敛性质．     

Beyond polyconvexity: an existence result for a class of quasiconvex hyperelastic materials

This article contains an existence result for a class of quasiconvex stored energy functions satisfying the material non‐interpenetrability condition, which primarily obstructs applying classical techniques from the vectorial calculus of variations to nonlinear elasticity. The fundamental concept of reversibility serves as the starting point for a theory of nonlinear elasticity featuring the basic duality inherent to the Eulerian and Lagrangian points of view. Motivated by this concept, split‐quasiconvex stored energy functions are shown to exhibit properties, which are very alluding from a mathematical point of view. For instance, any function with finite energy is automatically a Sobolev homeomorphism; existence of minimizers can be readily established and first variation formulae hold. Copyright © 2016 John Wiley & Sons, Ltd.     

解非线性约束拟凸规划的一个梯度投影法

目前国内外所流行的梯度投影法(包括Rosen的原有算法和一些修正算法)还存在以下几个问题:一、要增加Polak程序以保证算法的收僉性。二、在计算投影梯度时,每步一般要作两次投影。三、对于非线性约束问题,负梯度投影方向是不可行的,因此必须在此方向的基础上构造出能保证算法收歛的新可行下降方向。而目前为构造出这个新方向所作的计算都比较复杂。 1981年[5]提出了一个处理线性约束条件的梯度投影法,基本上解决了线     

Convergence of the projected gradient method for quasiconvex multiobjective optimization

We consider the projected gradient method for solving the problem of finding a Pareto optimum of a quasiconvex multiobjective function. We show convergence of the sequence generated by the algorithm to a stationary point. Furthermore, when the components of the multiobjective function are pseudoconvex, we obtain that the generated sequence converges to a weakly efficient solution.     

Characterization of R-Evenly Quasiconvex Functions

A function defined on a locally convex space is called evenly quasiconvex if its level sets are intersections of families of open half-spaces. Furthermore, if the closures of these open halfspaces do not contain the origin, then the function is called R-evenly quasiconvex. In this note, R-evenly quasiconvex functions are characterized as those evenly-quasiconvex functions that satisfy a certain simple relation with their lower semicontinuous hulls.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

Scalarization of vector optimization problems

In this paper, we investigate the scalar representation of vector optimization problems in close connection with monotonic functions. We show that it is possible to construct linear, convex, and quasiconvex representations for linear, convex, and quasiconvex vector problems, respectively. Moreover, for finding all the optimal solutions of a vector problem, it suffices to solve certain scalar representations only. The question of the continuous dependence of the solution set upon the initial vector problems and monotonic functions is also discussed.The author is grateful to the two referees for many valuable comments and suggestions which led to major imporvements of the paper.     

Proximal Point Methods for Lipschitz Functions on Hadamard Manifolds: Scalar and Vectorial Cases

In the second part of our study, we introduce the concept of global extended exactness of penalty and augmented Lagrangian functions, and derive the localization principle in the extended form. The main idea behind the extended exactness consists in an extension of the original constrained optimization problem by adding some extra variables, and then construction of a penalty/augmented Lagrangian function for the extended problem. This approach allows one to design extended penalty/augmented Lagrangian functions having some useful properties (such as smoothness), which their counterparts for the original problem might not possess. In turn, the global exactness of such extended merit functions can be easily proved with the use of the localization principle presented in this paper, which reduces the study of global exactness to a local analysis of a merit function based on sufficient optimality conditions and constraint qualifications. We utilize the localization principle in order to obtain simple necessary and sufficient conditions for the global exactness of the extended penalty function introduced by Huyer and Neumaier, and in order to construct a globally exact continuously differentiable augmented Lagrangian function for nonlinear semidefinite programming problems.