Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

New formulation of iterative substructuring methods without Lagrange multipliers: Neumann–Neumann and FETI

This article is devoted to introduce a new approach to iterative substructuring methods that, without recourse to Lagrange multipliers, yields positive definite preconditioned formulations of the Neumann–Neumann and FETI types. To my knowledge, this is the first time that such formulations have been made without resource to Lagrange multipliers. A numerical advantage that is concomitant to such multipliers‐free formulations is the reduction of the degrees of freedom associated with the Lagrange multipliers. Other attractive features are their generality, directness, and simplicity. The general framework of the new approach is rather simple and stems directly from the discretization procedures that are applied; in it, the differential operators act on discontinuous piecewise‐defined functions. Then, the Lagrange multipliers are not required because in such an environment the functions‐discontinuities are not an anomaly that need to be corrected. The resulting algorithms and equations‐systems are also derived with considerable detail. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

两个泛函优化定理的证明

在泛函优化理论中,Lagrange乘子定理、对偶定理占有重要地位.建立了带有等式和不等式约束的泛函优化问题,并给出了广义Lagrange乘子定理、广义Lagrange对偶定理的证明.     

Error analysis of variable degree mixed methods for elliptic problems via hybridization

A new approach to error analysis of hybridized mixed methods is proposed and applied to study a new hybridized variable degree Raviart-Thomas method for second order elliptic problems. The approach gives error estimates for the Lagrange multipliers without using error estimates for the other variables. Error estimates for the primal and flux variables then follow from those for the Lagrange multipliers. In contrast, traditional error analyses obtain error estimates for the flux and primal variables first and then use it to get error estimates for the Lagrange multipliers. The new approach not only gives new error estimates for the new variable degree Raviart-Thomas method, but also new error estimates for the classical uniform degree method with less stringent regularity requirements than previously known estimates. The error analysis is achieved by using a variational characterization of the Lagrange multipliers wherein the other unknowns do not appear. This approach can be applied to other hybridized mixed methods as well.

     

Preparation of papers

Recent studies are concerned with two types of questions in nonconvex optimization: (a) conditions for having bounded Lagrange multipliers, Refs. 1–2; (b) a priori bounds for such Lagrange multipliers, Ref. 3. Such topics have been investigated under suitable regularity assumptions. The purpose of this paper is to study the same problems for the generalized Lagrange multipliers of a locally Lipschitz programming.The author thanks the referees for helpful suggestions     

On the Genesis of the Lagrange Multipliers

The genesis of the Lagrange multipliers is analyzed in this work. Particularly, the author shows that this mathematical approach was introduced by Lagrange in the framework of statics in order to determine the general equations of equilibrium for problems with constraints. Indeed, the multipliers allowed Lagrange to treat the questions of maxima and minima in differential calculus and in calculus of variations in the same way as problems of statics: if the equilibrium of a point or a system of points is required, there is an analogy between statics and differential calculus; if the equilibrium of a rigid body is required, there is an analogy between statics and calculus of variations.     

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

该文讨论局部凸空间中的约束集值优化问题. 首先, 在生成锥内部凸-锥-类凸假设下, 建立了Henig真有效解在标量化和Lagrange乘子意义下的最优性条件. 其次, 对集值Lagrange映射引入Henig真鞍点的概念, 并用这一概念刻画了Henig真有效解. 最后, 引入了一个标量Lagrange对偶模型, 并得到了关于Henig真有效解的对偶定理. 另外, 该文所得结果均不需要约束序锥有非空的内部.     

Lagrange Multiplier Conditions Characterizing the Optimal Solution Sets of Cone-Constrained Convex Programs

Various characterizations of optimal solution sets of cone-constrained convex optimization problems are given. The results are expressed in terms of subgradients and Lagrange multipliers. We establish first that the Lagrangian function of a convex program is constant on the optimal solution set. This elementary property is then used to derive various simple Lagrange multiplier-based characterizations of the solution set. For a finite-dimensional convex program with inequality constraints, the characterizations illustrate that the active constraints with positive Lagrange multipliers at an optimal solution remain active at all optimal solutions of the program. The results are applied to derive corresponding Lagrange multiplier characterizations of the solution sets of semidefinite programs and fractional programs. Specific examples are given to illustrate the nature of the results.     

