Semi-infinite programming duality for order restricted statistical inference models

The equivalence of multinomial maximum likelihood and the isotonic projection problem: $$\inf \left\{ {\sum\limits_{i = 1}^n {p_i \ln (p_i /r_i )|p \in K,a convex} {\mathbf{ }}subset of the probability vectors{\mathbf{ }}p} \right\}$$ can be established using Fenchel's Duality Theorem and subgradient and complementary slackness relationships of convex analysis, all taking place over the real numbers. In this paper non-Archimedean polynomial subgradients (Jeroslow/Kortanek '71, Blair '74, Borwein '80, and Kortanek/Soyster '81) are employed for the case where some of the observed values of the random vector are zero, corresponding to “zero counts in the traditional multinomial setting.” With an appropriate linear semi-infinite programming dual pair it is shown that a vector solves the multinomial problem if and only if it converts to a solution of the isotonic projection problem. The development parallels the one of Robertson/Wright/Dykstra '88, where for the zero counts case the authors adjoin “-∞” to the real numbers and define ln(0)=-∞.     

Comparison of duality models in fractional linear programming

Summary This paper deals with the duality models in fractional linear programming presented in the last years bySwarup, Kaka, Sharma andSwarup and other authors.

---

Zusammenfassung Der Aufsatz befaßt sich mit Dualitätsmodellen für Linear Fractional Programming, die in den letzten Jahren vonSwarup, Kaka, Sharma undSwarup sowie von anderen Autoren angegeben wurden.

---

---

This work was sponsored by the Grant No. A 7329 from the National Research Council of Canada.     

The use of linear programming duality in mixed integer programming

This paper is about the primal-dual relationship in a mixedinteger programming problem (MIP) in which integer variablesare binary. It shows how the primal-dual relationship of a linearprogramming problem (LP) can be used to advantage in MIPs. Thecentral idea is to look conceptually at the nature of all possibleLPs that arise from all possible settings for the discrete variablesin order to deduce general properties of the solution set. Afterdeveloping the relevant theory, we show the usefulness of thisaproach by applying it to three totally different problems.New results are derived for the method of least median of squaresin robust regression, the problem of rectilinear obnoxious-facilitylocation, and the problem of finding a fixed-size rectanglecontaining the minimum weight of points.     

Conditional value at risk and related linear programming models for portfolio optimization

Many risk measures have been recently introduced which (for discrete random variables) result in Linear Programs (LP). While some LP computable risk measures may be viewed as approximations to the variance (e.g., the mean absolute deviation or the Gini’s mean absolute difference), shortfall or quantile risk measures are recently gaining more popularity in various financial applications. In this paper we study LP solvable portfolio optimization models based on extensions of the Conditional Value at Risk (CVaR) measure. The models use multiple CVaR measures thus allowing for more detailed risk aversion modeling. We study both the theoretical properties of the models and their performance on real-life data.     

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.     

A converse duality theorem on higher-order dual models in nondifferentiable mathematical programming

We consider in this paper Mond–Weir type higher-order dual models in nondifferentiable mathematical programming introduced by Mishra and Rueda (2002, J. Math. Anal. Appl. 272, 496–506). We give a converse duality theorem on Mond-Weir type higher-order dual model under mild assumptions.     

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.     

Pseudo-invexity and duality in nonlinear programming

The purpose of this paper is to study various duality results in nonlinear programming for pseudo-invex functions. Such results were known in the literature for invex functions.     

Uniform LP duality for semidefinite and semi-infinite programming

Recently, a semidefinite and semi-infinite linear programming problem (SDSIP), its dual (DSDSIP), and uniform LP duality between (SDSIP) and (DSDSIP) were proposed and studied by Li et al. (Optimization 52:507–528, 2003). In this paper, we show that (SDSIP) is an ordinary linear semi-infinite program and, therefore, all the existing results regarding duality and uniform LP duality for linear semi-infinite programs can be applied to (SDSIP). By this approach, the main results of Li et al. (Optimization 52:507–528, 2003) can be obtained easily.     

Lexicographical order and duality in multiobjective programming

