The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

The emergence of nonlinear programming: interactions between practical mathematics and mathematics proper

Conclusion  It was the duality theorem for linear programming-that is, a purely theoretical result-that sparked the interest of Kuhn and Tucker. It was the duality theory they wanted to extend to the general (quadratic) nonlinear case. It is in this respect that I find the development of the duality theorem in linear programming so crucial for the emergence of nonlinear programming.     

非凸向量集值优化Benson真有效解的最优性条件与对偶

在无需偏序锥内部非空的情况下给出了非凸约束向量集值优化Benaon真有效解一种加细的最优性条件，并建立了向量集值优化Benson真有效解一种改进的Lagrange乘子型对偶，它比已有的Lagrange乘子型对偶具有较好的对偶性。     

On fuzzy linear programming

Fuzzy multi-objective and fuzzy Goal Programming are discussed in connection with several membership functions which are used to transform the original problem into three equivalent linear programming problems. Existence and uniqueness theorems are given. Fuzzy duality is presented, and an extension of the initial fuzzy problem arises immediately from it.     

A note on Khatchian's algorithm

A short proof of some properties of Khatchian's algorithm is presented using the duality theorem of linear programming.Dedicated to R. Bellman     

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.     

Congruence computations in principal arithmetical varieties

This paper is a continuation of the earlier paper by the same authors in which a primary result was that every arithmetical affine complete variety of finite type is a principal arithmetical variety with respect to an appropriately chosen Pixley term. The paper begins by presenting an extension of this result to all finitely generated congruences and, as an example, constructs a closed form solution formula for any finitely presented system of pairwise compatible congruences (the Chinese remainder theorem). It is also shown that in all such varieties the meet of principal congruences is also principal, and finally, if a minimal generating algebra of the variety is regular, it is shown that the variety is also regular and the join of principal congruences is again principal.     

Homogeneous programming and symmetrization

A polyhedral or piecewise linear homogeneous programming problem is shown through symmetrization to be equivalent to a linear one, yielding a duality theorem for polyhedral homogeneous programming. As a consequence of this duality, it follows that the simplex method can be used to solve such problems.     

Fractional multi-commodity flow problem: Duality and optimality conditions

This paper deals with multi-commodity flow problem with fractional objective function. The optimality conditions and the duality concepts of this problem are given. For this aim, the fractional linear programming formulation of this problem is considered and the weak duality, the strong direct duality and the weak complementary slackness theorems are proved applying the traditional duality theory of linear programming problems which is different from same results in Chadha and Chadha (2007) [1]. In addition, a strong (strict) complementary slackness theorem is derived which is firstly presented based on the best of our knowledge. These theorems are transformed in order to find the new reduced costs for fractional multi-commodity flow problem. These parameters can be used to construct some algorithms for considered multi-commodity flow problem in a direct manner. Throughout the paper, the boundedness of the primal feasible set is reduced to a weaker assumption about solvability of primal problem which is another contribution of this paper. Finally, a real world application of the fractional multi-commodity flow problem is presented.     

Symmetric dual quadratic program in complex space

Symmetric dual quadratic program in complex space is presented and some duality theorems are proved. Self-dual linear and quadratic programs in complex space are formed and self-duality theorem is extended to these cases.     

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.     

多目标规划的 Lagrange 对偶与标量化定理

定义与问题设 K(?)R~p 为内部非空的点锥,则 K 在 R~p 上确定了如下偏序:x≦K.y(?)y-x∈K,xk(?)}.     

An elementary proof of the duality theorem of linear programming

A constructive and elementary proof of the duality theorem of linear programming is presented. The proof utilizes the new concept of an embedded core program, which is a program generated from a linear program with finite optimum by successively removing constraints until no remaining constraints can be deleted without changing the optimal solution.     

An extension of Chevalley's theorem to congruences modulo prime powers

Olson determined, for each finite abelian p-group G, the maximal length of a sequence of elements of G such that no subsequence has zero sum, thus settling (at least for these groups) a problem raised by Davenport in connection with factorization in number fields. This problem is equivalent to one on simultaneous linear congruences to which one seeks solutions with the variables restricted to the values 0 and 1. In the present note, the analogous problem for forms of arbitrary degree is settled, again with best possible results. The main tool is an extension of Chevalley's theorem on finite fields to congruences modulo prime powers. This in turn is deduced from Chevalley's theorem by a simple device which circumvents the use of Witt vectors.     

On duality theorems

There are several examples in linear algebra and number theory of theorems which are formally similar to the well-known duality theorem of linear programming. The object of this paper is to present a general setting in which we can state and prove a simple criterion for such duality theorems to hold.     

A dual approach to solve the fuzzy linear programming problem

A concept of fuzzy objective based on the Fuzzification Principle is presented. In accordance with this concept, the Fuzzy Linear Mathematical Programming problem is easily solved. A relationship of duality among fuzzy constraints and fuzzy objectives is given. The dual problem of a Fuzzy Linear Programming problem is also defined.     

Note: continuous-time linear programming problems revisited

This note is aimed to correct the strong duality theorem of previous paper regarding the continuous-time linear programming problems. The argument presented in the previous paper can only be used to prove the case of piecewise continuous functions in which the discontinuities are the left-continuities.     

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 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.     

Strong duality and minimal representations for cone optimization

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with Semidefinite Programming, SDP.