An intrinsic characterisation of polyhomogeneous Lagrangian distributions

The purpose of this paper is to present a method of characterising polyhomogeneous Lagrangian distributions via testing by pseudo-differential operators. The concept of a radial operator for a Lagrangian submanifold is introduced, and polyhomogeneous Lagrangian distributions are shown to be the only Lagrangian distributions which are eigenfunctions at the top order for these operators.

     

A Global Optimization Algorithm using Lagrangian Underestimates and the Interval Newton Method

Convex relaxations can be used to obtain lower bounds on the optimal objective function value of nonconvex quadratically constrained quadratic programs. However, for some problems, significantly better bounds can be obtained by minimizing the restricted Lagrangian function for a given estimate of the Lagrange multipliers. The difficulty in utilizing Lagrangian duality within a global optimization context is that the restricted Lagrangian is often nonconvex. Minimizing a convex underestimate of the restricted Lagrangian overcomes this difficulty and facilitates the use of Lagrangian duality within a global optimization framework. A branch-and-bound algorithm is presented that relies on these Lagrangian underestimates to provide lower bounds and on the interval Newton method to facilitate convergence in the neighborhood of the global solution. Computational results show that the algorithm compares favorably to the Reformulation–Linearization Technique for problems with a favorable structure.     

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 theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.     

On the Lagrangian form of the variational equations of Lagrangian dynamical systems

An extremal principle for obtaining the variational equations of a Lagrangian system is reviewed and formalized. Formalization is accomplished by relating the new Lagrangian function γ needed in such scheme to a prolongation of the original Lagrangian L. This formalization may be regarded as a necessary step before using the approach for stablishing nonintegrability of dynamical systems, or before applying it to analyse chaos-producing perturbations of integrable Lagrangian systems. The configuration manifold in which γ is defined is the double tangent bundle T(TQ) of the original configuration manifold Q modulo a flip mapping in such manifold. Our main result establishes that both the Euler–Lagrange equations and the corresponding variational equations of the original system can be viewed as the Lagrangian vector field associated with the composition of the first prolongation of the original Lagrangian with a flip mapping. Some applications of the approach to chaos and integrability issues are discussed.     

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.     

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai–Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.     

Singularities of Lagrangian mean curvature flow: zero-Maslov class case

We study singularities of Lagrangian mean curvature flow in ℂ ⁿ when the initial condition is a zero-Maslov class Lagrangian. We start by showing that, in this setting, singularities are unavoidable. More precisely, we construct Lagrangians with arbitrarily small Lagrangian angle and Lagrangians which are Hamiltonian isotopic to a plane that, nevertheless, develop finite time singularities under mean curvature flow. We then prove two theorems regarding the tangent flow at a singularity when the initial condition is a zero-Maslov class Lagrangian. The first one (Theorem A) states that that the rescaled flow at a singularity converges weakly to a finite union of area-minimizing Lagrangian cones. The second theorem (Theorem B) states that, under the additional assumptions that the initial condition is an almost-calibrated and rational Lagrangian, connected components of the rescaled flow converges to a single area-minimizing Lagrangian cone, as opposed to a possible non-area-minimizing union of area-minimizing Lagrangian cones. The latter condition is dense for Lagrangians with finitely generated H ₁(L,ℤ).     

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.     

Cup-length estimate for Lagrangian intersections

In this paper, we consider the Arnold conjecture on the Lagrangian intersections of some closed Lagrangian submanifold of a closed symplectic manifold with its image of a Hamiltonian diffeomorphism. We prove that if the Hofer's symplectic energy of the Hamiltonian diffeomorphism is less than a topology number defined by the Lagrangian submanifold, then the Arnold conjecture is true in the degenerated (nontransversal) case.     

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.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

Minimal Lagrangian submanifolds of the complex hyperquadric

We introduce a structural approach to study Lagrangian submanifolds of the complex hyperquadric in arbitrary dimension by using its family of non-integrable almost product structures.In particular,we define local angle functions encoding the geometry of the Lagrangian submanifold at hand.We prove that these functions are constant in the special case that the Lagrangian immersion is the Gauss map of an isoparametric hypersurface of a sphere and give the relation with the constant principal curvatures of the hypersurface.We also use our techniques to classify all minimal Lagrangian submanifolds of the complex hyperquadric which have constant sectional curvatures and all minimal Lagrangian submanifolds for which all local angle functions,respectively all but one,coincide.     

Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems

Lagrangian relaxations have been used in a variety of IP problem settings. The main thrust of such efforts is to obtain bounding information for use in a branch-and-bound procedure. This paper examines the effect of adding a single surrogate constraint to Lagrangian subproblems in an attempt to improve upon the bounds produced by conventional Lagrangian relaxation. Computational results on some randomly generated set-covering problems are reported.     

Closed characteristics on singular energy levels of second-order Lagrangian systems

We provide a lower bound on the number of closed characteristics on singular energy levels of second-order Lagrangian systems in the presence of saddle-focus equilibria. The hypotheses on the Lagrangian are mild, and the bound is given in terms of the number of saddle-foci and a potential function determined by the Lagrangian. The method of proof is variational, combining techniques to minimize near a saddle-focus and an analog of the method of broken geodesics.     

Pseudo-parallel Lagrangian submanifolds in complex space forms

In this work we study pseudo-parallel Lagrangian submanifolds in a complex space form. We give several general properties of pseudo-parallel submanifolds. For the 2-dimensional case, we show that any minimal Lagrangian surface is pseudo-parallel. We also give examples of non-minimal pseudo-parallel Lagrangian surfaces. Here we prove a local classification of the pseudo-parallel Lagrangian surfaces. In particular, semi-parallel Lagrangian surfaces are totally geodesic or flat. Finally, we give examples of pseudo-parallel Lagrangian surfaces which are not semi-parallel.     

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.     

Analysis of the one-dimensional Euler–Lagrange equation of continuum mechanics with a Lagrangian of a special form

The equations describing the flow of a one-dimensional continuum in Lagrangian coordinates are studied in this paper by the group analysis method. They are reduced to a single Euler–Lagrange equation which contains two undetermined functions (arbitrary elements). Particular choices of these arbitrary elements correspond to different forms of the shallow water equations, including those with both, a varying bottom and advective impulse transfer effect, and also some other motions of a continuum. A complete group classification of the equations with respect to the arbitrary elements is performed.One advantage of the Lagrangian coordinates consists of the presence of a Lagrangian, so that the equations studied become Euler–Lagrange equations. This allows us to apply Noether’s theorem for constructing conservation laws in Lagrangian coordinates. Not every conservation law in Lagrangian coordinates has a counterpart in Eulerian coordinates, whereas the converse is true. Using Noether’s theorem, conservation laws which can be obtained by the point symmetries are presented, and their analogs in Eulerian coordinates are given, where they exist.     

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.