Existence of augmented Lagrange multipliers for cone constrained optimization problems

In this paper, by using an augmented Lagrangian approach, we obtain several sufficient conditions for the existence of augmented Lagrange multipliers of a cone constrained optimization problem in Banach spaces, where the corresponding augmenting function is assumed to have a valley at zero. Furthermore, we deal with the relationship of saddle points, augmented Lagrange multipliers, and zero duality gap property between the cone constrained optimization problem and its augmented Lagrangian dual problem.     

Lagrangian formulation of domain decomposition methods: A unified theory

Domain decomposition methods based on one Lagrange multiplier have been shown to be very efficient for solving ill-conditioned problems in parallel. Several variants of these methods have been developed in the last ten years. These variants are based on an augmented Lagrangian formulation involving one or two Lagrange multipliers and on mixed type interface conditions between the sub-domains. In this paper, the Lagrangian formulations of some of these domain decomposition methods are presented both from a continuous and a discrete point of view.     

对合变换和薄板弯曲问题的多变量变分原理

本文利用拉氏乘子法把薄板弯曲问题的最小位能原理和最小余能原理的变分约束条件解除.从而导出了常见的广义变分原理.为了降低泛函中变量导数的阶次.我们用对合变换引进新的正则变量.于是,我们可以进一步利用拉氏乘子法,把这些对合变换当作变分约束而予以消除,从而导出了各种多变量的薄板弯曲广义变分原理.事实证明,使用上述拉氏乘子法,并不能消除一切变分约束;为此,我们进一步引用高阶拉氏乘子法消除这些剩下来的约束条件,从而导得了薄板弯曲问题的更一般的广义变分原理.     

Motion equations of cooperative multi flexible mobile manipulator via recursive Gibbs–Appell formulation

In this paper, the developed model of an N-flexible-link mobile manipulator with revolute-prismatic joints is presented for the cooperative flexible multi mobile manipulator. In this model, the deformation of flexible links is calculated by using the assumed modes method. In additions, non-holonomic constraints of the robots’ mobile platforms that bound its locomotion are considered. This limitation is alleviated through the concurrent motion of revolute and prismatic joints, although it results in computational complexity and changes the final motion equations to time-varying form. Not only is the proposed dynamic model implemented for the multi-mobile manipulators with arms having independent motion, but also for multi-mobile manipulators in cooperation after defining gripper's kinematic constraints. These constraints are imported to the dynamic equations by defining Lagrange multipliers. The recursive Gibbs–Appell formulation is preferred over other similar approaches owing to the capability of solving the equations without the need to use Lagrange multipliers for eliminating non-holonomic constraints in addition to the novel optimized process of obtaining system equations. Hence, cumbersome simultaneous computations for eliminating the constraints of platform and arms are circumvented. Therefore, this formulation is improved for the first time by importing Lagrange multipliers for solving kinematic constrained systems. In the simulation section, the results of forward dynamics solution for two flexible single-arm manipulators with revolute-prismatic joints while carrying a rigid object are presented. Inverse dynamics equations of the system are also presented to obtain the maximum dynamic load-carrying capacity of the two-rigid-link mobile manipulators on a predefined path. Two constraints, namely the capacity of joint motors torque and robot motion stability are considered as the limitation criteria. The concluded motion equations are used to accurately control the movement of sensitive bodies, which is not achievable through the use of one platform.     

On a characterization of convergence for the Hestenes method of multipliers

The connection between the convergence of the Hestenes method of multipliers and the existence of augmented Lagrange multipliers for the constrained minimum problem (P): minimizef(x), subject tog(x)=0, is investigated under very general assumptions onX,f, andg.In the first part, we use the existence of augmented Lagrange multipliers as a sufficient condition for the convergence of the algorithm. In the second part, we prove that this is also a necessary condition for the convergence of the method and the boundedness of the sequence of the multiplier estimates.Further, we give very simple examples to show that the existence of augmented Lagrange multipliers is independent of smoothness condition onf andg. Finally, an application to the linear-convex problem is given.     

从几何角度给予拉格朗日乘数法新的推导思路

拉格朗日乘数法是求条件极值的重要方法,该文通过数形结合给出定理推导的新路径,相比教材上纯代数推导更直观,体现了"几何意义"的重要性.     

