A new proof of the strong duality theorem for semidefinite programming

Semidefinite programs are convex optimization problems arising in a wide variety of applications and are the extension of linear programming. Most methods for linear programming have been generalized to semidefinite programs. Just as in linear programming, duality theorem plays a basic and an important role in theory as well as in algorithmics. Based on the discretization method and convergence property, this paper proposes a new proof of the strong duality theorem for semidefinite programming, which is different from other common proofs and is more simple.     

Duality for quasi-concave programs with explicit constraints

The idea of duality is now well established in the theory of concave programming. The basis of this duality is the concave conjugate transform. This has been exemplified in the development of generalised geometric programming. Much of the current research in duality theory is focused on relaxing the requirement of concavity. Here we develop a duality theory for mathematical programs with a quasi concave objective function and explicit quasi concave constraints. Generalisations of the concave conjugate transform are introduced which pair quasi concave functions as the concave conjugate transform does for concave functions. Optimality conditions are derived relating the primal quasi concave program to its dual. This duality theory was motivated by and has implications in certain problems of mathematical economics. An application to economics is given.     

Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming

Duality results are established in convex programming with the set-inclusive constraints studied by Soyster. The recently developed duality theory for generalized linear programs by Thuente is further generalized and also brought into the framework of Soyster's theory. Convex programming with set-inclusive constraints is further extended to fractional programming.     

Duality of a Nonconvex Sum of Ratios

For mathematical programs with objective involving a sum of ratios of affine functions, there are few theoretical results due to the nonconvex nature of the program. In this paper, we derive a duality theory for these programs by establishing their connection with geometric programming. This connection allows one to bring to bear the powerful theory and computational algorithms associated with geometric programming.     

均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题,基于Mond和Weir提出的标准非线性规划的对偶形式,利用其S稳定性,建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶,从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下,利用次线性函数,分别提出了弱对偶性、强对偶性和严格逆对偶性定理,并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.     

Composite geometric programming

Geometric programming is based on functions called posynomials, the terms of which are log-linear. This class of programs is extended from the composition of an exponential and a linear function to an exponential and a convex function. The resulting duality theory for composite geometric programs retains many of the qualities of geometric programming duality, while at the same time encompassing new areas of application. As an application, composite geometric programming is applied to exponential geometric programming. A pure dual is developed for the first time and used to solve a problem from the literature.This research was supported by the Air Force Office of Scientific Research, Grant No. AFOSR-83-0234.     

Equivalence between a generalized fenchel duality theorem and a saddle-point theorem for fractional programs

The convex case of a fractional program is considered. By the aid of a duality theory for mathematical programming involving a maximum and minimum operator, and by defining new operators, we obtain three equivalent duality theorems for three pairs of primal-dual programs. The second and the third one are the saddle-point theorem and a generalized Fenchel duality theorem, respectively.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

基于广义几何规划的最小广义信息密度区分问题及其对偶理论

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｑｕａｄｒａｔｉｃａｌｌｙｃｏｎｓｔｒａｉｎｅｄａｎｄｅｎｔｒｏｐｙｄｅｎｓｉｔｙｃｏｎｓｔｒａｉｎｅｄｑｕａｄｒａｔｉｃｐｒｏｇｒａｍｔｈａｔｉｓｇｏｉｎｇｔｏｂｅｓｔｕｄｉｅｄｉｎｔｈｉｓｐａｐｅｒｉｓｃｈａｒａｃｔｅｒｉｚｅｄａｓｔｈｅｆｏｌｌｏｗｉｎｇｆｏｒｍ :Ｐｒｏｇｒａｍ (Ｑ)(Ｑ)　　ｍｉｎ　Ｑ0 (ｚ)ｓ .ｔ .　Ｐｊ(ｚ)≤ 0 ,　ｊ =1 ,2 ,...,ｌ,Ｑｉ(ｚ) ≤ 0 ,　ｉ =1 ,2 ,...,ｒ ,ｚ=(ｚ1,...,ｚｎ) Ｔ ≥ 0 ,ｗｈｅｒｅＰｊ(ｚ) = ｎｋ =1ｚｋｌｏｇ ｚｋｅ…     

