A convergent criss-cross method

Our paper presents a new Criss-Cross method for solving linear programming problems. Starting from a neither primal nor dual feasible solution, we reach an optimal solution in finite number of steps if it exists. If there is no optimal solution, then we show that there is not primal feasible or dual feasible solution, We prove the finiteness of this procedure. Our procedure is not the same as the primal or dual simplex method if we have a primal or dual feasible solution, so we have constructed a quite new procedure for solving linear programming problems.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Certificates of Primal or Dual Infeasibility in Linear Programming

In general if a linear program has an optimal solution, then a primal and dual optimal solution is a certificate of the solvable status. Furthermore, it is well known that in the solvable case, then the linear program always has an optimal basic solution. Similarly, when a linear program is primal or dual infeasible then by Farkas's Lemma a certificate of the infeasible status exists. However, in the primal or dual infeasible case then there is not an uniform definition of what a suitable basis certificate of the infeasible status is.In this work we present a definition of a basis certificate and develop a strongly polynomial algorithm which given a Farkas type certificate of infeasibility computes a basis certificate of infeasibility. This result is relevant for the recently developed interior-point methods because they do not compute a basis certificate of infeasibility in general. However, our result demonstrates that a basis certificate can be obtained at a moderate computational cost.     

Recovering an optimal LP basis from an optimal dual solution

Given a linear program, we describe an approach for crossing over from an optimal dual solution to an optimal basic primal solution. It consists in restricting the dual problem to a small box around the available optimal dual solution then, resolving the associated modified primal problem.     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

On solving a primal geometric program by partial dual optimization

The several published methods for mapping a dual solution estimate to a primal solution estimate in posynomial geometric programming provide no criteria for deciding how much deviation from primal feasibility, or discrepancy between the primal and dual objective function values, should be permitted before the primal solution estimate is accepted by the designer. This paper presents a new and simple dual-to-primal conversion method that uses the cost coefficients to provide a sound economic criterion for determining when to accept a primal solution estimate. The primal solution estimate generated is the exact solution to a modified primal obtained from the given primal by modifying the cost coefficients, with the exponent matrix left unchanged. The method is shown to have desirable properties when coupled with a convergent dual algorithm.     

线性规划的最钝角CRISS-CROSS算法

1 引言 考虑如下标准线性规划问题 minimize c~Tx (1) subject to Ax=b, x≥0 其中A∈R~(m×n) (m相似文献   

Application of the alternating direction method of multipliers to separable convex programming problems

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established.     

Sensitivity analysis in geometric programming: Theory and computations

This paper surveys the main developments in the area of sensitivity analysis for geometric programming problems, including both the theoretical and computational aspects. It presents results which characterize solution existence, continuity, and differentiability properties for primal and dual geometric programs as well as the optimal value function differentiability properties for primal and dual programs. It also provides an overview of main computational approaches to sensitivity analysis in geometric programming which attempt to estimate new optimal solutions resulting from perturbations in some problem parameters.     

On the optimal value function for certain linear programs with unbounded optimal solution sets

Often, the coefficients of a linear programming problem represent estimates of true values of data or are subject to systematic variations. In such cases, it is useful to perturb the original data and to either compute, estimate, or otherwise describe the values of the functionf which gives the optimal value of the linear program for each perturbation. If the right-hand derivative off at a chosen point exists and is calculated, then the values off in a neighborhood of that point can be estimated. However, if the optimal solution set of either the primal problem or the dual problem is unbounded, then this derivative may not exist. In this note, we show that, frequently, even if the primal problem or the dual problem has an unbounded optimal solution set, the nature of the values off at points near a given point can be investigated. To illustrate the potential utility of our results, their application to two types of problems is also explained.This research was supported, in part, by the Center for Econometrics and Decision Sciences, University of Florida, Gainesville, Florida.The author would like to thank two anonymous reviewers for their most useful comments on earlier versions of this paper.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

Perturbing the Dual Feasible Region for Solving Convex Quadratic Programs

A dual l _p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l _p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming.     

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.     

整数规划的渐进强对偶方法

虽然整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。该文提出一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索。     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.