Comment on a note on duality gaps in linear programming over convex sets

In Ref. 1, Soyster has given a rather complicated proof of the absence of a duality gap, under a certain interiority condition, for a variant of a pair of optimization problems introduced by Ben-Israel, Charnes, and Kortanek (Ref. 2). A proof can be given directly (and under weaker conditions) by a simple application of a Lagrange multiplier theorem on convex programming in abstract spaces (Ref. 3).     

A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

Zero duality gaps in infinite-dimensional programming

In this paper we study the following infinite-dimensional programming problem: (P) inff ₀(x), subject toxC,f _i(x)0,iI, whereI is an index set with possibly infinite cardinality andC is an infinite-dimensional set. Zero duality gap results are presented under suitable regularity hypotheses for convex-like (nonconvex) and convex infinitely constrained program (P). Various properties of the value function of the convex-like program and its connections to the regularity hypotheses are studied. Relationships between the zero duality gap property, semicontinuity, and -subdifferentiability of the value function are examined. In particular, a characterization for a zero duality gap is given, using the -subdifferential of the value function without convexity.The authors are extremely grateful to the referees for their constructive criticisms and helpful suggestions which have contributed to the final preparation of this paper. This research was partially completed while the first author was a visitor of the Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada.This work was partially supported by NSERC Grant No. A9161.     

Intuitionistic fuzzy linear programming and duality: a level sets approach

The paper is concerned with linear programming problems whose input data may be intuitionistic fuzzy (IF) while the values of variables are always real numbers. We propose rather general approach to this type of problems based on level sets, and present recent results for problems in which the notions of feasibility and optimality are based on the IF relations. Special attention is devoted to the weak and strong duality.     

A note on Lipschitzian stability of variational inequalities over perturbed polyhedral convex sets

In the previous paper (Optim lett 6:749–762, 2012), under some technical assumptions, we proved that the solution mapping of variational inequalities over perturbed polyhedral convex sets is not Lipschitz-like around points at which the positively linear dependence of the active vectors defining the constraint set is valid. This note shows that the result holds without such assumptions. In addition, for more deeply understanding the results on the Lipschitz-like stability, some examples have been presented.     

A review of duality theory for linear programming over topological vector spaces

In this paper duality theory for infinite dimensional linear programs is discussed in a topological vector space setting. Infinite dimensional linear programs occur in many different areas and the duality theory of such problems has been discussed by a number of authors. However, the results are scattered in the literature and are proved in a variety of different settings. The purpose of this paper is to bring together the main results on this subject and to present them in a unified setting and notation with some new simpler proofs.     

A note on the measurability of convex sets

Archiv der Mathematik -     

A note on higher-order nondifferentiable symmetric duality in multiobjective programming

In this work, we establish a strong duality theorem for Mond–Weir type multiobjective higher-order nondifferentiable symmetric dual programs. This fills some gaps in the work of Chen [X. Chen, Higher-order symmetric duality in nondifferentiable multiobjective programming problems, J. Math. Anal. Appl. 290 (2004) 423–435].     

A note on degeneracy in linear programming

We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best vertex (which is highly degenerate) is already given. So, to solve the latter, it is sufficient to exit that vertex in a direction that improves the objective function value.     

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 duality theory of convex semi-infinite programming

In this article we discuss weak and strong duality properties of convex semi-infinite programming problems. We use a unified framework by writing the corresponding constraints in a form of cone inclusions. The consequent analysis is based on the conjugate duality approach of embedding the problem into a parametric family of problems parameterized by a finite-dimensional vector.     

Robustness and duality in linear programming

In this paper, we consider a linear program in which the right hand sides of theconstraints are uncertain and inaccurate. This uncertainty is represented byintervals, that is to say that each right hand side can take any value in itsinterval regardless of other constraints. The problem is then to determine arobust solution, which is satisfactory for all possible coefficient values.Classical criteria, such as the worst case and the maximum regret, are appliedto define different robust versions of the initial linear program. Morerecently, Bertsimas and Sim have proposed a new model that generalizes the worstcase criterion. The subject of this paper is to establish the relationshipsbetween linear programs with uncertain right hand sides and linear programs withuncertain objective function coefficients using the classical duality theory. Weshow that the transfer of the uncertainty from the right hand sides to theobjective function coefficients is possible by establishing new dualityrelations. When the right hand sides are approximated by intervals, we alsopropose an extension of the Bertsimas and Sim's model and we show that themaximum regret criterion is equivalent to the worst case criterion.     

On duality in linear fractional programming

In this paper, a dual of a given linear fractional program is defined and the weak, direct and converse duality theorems are proved. Both the primal and the dual are linear fractional programs. This duality theory leads to necessary and sufficient conditions for the optimality of a given feasible solution. A unmerical example is presented to illustrate the theory in this connection. The equivalence of Charnes and Cooper dual and Dinkelbach’s parametric dual of a linear fractional program is also established.     

A note on the condition numbers of convex sets

Mathematical Programming - In this note, we give a counterexample to show that the characterization formula for the condition numbers of a convex set $$C$$ of $$\mathbb R^n$$ given in Coulibaly and...     

A weak duality theorem for stochastic linear programming