On Duality for a Class of Quasiconcave Multiplicative Programs

Multiplicative programs are a difficult class of nonconvex programs that have received increasing attention because of their many applications. However, given their nonconvex nature, few theoretical results are available. In this paper, we study a particular case of these programs which involves the maximization of a quasiconcave function over a linear constraint set. Using results from conjugate function theory and generalized geometric programming, we derive a complete duality theory. The results are further specialized to linear multiplicative programming.     

Inverse conic programming with applications

Linear programming duality yields efficient algorithms for solving inverse linear programs. We show that special classes of conic programs admit a similar duality and, as a consequence, establish that the corresponding inverse programs are efficiently solvable. We discuss applications of inverse conic programming in portfolio optimization and utility function identification.     

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.     

On some relations between a dual pair of multiple objective linear programs

Summary This paper is a contribution to the theory of multiple objective linear programming. Existence and duality properties for multiple objective linear programs are developed which contain the fundamental existence and duality results of linear programming as special cases. Several implications of the duality results will be indicated.

---

Zusammenfassung In diesem Beitrag werden einige Existenz- und Dualitätsaussagen für lineare Programme mit mehreren Zielfunktionen (Vektoroptimierungsprobleme) vorgestellt. Es wird gezeigt, daß diese Aussagen die Existenz- und Dualitätsaussagen der linearen Programmierung als Spezialfälle enthalten.

     

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.     

Primal-dual stability in continuous linear optimization

Any linear (ordinary or semi-infinite) optimization problem, and also its dual problem, can be classified as either inconsistent or bounded or unbounded, giving rise to nine duality states, three of them being precluded by the weak duality theorem. The remaining six duality states are possible in linear semi-infinite programming whereas two of them are precluded in linear programming as a consequence of the existence theorem and the non-homogeneous Farkas Lemma. This paper characterizes the linear programs and the continuous linear semi-infinite programs whose duality state is preserved by sufficiently small perturbations of all the data. Moreover, it shows that almost all linear programs satisfy this stability property.     

Optimality conditions and duality in continuous programming II. The linear problem revisited

This is Part II of a two-part paper; the purpose of this two-part paper is (a) to develop new concepts and techniques in the theory of infinite-dimensional programming, and (b) to obtain fruitful applications in continuous time programming. In Part II the continuous time version of Farkas' theorem developed in Part I serves as the foundation for the duality theory for a broad class of linear continuous time programming problems distinct from those previously examined. In particular, we establish duality under analytic conditions, e.g., whether the given functions are measurable or continuous, that are weaker, and algebraic conditions that are more general, than those previously imposed. The new class of problems arising from these conditions allows for several important resource allocation problems previously excluded from consideration. In addition, an assumption needed to prove the Kuhn-Tucker theorem for the nonlinear problem of Part I is shown in the linear case to be completely analogous to the well-known Slater condition utilized in finite-dimensional programming theory. An example is given that exhibits the essential role of the constraint qualification in linear continuous time programming, a result at variance with the theory in finite dimensions but consistent with other results concerning linear programs in infinite-dimensional spaces.     

Symmetric duality for disjunctive programming with absolute value functionals

In this paper we develop a complete duality theory for a couple of disjunctive linear programming problems with absolute value functionals. The pair of dual problems constructed has no duality gap, and may be considered as a generalization of the duality theory for convex programming.     

Higher-order symmetric duality in multiobjective programming problems under higher-order invexity

In this paper we present a pair of Wolfe and Mond-Weir type higher-order symmetric dual programs for multiobjective symmetric programming problems. Different types of higher-order duality results (weak, strong and converse duality) are established for the above higher-order symmetric dual programs under higher-order invexity and higher-order pseudo-invexity assumptions. Also we discuss many examples and counterexamples to justify our work.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

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.