On a Modified Subgradient Algorithm for Dual Problems via Sharp Augmented Lagrangian*

We study convergence properties of a modified subgradient algorithm, applied to the dual problem defined by the sharp augmented Lagrangian. The primal problem we consider is nonconvex and nondifferentiable, with equality constraints. We obtain primal and dual convergence results, as well as a condition for existence of a dual solution. Using a practical selection of the step-size parameters, we demonstrate the algorithm and its advantages on test problems, including an integer programming and an optimal control problem. *Partially Supported by 2003 UniSA ITEE Small Research Grant Ero2. Supported by CAPES, Brazil, Grant No. 0664-02/2, during her visit to the School of Mathematics and Statistics, UniSA.     

Comment on “A nonlinear Lagrangian dual for integer programming”

We present a counterexample and correction to the contention by Xu and Li that the nonlinear Lagrangian dual problem they propose [Oper. Res. Lett. 30 (2002) 401] asymptotically has no duality gap.     

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 dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

Bundle Relaxation and Primal Recovery in Unit Commitment Problems. The Brazilian Case

We consider the inclusion of commitment of thermal generation units in the optimal management of the Brazilian power system. By means of Lagrangian relaxation we decompose the problem and obtain a nondifferentiable dual function that is separable. We solve the dual problem with a bundle method. Our purpose is twofold: first, bundle methods are the methods of choice in nonsmooth optimization when it comes to solve large-scale problems with high precision. Second, they give good starting points for recovering primal solutions. We use an inexact augmented Lagrangian technique to find a near-optimal primal feasible solution. We assess our approach with numerical results.     

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.)     

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

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

Sensitivity analysis for the matching problem and its use in solving matching problems with a single side constraint

This paper develops certain sensitivity analysis capabilities for use with a primaldual matching code. The specific problem addressed is reoptimizing after the costs of a subset of the edges have been increased by a constant amount. This capability is applied to a dual ascent procedure for a Lagrangian relaxation of a matching problem with a single generalized upper bound side constraint. Some of the sensitivity analysis capabilities should be useful in other contexts as well. In particular, we give a method for solving for a set of dual variables that satisfy the strong complementary conditions given a blossom structure.Part of this work was performed while this author was visiting the University of Waterloo.     

A dual view of equilibrium problems

The aim of this paper is to introduce and study a dual problem associated to a generalized equilibrium problem (GEP). We show that the solutions of (GEP) and its dual are strictly related to the saddle points of an associated Lagrangian function, and, under some suitable conditions, to the solutions of a family of parametric optimization problems and their dual problems. Our results allow us to show that well-known concepts and results from duality theory of some important particular cases of (GEP) like variational inequalities and optimization problems can be recovered.     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

Comparison of Lagrangian bounds for one class of generalized assignment problems

Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are examined. For the class of generalized assignment problems, this property of constraints is used to design a Benders algorithm for solving the modified dual problem. Numerical results are presented that compare the quality of classical and modified bounds.     

New Lagrangian Relaxation Based Algorithm for Resource Scheduling with Homogeneous Subproblems

Solution oscillations, often caused by identical solutions to the homogeneous subproblems, constitute a severe and inherent disadvantage in applying Lagrangian relaxation based methods to resource scheduling problems with discrete decision variables. In this paper, the solution oscillations caused by homogeneous subproblems in the Lagrangian relaxation framework are identified and analyzed. Based on this analysis, the key idea to alleviate the homogeneous oscillations is to differentiate the homogeneous subproblems. A new algorithm is developed to solve the problem under the Lagrangian relaxation framework. The basic idea is to introduce a second-order penalty term in the Lagrangian. Since the dual cost function is no longer decomposable, a surrogate subgradient is used to update the multiplier at the high level. The homogeneous subproblems are not solved simultaneously, and the oscillations can be avoided or at least alleviated. Convergence proofs and properties of the new dual cost function are presented in the paper. Numerical testing for a short-term generation scheduling problem with two groups of identical units demonstrates that solution oscillations are greatly reduced and thus the generation schedule is significantly improved.     

Augmented Lagrangian Duality and Nondifferentiable Optimization Methods in Nonconvex Programming

In this paper we present augmented Lagrangians for nonconvex minimization problems with equality constraints. We construct a dual problem with respect to the presented here Lagrangian, give the saddle point optimality conditions and obtain strong duality results. We use these results and modify the subgradient and cutting plane methods for solving the dual problem constructed. Algorithms proposed in this paper have some advantages. We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies. The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the penalty like parameter to infinity in the new methods. In both methods the value of the dual function strongly increases at each iteration. In the contrast, by using the primal-dual gap, the proposed algorithms possess a natural stopping criteria. The convergence theorem for the subgradient method is also presented.     

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.     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

整数规划的渐进强对偶方法

虽然整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。该文提出一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索。     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

Duality Theory in Fuzzy Optimization Problems

A solution concept of fuzzy optimization problems, which is essentially similar to the notion of Pareto optimal solution (nondominated solution) in multiobjective programming problems, is introduced by imposing a partial ordering on the set of all fuzzy numbers. We also introduce a concept of fuzzy scalar (inner) product based on the positive and negative parts of fuzzy numbers. Then the fuzzy-valued Lagrangian function and the fuzzy-valued Lagrangian dual function for the fuzzy optimization problem are proposed via the concept of fuzzy scalar product. Under these settings, the weak and strong duality theorems for fuzzy optimization problems can be elicited. We show that there is no duality gap between the primal and dual fuzzy optimization problems under suitable assumptions for fuzzy-valued functions.