Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.     

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.     

Robust Duality in Parametric Convex Optimization

Modelling of convex optimization in the face of data uncertainty often gives rise to families of parametric convex optimization problems. This motivates us to present, in this paper, a duality framework for a family of parametric convex optimization problems. By employing conjugate analysis, we present robust duality for the family of parametric problems by establishing strong duality between associated dual pair. We first show that robust duality holds whenever a constraint qualification holds. We then show that this constraint qualification is also necessary for robust duality in the sense that the constraint qualification holds if and only if robust duality holds for every linear perturbation of the objective function. As an application, we obtain a robust duality theorem for the best approximation problems with constraint data uncertainty under a strict feasibility condition.     

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.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Quadratic geometric programming with application to machining economics

Geometric Programming is extended to include convex quadratic functions. Generalized Geometric Programming is applied to this class of programs to obtain a convex dual program. Machining economics problems fall into this class. Such problems are studied by applying this duality to a nested set of three problems. One problem is zero degree of difficulty and the solution is obtained by solving a simple system of equations. The inclusion of a constraint restricting the force on the tool to be less than or equal to the breaking force provides a more realistic solution. This model is solved as a program with one degree of difficulty. Finally the behavior of the machining cost per part is studied parametrically as a function of axial depth. This research was supported by the Air Force Office of Scientific Research Grant AFOSR-83-0234     

A linear programming approach to solving bilinear programmes

This paper discusses the maximization of a bilinear function over two independent polytopes. The maximization problem is converted into a max—min problem, using duality. This problem is then solved via a sequence of dual linear programmes, whose constraint vectors are successively determined bytth order optima of a master linear programme.     

Duality for minmax programs

A duality theory is derived for minimizing the maximum of a finite set of convex functions subject to a convex constraint set generated by both linear and nonlinear inequalities. The development uses the theory of generalised geometric programming. Further, a particular class of minmax program which has some practical significance is considered and a particularly simple dual program is obtained.     

Clark's theorem for semi-infinite convex programs

In 1961, Clark proved that if either the feasible region of a linear program or its dual is nonempty and bounded, then the other is unbounded. Recently, Duffin has extended this result to a convex program and its Lagrangian dual. Moreover, Duffin showed that under this boundedness assumption there is no duality gap. The purpose of this paper is to extend Duffin's results to semi-infinite programs.     

Perfect duality for convexlike programs

The minimizing problem for a convex program has a dual problem, that is, the maximizing problem of the Lagrangian. Although these problems have a duality gap in general, the duality gap can be eliminated by relaxing the constraint of the minimizing problem, so that the constraint is enforced only in the limit. We extend this result to the convexlike case. Moreover, we obtain a necessary condition for optimality for minimizing problems whose objective function and constraint mapping have convex Gateaux derivative.The authors are indebted to Professor W. Takahashi of Tokyo Institute of Technology for his valuable comments, and also to the referees for their helpful suggestions.     

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     

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.     

Necessary and sufficient constraint qualifications for solvability of systems of infinite convex inequalities

In this paper we present constraint qualifications which completely characterize the Farkas–Minkowski and the locally Farkas–Minkowski convex (possibly infinite) inequality systems posed in topological vector spaces. The number of constraints and the dimension of the linear space are arbitrary (possibly infinite). The constraint qualifications considered in this paper are expressed in terms of the solvability of certain parametric convex (linear) systems and the uniform strong duality or the uniform min–max duality relative to the Lagrange (Haar) dual problems of suitable convex (linear) parametric optimization problems.     

Lagrangian duality of concave minimization subject to linear constraints and an additional facial reverse convex constraint

This paper is concerned with the global optimization problem of minimizing a concave function subject to linear constraints and an additional facial reverse convex constraint. Here, the feasible set is the union of some faces of the polyhedron determined by the linear constraints. Several well-known mathematical problems can be written or transformed into the form considered. The paper addresses the Lagrangian duality of the problem. It is shown that, under slight assumptions, the duality gap can be closed with a finite dual multiplier. Finite methods based on solving concave minimization problems are also proposed. We deal with the advantages accrued when outer approximation, cutting plane, or branch-and-bound methods are used for solving these subproblems.This research was supported in part by the Hungarian National Research Foundation, Grant OTKA 2568. The author wishes to thank the Associate Editor and the referees for their valuable comments.     

Parametric Disjunctive Programming: One-Sided Differentiability of the Value Function

We consider a countable family of one-parameter convex programs and give sufficient conditions for the one-sided differentiability of its optimal value function. The analysis is based on the Borwein dual problem for a family of convex programs (a convex disjunctive program). We give conditions that assure stability of the situation of perfect duality in the Borwein theory.For the reader's convenience, we start with a review of duality results for families of convex programs. A parametric family of dual problems is introduced that contains the dual problems of Balas and Borwein as special cases. In addition, a vector optimization problem is defined as a dual problem. This generalizes a result by Helbig about families of linear programs.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.