Higher order duality in vector optimization over cones

In this paper higher order cone convex, pseudo convex, strongly pseudo convex, and quasiconvex functions are introduced. Higher order sufficient optimality conditions are given for a weak minimum, minimum, strong minimum and Benson proper minimum solution of a vector optimization problem. A higher order dual is associated and weak and strong duality results are established under these new generalized convexity assumptions.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

On sufficiency and duality for a class of interval-valued programming problems

In this paper, we are concerned with an interval-valued programming problem. Sufficient optimality conditions are established under generalized convex functions for a feasible solution to be an efficient solution. Appropriate duality theorems for Mond-Weir and Wolfe type duals are discussed in order to relate the efficient solutions of primal and dual programs.     

Optimality conditions for weak efficiency to vector optimization problems with composed convex functions

We consider a convex optimization problem with a vector valued function as objective function and convex cone inequality constraints. We suppose that each entry of the objective function is the composition of some convex functions. Our aim is to provide necessary and sufficient conditions for the weakly efficient solutions of this vector problem. Moreover, a multiobjective dual treatment is given and weak and strong duality assertions are proved.      

Nondifferentiable multiobjective second-order symmetric duality

In this paper, a pair of Wolfe type second-order multiobjective symmetric dual programs involving nondifferentiable functions is formulated. Weak, strong and converse duality theorems are then established using the notion of second-order F-convexity assumptions. An example which is second-order F-convex but not convex is also illustrated. Further, special cases are discussed to show that this paper extends some known results of the literature.     

Some Farkas-type results for fractional programming problems with DC functions

For a kind of fractional programming problem that the objective functions are the ratio of two DC (difference of convex) functions with finitely many convex constraints, in this paper, its dual problems are constructed, weak and strong duality assertions are given, and some sufficient and necessary optimality conditions which characterize their optimal solutions are obtained. Some recently obtained Farkas-type results for fractional programming problems that the objective functions are the ratio of a convex function to a concave function with finitely many convex constraints are the special cases of the general results of this paper.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Duality for multiobjective optimization problems with convex objective functions and D.C. constraints

In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints.     

Sufficiency and Duality in Multiobjective Programming under Generalized Type I Functions

In this paper, new classes of generalized (F,α,ρ,d)-V-type I functions are introduced for differentiable multiobjective programming problems. Based upon these generalized convex functions, sufficient optimality conditions are established. Weak, strong and strict converse duality theorems are also derived for Wolfe and Mond-Weir type multiobjective dual programs.     

Universal duality in conic convex optimization

Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and −∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the primal or the dual is feasible. For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices' and cone under which the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality'. Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications. This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931, CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

A class of problems where dual bounds beat underestimation bounds

We investigate the problem of minimizing a nonconvex function with respect to convex constraints, and we study different techniques to compute a lower bound on the optimal value: The method of using convex envelope functions on one hand, and the method of exploiting nonconvex duality on the other hand. We investigate which technique gives the better bound and develop conditions under which the dual bound is strictly better than the convex envelope bound. As a byproduct, we derive some interesting results on nonconvex duality.     

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     

Existence of optimal Lagrange multipliers for certain nonconvex allocation problems

The use of Lagrange multipliers for decentralization of large resource allocation problems is well known. However, these dual techniques may suffer from the drawback ofduality gaps, to guarantee the absence of which various functions are required to be convex. This limits greatly the applicability of the decentralized approach. We show that less restrictive conditions can be formulated for a certain class of allocation problems, which we call resource management problems, which typically occur in large operational systems. We present a theorem for the existence of optimal multipliers, while placing almost no restrictions on the forms of the resource usage functions or the domains of the decision variables. Efficient solution algorithms, with provable convergence properties, have been given in a companion paper. Our results justify the application of dual methods to this class ofreal-world problems.The author is indebted to Mr. G. Karady and Professor Y. C. Ho of Harvard University for their valuable comments, and also to the referees for their helpful suggestions. This research was partially supported by the Office of Naval Research, under the Joint Services Electronic Program, Contract No. N0001475-C-0648, and by the National Science Foundation, Grant No. ENG-78-15231.     

Partially finite convex programming,Part II: Explicit lattice models

In Part I of this work we derived a duality theorem for partially finite convex programs, problems for which the standard Slater condition fails almost invariably. Our result depended on a constraint qualification involving the notion ofquasi relative interior. The derivation of the primal solution from a dual solution depended on the differentiability of the dual objective function: the differentiability of various convex functions in lattices was considered at the end of Part I. In Part II we shall apply our results to a number of more concrete problems, including variants of semi-infinite linear programming,L ¹ approximation, constrained approximation and interpolation, spectral estimation, semi-infinite transportation problems and the generalized market area problem of Lowe and Hurter (1976). As in Part I, we shall use lattice notation extensively, but, as we illustrated there, in concrete examples lattice-theoretic ideas can be avoided, if preferred, by direct calculation.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

Dual gauge programs,with applications to quadratic programming and the minimum-norm problem

A gauge functionf(·) is a nonnegative convex function that is positively homogeneous and satisfiesf(0)=0. Norms and pseudonorms are specific instances of a gauge function. This paper presents a gauge duality theory for a gauge program, which is the problem of minimizing the value of a gauge functionf(·) over a convex set. The gauge dual program is also a gauge program, unlike the standard Lagrange dual. We present sufficient conditions onf(·) that ensure the existence of optimal solutions to the gauge program and its dual, with no duality gap. These sufficient conditions are relatively weak and are easy to verify, and are independent of any qualifications on the constraints. The theory is applied to a class of convex quadratic programs, and to the minimuml _p norm problem. The gauge dual program is shown to provide a smaller duality than the standard dual, in a certain sense discussed in the text.     

一类多目标Lipschitz规划的对偶定理

Lipschitz函数定义了广义本性伪凸的概念,建立了多目标Lipschitz规划的Mond-Weir型对偶和Wolfe型对偶,证明了原规划与对偶规划之间的对偶定理。     

Lagrangian Duality and Cone Convexlike Functions

In this paper, we consider first the most important classes of cone convexlike vector-valued functions and give a dual characterization for some of these classes. It turns out that these characterizations are strongly related to the closely convexlike and Ky Fan convex bifunctions occurring within minimax problems. Applying the Lagrangian perturbation approach, we show that some of these classes of cone convexlike vector-valued functions show up naturally in verifying strong Lagrangian duality for finite-dimensional optimization problems. This is achieved by extending classical convexity results for biconjugate functions to the class of so-called almost convex functions. In particular, for a general class of finite-dimensional optimization problems, strong Lagrangian duality holds if some vector-valued function related to this optimization problem is closely K-convexlike and satisfies some additional regularity assumptions. For K a full-dimensional convex cone, it turns out that the conditions for strong Lagrangian duality simplify. Finally, we compare the results obtained by the Lagrangian perturbation approach worked out in this paper with the results achieved by the so-called image space approach initiated by Giannessi.