Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

Duality for Algebraic Linear Programming

A duality theory for algebraic linear (integer) programming (ALP) is developed which is of the same importance for linear (integer) programming with linear algebraic objectives as linear programming duality is for classical LP. In particular, optimality criteria for primal, primal-dual, and dual methods are given which generalize feasibility and complementarity criteria of classical LP. Strong duality results are given for special combinatorial problems. Further, the validity and finiteness of a primal simplex method based on a feasibility criterion are proved in the case of nondiscrete variables. In this case a strong duality result is shown.     

On robust duality for fractional programming with uncertainty data

In this paper, we present a duality theory for fractional programming problems in the face of data uncertainty via robust optimization. By employing conjugate analysis, we establish robust strong duality for an uncertain fractional programming problem and its uncertain Wolfe dual programming problem by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. We show that our results encompass as special cases some programming problems considered in the recent literature. Moreover, we also show that robust strong duality always holds for linear fractional programming problems under scenario data uncertainty or constraint-wise interval uncertainty, and that the optimistic counterpart of the dual is tractable computationally.     

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.     

The volume algorithm: producing primal solutions with a subgradient method

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location. Received: June 15, 1998 / Accepted: November 15, 1999?Published online March 15, 2000     

An elementary survey of general duality theory in mathematical programming

We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Third order duality in nonlinear programming problems

Third order dual of a primal nonlinear programming problem is established which involves the third order derivatives of the functions constituting the primal problem. Desired duality theorems are provided for the pair of primal and the corresponding third order dual problem. Numerical examples are illustrated to justify the efficiency of the proposed method. It is also observed that some of the existing results are obtained as special cases.     

On the Interpretation of Optimal Dual Solutions in Convex Programming

The relationships between multiple optimal dual solutions of a convex programming problem and the corresponding primal optimal value function are established by straightforward arguments on known results in duality theory. The subsequent discussion includes a demonstration that one-sided shadow prices can be found by solving a linear programming problem, conditions for the uniqueness and validity of the classical shadow price interpretation and a specialization of the results to the linear programming case.     

Sufficient conditions for duality in homogeneous programming

A symmetric duality theory for programming problems with homogeneous objective functions was published in 1961 by Eisenberg and has been used by a number of authors since in establishing duality theorems for specific problems. In this paper, we study a generalization of Eisenberg's problem from the viewpoint of Rockafellar's very general perturbation theory of duality. The extension of Eisenberg's sufficient conditions appears as a special case of a much more general criterion for the existence of optimal vectors and lack of a duality gap. We give examples where Eisenberg's sufficient condition is not satisfied, yet optimal vectors exist, and primal and dual problems have the same value.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Duality for nondifferentiable minimax programming in complex spaces

Employing the optimality (necessary and sufficient) conditions of a nondifferentiable minimax programming problem in complex spaces, we formulate a one-parametric dual and a parameter free dual problems. On both dual problems, we establish three duality theorems: weak, strong, and strict converse duality theorem, and prove that there is no duality gap between the two dual problems with respect to the primal problem under some generalized convexities of complex functions in the complex programming problem.     

Duality Theory in Interval-Valued Linear Programming Problems

The weak and strong duality theorems in interval-valued linear programming problems are derived in this paper. The primal and dual interval-valued linear programming problems are formulated by proposing the concept of a scalar (inner) product of closed intervals. We introduce a solution concept that is essentially similar to the notion of nondominated solution in multiobjective programming problems by imposing a partial ordering on the set of all closed intervals. Under these settings, the weak and strong duality theorems for interval-valued linear programming problems are derived naturally.     

Feasibility and solvability of Lyapunov-type linear programming over symmetric cones

In this paper, we consider the Lyapunov-type linear programming and its dual over symmetric cones. By introducing and characterizing the generalized inverse of Lyapunov operator in Euclidean Jordan algebras, we establish two kinds of Lyapunov-type Farkas’ lemmas to exhibit feasibilities of the corresponding primal and dual programming problems, respectively. As one of the main results, we show that the feasibilities of the primal and dual problems lead to the solvability of the primal problem and zero duality gap under some mild condition. In this case, we obtain that any solution to the pair of primal and dual problems is equivalent to the solution of the corresponding KKT system.     

Duality for nondifferentiable minimax programming in complex spaces

Employing the optimality (necessary and sufficient) conditions of a nondifferentiable minimax programming problem in complex spaces, we formulate a one-parametric dual and a parameter free dual problems. On both dual problems, we establish three duality theorems: weak, strong, and strict converse duality theorem, and prove that there is no duality gap between the two dual problems with respect to the primal problem under some generalized convexities of complex functions in the complex programming problem.     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

Duality theorem for a generalized Fermat-Weber problem

The classical Fermat-Weber problem is to minimize the sum of the distances from a point in a plane tok given points in the plane. This problem was generalized by Witzgall ton-dimensional space and to allow for a general norm, not necessarily symmetric; he found a dual for this problem. The authors generalize this result further by proving a duality theorem which includes as special cases a great variety of choices of norms in the terms of the Fermat-Weber sum. The theorem is proved by applying a general duality theorem of Rockafellar. As applications, a dual is found for the multi-facility location problem and a nonlinear dual is obtained for a linear programming problem with a priori bounds for the variables. When the norms concerned are continuously differentiable, formulas are obtained for retrieving the solution for each primal problem from the solution of its dual.     

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.     

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.