Least‐square collocation and Lagrange multipliers forTaylor meshless method

A recently proposed meshless method is discussed in this article. It relies on Taylor series, the shape functions being high degree polynomials deduced from the Partial Differential Equation (PDE). In this framework, an efficient technique to couple several polynomial approximations has been presented in (Tampango, Potier‐Ferry, Koutsawa, Tiem, Int. J. Numer. Meth. Eng. vol. 95 (2013) pp. 1094–1112): the boundary conditions were applied using the least‐square collocation and the interface was coupled by a bridging technique based on Lagrange multipliers. In this article, least‐square collocation and Lagrange multipliers are applied for boundary conditions, respectively, and least‐square collocation is revisited to account for the interface conditions in piecewise resolutions. Various combinations of these two techniques have been investigated and the numerical results prove their effectiveness to obtain very accurate solutions, even for large scale problems.     

Non-linearity of multibody dynamic equations with respect to Lagrange multipliers: application to railway dynamics

In this paper, the dynamics of multibody systems with closed kinematical chains of bodies is considered. The main focus is set on non-linearity of the multibody equations with respect to the Lagrange multipliers. When closed chains are considered, loop cutting procedure is a solution to express the constraint equations associated with the loops. Dynamic equations of the multibody tree-like structure are thus completed with the constraint forces via the Lagrange multipliers. In the considered case of railway vehicles, constraints arise from the contact between the rigid wheels and the rails. Corresponding contact forces applied to the wheels appears via the Lagrange multipliers λ and the tangent creep forces as well. Resulting differential-algebraic equations can be transformed into an ODE system and then time-integrated using the coordinate partitioning method [3], when the system is linear with respect to λ. This paper presents an algorithm allowing us to solve this system in case of nonlinearities with respect to λ, which is typical of wheel/rail contact force models. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Variational iteration method for the Burgers’ flow with fractional derivatives—New Lagrange multipliers

The flow through porous media can be better described by fractional models than the classical ones since they include inherently memory effects caused by obstacles in the structures. The variational iteration method was extended to find approximate solutions of fractional differential equations with the Caputo derivatives, but the Lagrange multipliers of the method were not identified explicitly. In this paper, the Lagrange multiplier is determined in a more accurate way and some new variational iteration formulae are presented.     

Generating pareto-optimal alternatives by a nonfeasible hierarchical method

A hierarchical algorithm for generating Pareto-optimal alternatives for convex multicriteria problems is derived. At the upper level, values for Lagrange multipliers of the coupling constraints are first given. Then at the subsystems, Pareto-optimal values are determined for the subsystem objectives, whereby an additional term or an additional objective is included due to the Lagrange multipliers. In the subsystem optimizations, the coupling equations between the subsystems are not satisfied; therefore, the method is called nonfeasible. Finally, the upper level checks which of the subsystem solutions satisfy the coupling constraints; these solutions are Pareto-optimal solutions for the overall system.     

Linear programming based decomposition methods for inventory distribution systems

We consider an inventory distribution system consisting of one warehouse and multiple retailers. The retailers face random demand and are supplied by the warehouse. The warehouse replenishes its stock from an external supplier. The objective is to minimize the total expected replenishment, holding and backlogging cost over a finite planning horizon. The problem can be formulated as a dynamic program, but this dynamic program is difficult to solve due to its high dimensional state variable. It has been observed in the earlier literature that if the warehouse is allowed to ship negative quantities to the retailers, then the problem decomposes by the locations. One way to exploit this observation is to relax the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers with them, which naturally raises the question of how to choose a good set of Lagrange multipliers. In this paper, we propose efficient methods that choose a good set of Lagrange multipliers by solving linear programming approximations to the inventory distribution problem. Computational experiments indicate that the inventory replenishment policies obtained by our approach can outperform several standard benchmarks by significant margins.     

一个求解条件极值问题的极值点的新方法

利用齐次线性方程组理论,建立了一个求解条件极值问题的极值点的新方法.该方法的优点是:能有效地避免在运用Lagrange乘数法求解条件极值时,因引进了参数而给解方程组带来的困扰.也可以说,对于有些问题我们仅从已知条件入手,不必引进参数就可以直接求得极值点.