线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

Global solutions of mathematical programs with intrinsically concave functions

An implicit enumeration technique for solving a certain type of nonconvex program is described. The method can be used for solving signomial programs with constraint functions defined by sums of quasiconcave functions and other types of programs with constraint functions called intrinsically concave functions. A signomial-type example is solved by this method. The algorithm is described together with a convergence proof. No computational results are available at present.     

On the Convergence of Cone Splitting Algorithms with ω-Subdivisions

We present a convergence proof of the Tuy cone splitting algorithm with a pure -subdivision strategy for the minimization of a concave function over a polytope. The key idea of the convergence proof is to associate with the current hyperplane a new hyperplane that supports the whole polytope instead of only the portion of it contained in the current cone. A branch-and-bound variant of the algorithm is also discussed.     

一个正定几何规划的对偶算法及收敛性

由于正定几何规划的对偶规划只含线性等式约束和非负约束,处理起来似乎要方便得多.然而,实际上许多对偶算法实施起来却往往失败(见[2,8,9]),这是由于对偶规划所特有的“块性质”以及目标函数在某些点的不可微性质引起的.因此,近年来主要的努力集中在克服这二个困难上。主要的工作有:1975年Beck和Ecker的修正凹单纯形     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

A New Duality Approach to Solving Concave Vector Maximization Problems

We introduce a special class of monotonic functions with the help of support functions and polar sets, and use it to construct a scalarized problem and its dual for a vector optimization problem. The dual construction allows us to develop a new method for generating weak efficient solutions of a concave vector maximization problem and establish its convergence. Some numerical examples are given to illustrate the applicability of the method.     

Finite Convergence of the Partial Inverse Algorithm

In Refs. 1–2, Lefebvre and Michelot proved the finite convergence of the partial inverse algorithm applied to a polyhedral convex function by means of some suitable tools of convex analysis. They obtained their result under some assumptions on the primal and dual solution sets. The aim of this note is to show that the proof can be extended to remove the nasty assumption on the dual solution set. The result is in conformity with the proof given in Ref. 3, which has been obtained using the concept of folding.     

Chebyshev Approximation to Data by Positive Sums of Exponentials

The problem is considered of calculating Chebyshev approximationsto given data by sums of exponentials with positive coefficients,where the number of terms in the sum has to be obtained as partof the process. An exchange procedure based on linear programmingis developed for the estimation of the exponents, and this ismade efficient by the use of postoptimality theory and the applicationof the dual simplex algorithm. Rapid convergence to a best approximationcan then be obtained by the application of Newton's method tothe characterization conditions interpreted as a nonlinear systemof equations. The Newton step can be determined through thesolution of a quadratic programming problem, and advantage istaken of the structure so that the calculation can be simplifiedwithout inhibiting a second-order convergence rate. Numericalresults are presented for the application of an algorithm basedon these ideas to a number of data sets which have appearedin the literature.     

A generalization of the potential method for conditional maxima on the Banach,reflexive spaces

Summary The paper discusses conditions of the convergence of a potential method. The method consists of approximating a constrained maximum by unconstrained maxima of a potential function. A proof of the convergence is given when dealing with the local nonsingular maximum of a locally concave functional on a locally convex set in a Banach reflexive space. Some examples of applications are discussed. Finally there is presented (as an open problem) a suggestion for further weakening of the conditions of convergence.     

Facial Reduction Algorithms for Conic Optimization Problems

In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems.     

Comparison of Four Goal Programming Algorithms

A major limitation in the use of goal programming has been the lack of an efficient algorithm for model solution. Schniederjans and Kwak recently published a proposal for more efficient solution of goal programming models utilizing dual simplex procedures. A goal programming algorithm based upon that method has been coded, as well as a revised, simplex-based algorithm. These algorithms are compared in terms of accuracy and time requirements with algorithms previously presented by Lee and by Arthur and Ravindran. Solution times for a series of 12 goal programming models are presented. The dual simplex method appears to have superior computational times for models with a large proportion of positive deviational variables in the solution. The revised simplex algorithm appears more consistent in time and accuracy for general goal programming models.     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.     

A modified reduced gradient method for dual posynomial programming

In this paper, we present a method for solving the dual of a posynomial geometric program based on modifications of the reduced gradient method. The modifications are necessary because of the numerical difficulties associated with the nondifferentiability of the dual objective function. Some preliminary numerical results are included that compare the proposed method with the modified concave simplex method of Beck and Ecker of Ref. 1.This research was supported in part by the National Science Foundation, Grant No. MCS75-09443-A01.The authors sincerely thank P. Vandeputte for his computing assistance. We also wish to thank T. Magnanti and unknown referees for helpful criticism.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

Linear Programs With an Additional Separable Concave Constraint

In this paper, we develop two algorithms for globally optimizing a special class of linear programs with an additional concave constraint. We assume that the concave constraint is defined by a separable concave function. Exploiting this special structure, we apply Falk-Soland's branch-and-bound algorithm for concave minimization in both direct and indirect manners. In the direct application, we solve the problem alternating local search and branch-and-bound. In the indirect application, we carry out the bounding operation using a parametric right-hand-side simplex algorithm.     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.