pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

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.     

Generalized Nonlinear Lagrangian Formulation for Bounded Integer Programming

Several nonlinear Lagrangian formulations have been recently proposed for bounded integer programming problems. While possessing an asymptotic strong duality property, these formulations offer a success guarantee for the identification of an optimal primal solution via a dual search. Investigating common features of nonlinear Lagrangian formulations in constructing a nonlinear support for nonconvex piecewise constant perturbation function, this paper proposes a generalized nonlinear Lagrangian formulation of which many existing nonlinear Lagrangian formulations become special cases.     

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.     

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.     

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.     

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.     

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.     

本刊英文版Vol.30(2014),No.1论文摘要

<正>Analysis on a Superlinearly Convergent Augmented Lagrangian Method Ya Xiang YUAN Abstract The augmented Lagrangian method is a classical method for solving constrained optimization.Recently,the augmented Lagrangian method attracts much attention due to its applications to sparse optimization in compressive sensing and low rank matrix optimization problems.However,most Lagrangian methods use first order information to update the Lagrange multipliers,which lead to only linear convergence.In this paper,we study an update technique     

Duality for Multiobjective Optimization via Nonlinear Lagrangian Functions

In this paper, a strong nonlinear Lagrangian duality result is established for an inequality constrained multiobjective optimization problem. This duality result improves and unifies existing strong nonlinear Lagrangian duality results in the literature. As a direct consequence, a strong nonlinear Lagrangian duality result for an inequality constrained scalar optimization problem is obtained. Also, a variant set of conditions is used to derive another version of the strong duality result via nonlinear Lagrangian for an inequality constrained multiobjective optimization problem.     

Lagrangian actions for elliptical solutions of 2-body and 3-body problems with fixed energies

Based on the works of Gordon (1977) and Zhang and Zhou (2001) on the variational minimizing properties for Keplerian orbits and Lagrangian solutions of Newtonian 2-body and 3-body problems, we use the constrained variational principle of Ambrosetti and Coti Zelati (1990) to compute the Lagrangian actions on Keplerian and Lagrangian elliptical solutions with fixed energies. We also find an interesting relation between the period and the energy for Lagrangian elliptical solutions with Newtonian potentials.     

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.     

Surgery on Lagrangian and Legendrian Singularities

Let be a smooth fiber bundle whose total space is a symplectic manifold and whose fibers are Lagrangian. Let L be an embedded Lagrangian submanifold of E. In the paper we address the following question: how can one simplify the singularities of the projection by a Hamiltonian isotopy of L inside E? We give an answer in the case when dim and both L and M are orientable. A weaker version of the result is proved in the higher-dimensional case. Similar results hold in the contact category.?As a corollary one gets an answer to one of the questions of V. Arnold about the four cusps on the caustic in the case of the Lagrangian collapse. As another corollary we disprove Y. Chekanov's conjecture about singularities of the Lagrangian projection of certain Lagrangian tori in . Submitted: January 1998, revised: January 1999.     

On base manifolds of Lagrangian fibrations

We consider base spaces of Lagrangian fibrations from singular symplectic varieties.After defining cohomologically irreducible symplectic varieties,we construct an example of Lagrangian fibration whose base space is isomorphic to a quotient of the projective space.We also prove that the base space of Lagrangian fibration from a cohomologically symplectic variety is isomorphic to the projective space provided that the base space is smooth.     

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.     

A Modified Barrier-Augmented Lagrangian Method for Constrained Minimization

We present and analyze an interior-exterior augmented Lagrangian method for solving constrained optimization problems with both inequality and equality constraints. This method, the modified barrier—augmented Lagrangian (MBAL) method, is a combination of the modified barrier and the augmented Lagrangian methods. It is based on the MBAL function, which treats inequality constraints with a modified barrier term and equalities with an augmented Lagrangian term. The MBAL method alternatively minimizes the MBAL function in the primal space and updates the Lagrange multipliers. For a large enough fixed barrier-penalty parameter the MBAL method is shown to converge Q-linearly under the standard second-order optimality conditions. Q-superlinear convergence can be achieved by increasing the barrier-penalty parameter after each Lagrange multiplier update. We consider a dual problem that is based on the MBAL function. We prove a basic duality theorem for it and show that it has several important properties that fail to hold for the dual based on the classical Lagrangian.     

A weak version of the Lipman–Zariski conjecture

Markushevich and Tikhomirov provided a construction of an irreducible symplectic V-manifold of dimension 4, the relative compactified Prym variety of a family of curves with involution, which is a Lagrangian fibration with polarization of type (1,2). We give a characterization of the dual Lagrangian fibration. We also identify the moduli space of Lagrangian fibrations of this type and show that the duality defines a rational involution on it.     

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.     

Hofer’s metric on the space of Lagrangian submanifolds and wrapped Floer homology

In this paper, we study the relationship between wrapped Floer homology and displaceability of a Lagrangian submanifold which we call vanishing theorem of wrapped Floer homology. We also use this theorem to study Hofer’s pseudometric on the space of Lagrangian submanifolds. We prove an inequality, the Lagrangian version of the inequality of Gromov width and displacement energy, which is called energy-capacity inequality.