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.     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

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

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

Perturbing the Dual Feasible Region for Solving Convex Quadratic Programs

A dual l _p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l _p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.     

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.     

The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC ¹) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.     

Convergent Lagrangian and domain cut method for nonlinear knapsack problems

The nonlinear knapsack problem, which has been widely studied in the OR literature, is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to separable nondecreasing constraints. In this paper we develop a convergent Lagrangian and domain cut method for solving this kind of problems. The proposed method exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the finding of an optimal exact solution to the primal problem. The algorithm is first motivated and developed for singly constrained nonlinear knapsack problems and is then extended to multiply constrained nonlinear knapsack problems. Computational results are presented for a variety of medium- or large-size nonlinear knapsack problems. Comparison results with other existing methods are also reported.     

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.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results

In a multiperiod dynamic network flow problem, we model uncertain arc capacities using scenario aggregation. This model is so large that it may be difficult to obtain optimal integer or even continuous solutions. We develop a Lagrangian decomposition method based on the structure recently introduced in G.D. Glockner and G.L. Nemhauser, Operations Research, vol. 48, pp. 233–242, 2000. Our algorithm produces a near-optimal primal integral solution and an optimum solution to the Lagrangian dual. The dual is initialized using marginal values from a primal heuristic. Then, primal and dual solutions are improved in alternation. The algorithm greatly reduces computation time and memory use for real-world instances derived from an air traffic control model.     

A note on the existence of saddle points of p-th power Lagrangian for constrained nonconvex optimization

Li and Sun [D. Li and X.L. Sun, Existence of a saddle point in nonconvex constrained optimization, J. Global Optim. 21 (2001), pp. 39--50; D. Li and X.L. Sun, Convexification and existence of saddle point in a p-th-power reformulation for nonconvex constrained optimization, Nonlinear Anal. 47 (2001), pp. 5611--5622], present the existence of a global saddle point of the p-th power Lagrangian functions for constrained nonconvex optimization, under second-order sufficiency conditions and additional conditions that the feasible set is compact and the global solution of the primal problem is unique. In this article, it is shown that the same results can be obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the primal problem.     

A primal dual modified subgradient algorithm with sharp Lagrangian

We apply a modified subgradient algorithm (MSG) for solving the dual of a nonlinear and nonconvex optimization problem. The dual scheme we consider uses the sharp augmented Lagrangian. A desirable feature of this method is primal convergence, which means that every accumulation point of a primal sequence (which is automatically generated during the process), is a primal solution. This feature is not true in general for available variants of MSG. We propose here two new variants of MSG which enjoy both primal and dual convergence, as long as the dual optimal set is nonempty. These variants have a very simple choice for the stepsizes. Moreover, we also establish primal convergence when the dual optimal set is empty. Finally, our second variant of MSG converges in a finite number of steps.     

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.     

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.     

有界整规划中的渐近强非线性对偶

本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法.     

Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality

This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided.     

Mixed-Type Duality on Nonsmooth Minimax Fractional Programming Involving Exponential (p,r)-Invexity

Considering a nonsmooth minimax fractional programming problem involving exponential (p, r)-invexity, we construct a mixed-type dual problem, which is performed by an incomplete Lagrangian dual model. This mixed-type dual model involves the Wolfe type dual and Mond-Weir type dual as the special cases under exponential (p, r)-invexity. We establish the mixed-type duality problem with conditions for exponential (p, r)-invexity and prove that the optimal values of the primary problem and the mixed-type duality problem have no duality gap under the framwork of exponential (p, r)-invexity.     

A primal-dual augmented Lagrangian

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ ₁ linearly constrained Lagrangian (pdℓ ₁LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.