Summary A linear programming problem is said to be stochastic if one or more of the coefficients in the objective function or the system of constraints or resource availabilities is known only by its probability distribution. A distinction is usually made between two related approaches to stochastic linear programming, the active and passive approach respectively. An extension of the duality theorem of non-stochastic or deterministic programming problem has been attempted in this paper in the area of stochastic linear programming in its two approaches. The method of proof is based on the idea that since the parameter space defined by a stochastic linear programme is the topological product of the real line with itself, it forms a first countable topological space. Using a set of distinct and selected points in the parameter space the concepts of feasibility, optimality and duality are extended to stochastic linear programming problems of arbitrary dimensionality. Based on the non-singular regions of the parameter space of a stochastic linear programming problem the theorem utilizes the conditions of convergence of the sequence of distinct and selected points in the parameter space to a limit point and thereby generalizes the duality theorem in the stochastic case. Furthermore it is shown that the regions of feasibility of the active and passive approaches of stochastic linear programming may be different, so that on this basis it may be possible to establish some inequality relations for the optimal solutions defined for the respective feasible regions.

---

Zusammenfassung Ein lineares Programmproblem wird stochastisch genannt, wenn ein oder mehrere Koeffizienten der Zielfunktion oder des Systems der Beschränkungen oder der verfügbaren Ressourcen nur durch ihre Wahrscheinlichkeitsverteilung bekannt sind. Gewöhnlich wird zwischen zwei verwandten Verfahren für das stochastische lineare Programmieren unterschieden, dem aktiven und dem passiven Verfahren.In der vorliegenden Arbeit wird versucht, das für nichtstochastische oder deterministische Programmprobleme gültige Dualitätstheorem unter Berücksichtigung beider Verfahrensweisen auf den Bereich des stochastischen linearen Programmierens auszudehnen. Der Beweis gründet sich auf den Gedanken, daß der Parameterraum einen abzählbaren topologischen Raum bildet, da er — durch ein stochastisches lineares Programm definiert — das topologische Produkt der reellen Achse mit sich selbst ist. Unter Benutzung einer Menge von verschiedenen und ausgewählten Punkten im Parameterraum werden die Begriffe der Zulässigkeit, der Optimalität und der Dualität auf stochastische lineare Programmprobleme beliebiger Dimension ausgedehnt. Auf der Grundlage nichtsingulärer Bereiche des Parameterraumes eines stochastischen linearen Programmproblems benutzt das Theorem die Bedingungen für die Konvergenz einer Folge verschiedener und ausgewählter Punkte des Parameterraumes nach einem Grenzpunkt und verallmeinert damit das Dualitätstheorem für den stochastischen Fall. Weiter wird gezeigt, daß die Zulässigkeitsbereiche der aktiven und passiven Verfahren des stochastischen linearen Programmierens verschieden sein können, so daß es möglich sein kann, gewisse Ungleichungen für die optimalen Lösungen aufzustellen, die für die entsprechenden zulässigen Bereiche definiert sind.

     

A duality theorem for continuous-time linear programming problems

Summary In dealing with dynamic economic policy models one encounters optimization problems whose objective function is an integral of a linear function of a finite number of continuous variables and whose constraints are linear integral inequalities. A set of intertemporal efficiency conditions (equilibrium conditions) yielding the optimal policy are given. By approximating the continuous problem by a set of discrete problems and appealing to a well known convergence theorem in functional analysis a continuous analog of the duality theorem is proved.

---

Zusammenfassung Bei der Beschäftigung mit dynamischen Modellen der ökonomischen Politik stößt man auf Optimierungsprobleme, deren Zielfunktion ein Integral einer linearen Funktion von einer endlichen Anzahl stetiger Variablen ist und deren Beschränkungen lineare Integral-Ungleichungen sind. Eine Menge intertemporaler Effizienz-Bedingungen (Gleichgewichtsbedingungen), die zur optimalen Politik führen, sind gegeben. Durch Approximation des kontinuierlichen Problems mittels einer Menge von diskreten Problemen und Berufung auf einen wohlbekannten Konvergenzsatz aus der Funktionalanalysis wird ein stetiges Analogon des Dualitätstheorems bewiesen.

---

---

The author is indebted to Mr.Arnold Faden for helpful suggestions and to ProfessorKarl A. Fox andGerhard Tintner for encouragement during the preparation of the paper. This research has been partially supported by a grant from the Ford Foundation to the School of Business Administration administered by the Center for Research in Management Science, University of California, Berkeley.

---

Vorgel. v.:G. Tintner.     

A note about linear inequality systems and duality

The optimization of a linear function on a closed convex set,F, can be stated as a linear semi-infinite program, sinceF is the solution set of (usually) infinite linear inequality systems, the so-called linear representations ofF. The duality properties of these programs are analyzed when the linear representation ofF ranges in some well known classes of linear inequality systems. This paper provides propositions on the duality diagrams of Farkas-Minkowski, canonically closed, compact and closed systems. Converse statements are also given.

---

Zusammenfassung Die Optimierung einer linearen Funktion auf einer konvexen abgeschlossenen MengeF kann als semi-infinites lineares Programm aufgefaßt werden, daF als Durchschnitt (unendlich) vieler Halbräume dargestellt werden kann. Es werden Dualitätseigenschaften dieser Programme untersucht, wobei von verschiedenen linearen Darstellungen fürF ausgegangen wird. Die Arbeit enthält Sätze über Dualitätsbeziehungen von Farkas-Minkowski, kanonisch abgeschlossene, kompakte und abgeschlossene Systeme. Es werden auch umgekehrte Beziehungen angegeben.

     

Unconstrained convex programming approach to linear programming

Recently, Fang proposed approximating a linear program in the Karmarkar standard form by adding an entropic barrier function to the objective function and derived an unconstrained dual concave program. We present in this note a necessary and sufficient condition for the existence of a dual optimal solution to the perturbed problem. In addition, a sharp upper bound of error estimation in this approximation scheme is provided.