求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

Maximum network flows with concave gains

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. Supported by a Grant-in-Aid for Scientific Research (No. 13780351 and No.14380188) from The Ministry of Education, Culture, Sports, Science and Technology of Japan.     

Decomposition Branch-and-Bound Based Algorithm for Linear Programs with Additional Multiplicative Constraints

This article presents an algorithm for globally solving a linear program (P) that contains several additional multiterm multiplicative constraints. To our knowledge, this is the first algorithm proposed to date for globally solving Problem (P). The algorithm decomposes the problem to obtain a master problem of low rank. To solve the master problem, the algorithm uses a branch-and-bound scheme where Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems in the algorithm are ordinary linear programs. Convergence of the algorithm is shown and a solved sample problem is given.     

Deepest point of a polyhedron and linear programming

Abstract

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

A practicable branch-and-bound algorithm for globally solving linear multiplicative programming

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

线性互补问题的并行多分裂松弛迭代算法

运用矩阵多重分裂理论,同时考虑并行计算与松弛迭代法,得到一类求解线性互补问题的高效数值算法．当问题的系数矩阵为对角元为正的H-矩阵或对称半正定矩阵时,证明了算法的全局收敛性；该算法与已有算法相比,具有计算量小、计算速度快等特点,因而特别适于求解大规模问题．数值试验的结果说明了算法的有效性．     

Solution of Complementarity Problems via Piecewise Linearization

My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

线性分式运输问题的一个解法

线性分式运输问题是线性分式规划问题的一种特殊情况，通常可以用线性分式规划问题的一般解法来解这类问题，本文针对分式运输问题的特点给出了一种简便的解法．     

非线性比式和问题的全局优化算法

In this paper,a global optimization algorithm is proposed for nonlinear sum of ratios problem(P).The algorithm works by globally solving problem(P1) that is equivalent to problem(P),by utilizing linearization technique a linear relaxation programming of the (P1) is then obtained.The proposed algorithm is convergent to the global minimum of(P1) through the successive refinement of linear relaxation of the feasible region of objective function and solutions of a series of linear relaxation programming.Nume...     

An O(n) algorithm for the multiple-choice knapsack linear program

An algorithm for solving the linear program associated with the multiple choice knapsack problem is described. The algorithm is shown to work in time linear in the number of variables. This improves the previously known best bound for this problem, and is optimal to within a constant factor.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region

A global optimization algorithm is presented for maximizing the sum of difference of convex functions ratios problem over nonconvex feasible region. This algorithm is based on branch and bound framework. To obtain a difference of convex programming, the considered problem is first reformulated by introducing new variables as few as possible. By using subgradient and convex envelope, the fundamental problem of estimating lower bound in the branch and bound algorithm is transformed into a relaxed linear programming problem which can be solved efficiently. Furthermore, the size of the relaxed linear programming problem does not change during the algorithm search. Lastly, the convergence of the algorithm is analyzed and the numerical results are reported.     

A finite,nonadjacent extreme-point search algorithm for optimization over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.The author owes thanks to two anonymous referees for their helpful comments.     

对称双正型线性互补问题的多重网格迭代解收敛性理论

多重网格法是七十年代产生并获得迅速发展的快速送代法.八十年代初,此方法开始应用于变分不等式的求解,其中包括一类互补问题,近十年来大量的数值实验证实,算法是成功的,而算法的收敛性理论也正在逐步建立,当A正定对称时的多重网格收敛性可见[3]和[7];[4]讨论了A半正定时的情况·本文考虑A为更广的一类矩阵:对称双正阵(见定义1.1),建立互补问题:     

An algorithm for optimizing over the weakly-efficient set

In this paper a bisecting search algorithm is developed for solving the problem (P) of optimizing a linear function over the set of weakly-efficient solutions of a multiple objective linear program. We show that problem (P) can arise in a variety of practical situations. The algorithm for solving problem (P) is guaranteed to find an optimal or approximately-optimal solution for the problem in a finite number of steps. Using a Fortran computer code called Conmin as an aid, we have solved ten test problems using our proposed algorithm. This preliminary computational experience seems to indicate that the algorithm is quite practical for relatively small problems.