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.     

Duality and Penalization in Optimization via an Augmented Lagrangian Function with Applications

This paper aims to establish duality and exact penalization results for the primal problem of minimizing an extended real-valued function in a reflexive Banach space in terms of a valley-at-0 augmented Lagrangian function. It is shown that every weak limit point of a sequence of optimal solutions generated by the valley-at-0 augmented Lagrangian problems is a solution of the original problem. A zero duality gap property and an exact penalization representation between the primal problem and the valley-at-0 augmented Lagrangian dual problem are obtained. These results are then applied to an inequality and equality constrained optimization problem in infinite-dimensional spaces and variational problems in Sobolev spaces, respectively. The first author was supported by the Research Committee of Hong Kong Polytechnic University, by Grant 10571174 from the National Natural Science Foundation of China and Grant 08KJB11009 from the Jiangsu Education Committee of China. The second author was supported by Grant BQ771 from the Research Grants Council of Hong Kong. We are grateful to the referees for useful suggestions which have contributed to the final presentation of the paper.     

A note on strong duality in convex semidefinite optimization: necessary and sufficient conditions

A strong duality which states that the optimal values of the primal convex problem and its Lagrangian dual problem are equal (i.e. zero duality gap) and the dual problem attains its maximum is a corner stone in convex optimization. In particular it plays a major role in the numerical solution as well as the application of convex semidefinite optimization. The strong duality requires a technical condition known as a constraint qualification (CQ). Several CQs which are sufficient for strong duality have been given in the literature. In this note we present new necessary and sufficient CQs for the strong duality in convex semidefinite optimization. These CQs are shown to be sharper forms of the strong conical hull intersection property (CHIP) of the intersecting sets of constraints which has played a critical role in other areas of convex optimization such as constrained approximation and error bounds. Research was partially supported by the Australian Research Council. The author is grateful to the referees for their helpful comments     

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

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

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

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.     

Minimax Fractional Programming for <Emphasis Type="Italic">n</Emphasis>-Set Functions and Mixed-Type Duality under Generalized Invexity

We establish the sufficient optimality conditions for a minimax programming problem involving p fractional n-set functions under generalized invexity. Using incomplete Lagrange duality, we formulate a mixed-type dual problem which unifies the Wolfe type dual and Mond-Weir type dual in fractional n-set functions under generalized invexity. Furthermore, we establish three duality theorems: weak, strong, and strict converse duality theorem, and prove that the optimal values of the primal problem and the mixed-type dual problem have no duality gap under extra assumptions in the framework. This research was partly supported by the National Science Council, NSC 94-2115-M-033-003, Taiwan.     

Some Results about Duality and Exact Penalization

In this paper, we introduce the concept of the valley at 0 augmenting function and apply it to construct a class of valley at 0 augmented Lagrangian functions. We establish the existence of a path of optimal solutions generated by valley at 0 augmented Lagrangian problems and its convergence toward the optimal set of the original problem and obtain the zero duality gap property between the primal problem and the valley at 0 augmented Lagrangian dual problem. Moreover, we establish the exact penalization representation results in the framework of valley at 0 augmented Lagrangian.     

The exact penalty map for nonsmooth and nonconvex optimization

Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets.     

Unified Nonlinear Lagrangian Approach to Duality and Optimal Paths

In the context of an inequality constrained optimization problem, we present a unified nonlinear Lagrangian dual scheme and establish necessary and sufficient conditions for the zero duality gap property. From these results, we derive necessary and sufficient conditions for four classes of zero duality gap properties and establish the equivalence among them. Finally, we obtain the convergence of an optimal path for the unified scheme and present a sufficient condition for the finite termination of the optimal path. This research was partially supported by the Research Grants Council of Hong Kong Grant PolyU 5250/03E, the National Natural Science Foundation of China Grants 10471159 and 10571106, NCET, and the Natural Science Foundation of Chongqing     

Second order optimality conditions for bilevel set optimization problems

In this paper, we introduce a new notion of augmenting function known as indicator augmenting function to establish a minmax type duality relation, existence of a path of solution converging to optimal value and a zero duality gap relation for a nonconvex primal problem and the corresponding Lagrangian dual problem. We also obtain necessary and sufficient conditions for an exact penalty representation in the framework of indicator augmented Lagrangian.     

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.     

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.     

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.     

Augmented Lagrangian function, non-quadratic growth condition and exact penalization

In this paper, under the assumption that the perturbation function satisfies a growth condition, necessary and sufficient conditions for an exact penalty representation and a zero duality gap property between the primal problem and its augmented Lagrangian dual problem are established.     

Dynamic convex duality in constrained utility maximization

ABSTRACT

In this paper, we study a constrained utility maximization problem following the convex duality approach. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of forward and backward stochastic differential equations (FBSDEs) plus some additional conditions. Such formulation then allows us to explicitly characterize the primal optimal control as a function of the adjoint process coming from the dual FBSDEs in a dynamic fashion and vice versa. We also find that the optimal wealth process coincides with the adjoint process of the dual problem and vice versa. Finally we solve three constrained utility maximization problems, which contrasts the simplicity of the duality approach we propose and the technical complexity of solving the primal problem directly.     

Additively separable duality theory

In duality theory, there is a trade-off between generality and tractability. Thus, the generality of the Tind-Wolsey framework comes at the expense of an infinite-dimensional dual solution space, even if the primal solution space is finite dimensional. Therefore, the challenge is to impose additional structure on the dual solution space and to identify conditions on the primal program, such that the properties that are typically associated with duality, like weak and strong duality, are preserved.In this paper, we consider real-valuedness, continuity, and additive separability as such additional structures. The virtue of the latter property is that it restores the one-to-one correspondence between primal constraints and dual variables as it exists in Lagrangian duality. The main result of this paper is that, roughly speaking, the existence of realvalued, continuous, and additively separable dual solutions that preserve strong duality is guaranteed, once the primal program satisfies a certain stability condition. The latter condition is ensured by the well-known regularity conditions that imply constraint qualification in Karush-Kuhn-Tucker points. On the other hand, if instead of additive separability, a mild tractability condition is imposed on the dual solution space, then stability turns out to be a necessary condition for strong duality in a well-defined sense. This result, combined with the observation that applicability of some well-known augmented Lagrangian methods to constrained optimization.This study was supported by the Netherlands Foundation for Mathematics (SMC) with financial aid from the Netherlands Organization for Scientific Research (NWO).     

Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

Subdifferentiability and the Duality Gap

We point out a connection between sensitivity analysis and the fundamental theorem of linear programming by characterizing when a linear programming problem has no duality gap. The main result is that the value function is subdifferentiable at the primal constraint if and only if there exists an optimal dual solution and there is no duality gap. To illustrate the subtlety of the condition, we extend Kretschmer's gap example to construct (as the value function of a linear programming problem) a convex function which is subdifferentiable at a point but is not continuous there. We also apply the theorem to the continuum version of the assignment model.     

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.