This paper studies the applications of lexicographical order relation for vectors in the mathematical theory of multiobjective programming. We show that any Pareto minimum of an unconstrained convex. problem is the lexicographical minimum for the problem associated to a matrix multiplier having lexicographical positive columns. A similar result is also obtained for inequality constrained problems.Our approach to the theory of duality follows the pattern of Jahn [3], but we substitute vectors by matrices in the formulation of the dual problem and the usual scalar order relation by the lexicographical order relation. This allows us to state the Strong Duality Theorem in terms of Pareto minima and to eliminate some regularity assumptions.     

Surrogate duality in a branch-and-bound procedure for integer programming

The existence of efficient techniques such as subgradient search for solving Lagrangean duals has led to some very successful applications of Lagrangean duality in solving specially structured discrete problems. While surrogate duals have been theoretically shown to provide stronger bounds, the complexity of surrogate dual multiplier search has discouraged their employment in solving integer programs. We have recently suggested a new strategy for computing surrogate dual values that allows us to directly use established Lagrangean search methods for exploring surrogate dual multipliers. This paper considers the problem of incorporating surrogate duality within a branch-and-bound procedure for solving integer programming problems. Computational experience with randomly generated multiconstraint knapsack problems is also reported.     

An abstract symmetric framework for duality in mathematical programming

The paper offers an abstract structure called environment (of mathematical programming) in which a pair of dual programs is settled symmetrically. Given an environment, the concepts of an optimization program, its dual and the associated Lagrangean are formalized and studied. The usual asymmetries in certain types of mathematical programming are due to selection of asymmetric environments. Common types of programming like: linear, nonlinear, convex, integer etc. are reviewed in the proposed framework.     

Non-differentiable pseudo-convex functions and duality for minimax programming problems

Optimality results are derived for a general minimax programming problem under non-differentiable pseudo-convexity assumptions. A dual in terms of Dini derivatives is introduced and duality results are established. Finally, two duals again in terms of Dini derivatives are introduced for a generalized fractional minimax programming problem and corresponding results are studied.     

Saddle point and generalized convex duality for multiobjective programming

In this paper we consider the dual problems for multiobjective programming with generalized convex functions. We obtain the weak duality and the strong duality. At last, we give an equivalent relationship between saddle point and efficient solution in multiobjective programming.     

Base duality theorem for stochastic and parametric linear programming

Summary Consider the primal and dual bases of a basic optimal solution to a linear-programming problem with a given set of parameters (coefficients of objective function, technology matrix, and restriction vector). For brevity, call those bases themselves optimal. If the parameters are subject to variation (controlled or uncontrolled according as one deals with parametric or stochastic programming, respectively) the initial bases are optimal throughout certain subregions of parameter space, termed optimality regions of the respective bases.It is shown that the optimality regions of primal and dual bases are identical.

---

Zusammenfassung Betrachtet werden die Primär- und Dualbasen einer optimalen Basislösung eines linearen Programms mit einer gegebenen Parametermenge (d. h. Koeffizienten der Zielfunktion, Koeffizienten der Matrix und des Beschränkungsvektors). Der Kürze halber seien diese Basen selbst optimal genannt. Die Anfangsbasen bleiben optimal innerhalb gewisser Teilbereiche des Parameterraumes, bezeichnet als Optimalitätsbereiche der jeweiligen Basen, wenn die Parameter gewissen Variationen unterliegen (vorgegeben oder nicht, je nachdem, ob es sich um parametrisches oder stochastisches Programmieren handelt).Es wird gezeigt, daß die Optimalitätsbereiche der Primär- und Dualbasen übereinstimmen.

---

---

This research has been carried out in association with, and with partial support from the National Science Foundation, Project Nr. 401-04-07 at Iowa State University.     

Lagrangian duality and saddle points for sparse linear programming

The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.     

Lexicographic regularization and duality for improper linear programming problems

A new approach to the optimal lexicographic correction of improper linear programming problems is proposed. The approach is based on the multistep regularization of the classical Lagrange function with respect to primal and dual variables simultaneously. The regularized function can be used as a basis for generating new duality schemes for problems of this kind. Theorems on the convergence and numerical stability of the method are presented, and an informal interpretation of the obtained generalized solution is given.     

Generalized invexity and duality in multiobjective nonlinear programming

The purpose of this paper is to study the duality theorems in cone constrained multiobjective nonlinear programming for pseudo-invex objectives and quasi-invex constrains and the constraint cones are arbitrary closed convex ones and not necessarily the nonnegative orthants.