A multiplicative barrier function method for linear programming

A simple Newton-like descent algorithm for linear programming is proposed together with results of preliminary computational experiments on small- and medium-size problems. The proposed algorithm gives local superlinear convergence to the optimum and, experimentally, shows global linear convergence. It is similar to Karmarkar's algorithm in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is protective geometry needed, but only affine geometry suffices.The works of the first author and the second were supported in part by the Grant-in-Aid for Scientific Research (B) 60460130 (1985) and by the Grant-in-Aid for Encouragement of Young Scientists (A) 60790046 (1985), respectively, of the Ministry of Education, Science and Culture of Japan.     

A nonisolated optimal solution of general linear multiplicative programming problems

This article presents a finite branch-and-bound algorithm for globally solving general linear multiplicative programming problems (GLMP). The proposed algorithm is based on the recently developed theory of monotonic optimization. The proposed algorithm provides a nonisolated global optimal solution, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. It can be shown by the numerical results that the proposed algorithm is effective and the computational results can be gained in short time.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations.The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

结合分支定界法和线性规划的摄像机位姿估计

介绍了一种新的利用对应点估计摄像机位姿的算法。通常情况下,摄像机位姿估计可以转化为一个最优化问题,现有算法将问题转换成一个序列二阶锥规划问题,通过对旋转矩阵所在空间进行分支定界搜索来求取全局最优解。对现有算法进行改进,通过将二阶锥约束松弛为线性约束,提出了一种结合分支定界法和线性规划方法的全局优化算法。该算法不仅能够求得全局最优解,而且算法速度较现有算法提高了一倍以上。最后通过模拟数据和真实数据对该算法进行了验证,结果表明了该算法的准确性和高效性。     

Maximizing for the sum of ratios of two convex functions over a convex set

This paper presents an algorithm for globally maximizing a sum of convex–convex ratios problem with a convex feasible region, which does not require involving all the functions to be differentiable and requires that their sub-gradients can be calculated efficiently. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme in which the main computational effort involves solving a sequence of linear programming subproblems. Because of these properties, the algorithm offers a potentially attractive means for globally solving the sum of convex–convex ratios problem over a convex feasible region. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.     

A multiplicative barrier function method for linear programming

A simple Newton-like descent algorithm for linear programming is proposed together with results of preliminary computational experiments on small- and medium-size problems. The proposed algorithm gives local superlinear convergence to the optimum and, experimentally, shows global linear convergence. It is similar to Karmarkar's algorithm in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is protective geometry needed, but only affine geometry suffices.     

Multiple objective branch and bound for mixed 0-1 linear programming: Corrections and improvements for the biobjective case

This work addresses the correction and improvement of Mavrotas and Diakoulaki's branch and bound algorithm for mixed 0-1 multiple objective linear programs. We first elaborate the issues encountered by the original algorithm and then propose a corrected version for the biobjective case using an exact representation of the nondominated set associated with an appropriate update procedure. Then we introduce several improvements using better bound sets and branching strategies and finally present some experiments to study the effectiveness of our propositions.     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

基于线性松弛方法的网络故障链路诊断

为解决通信网络中端到端测量定位故障链路的NP难问题,提出了一种新的松弛布尔约束的诊断方法。首先将网络中的路径状态和链路状态的关系建模为布尔代数方程,而故障定位的本质即满足该布尔方程条件的优化求解;然后,依据该优化表达式判断其NP性来源于链路状态的布尔约束（正常/故障）,通过将布尔约束松弛为线性约束,所提方法将问题简单地转换为线性规划（LP）问题,线性规划问题非常容易求解并可以由任何LP求解器来得到故障链路集合。在真实网络拓扑中进行了链路故障诊断仿真实验,实验结果表明,所提方法与现有的经典启发式算法——TOMO相比,降低了5%~30%的误诊率。     

A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems

In this paper we formulate necessary and sufficient conditions for an arbitrary polyhedral set to be a positively invariant set of a linear discrete-time system. Polyhedral cones and linear subspaces are included in the analysis. A linear programming algorithm is presented that enables practical application of the results stated in this paper.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.     

A multiplicative multisplitting method for solving the linear complementarity problem

The convergence of the multiplicative multisplitting-type method for solving the linear complementarity problem with an H-matrix is discussed using classical and new results from the theory of splitting. This directly results in a sufficient condition for guaranteeing the convergence of the multiplicative multisplitting method. Moreover, the multiplicative multisplitting method is applied to the H-compatible splitting and the multiplicative Schwarz method, separately. Finally, we establish the monotone convergence of the multiplicative multisplitting method under appropriate conditions.     

A branch and bound method for isolation of faulty variables through missing variable analysis

Fault detection and diagnosis is a critical approach to ensure safe and efficient operation of manufacturing and chemical processing plants. Although multivariate statistical process monitoring has received considerable attention, investigation into the diagnosis of the source or cause of the detected process fault has been relatively limited. This is partially due to the difficulty in isolating multiple variables, which jointly contribute to the occurrence of fault, through conventional contribution analysis. In this work, a method based on probabilistic principal component analysis is proposed for fault isolation. Furthermore, a branch and bound method is developed to handle the combinatorial nature of problem involving finding the contributing variables, which are most likely to be responsible for the occurrence of fault. The efficiency of the method proposed is shown through benchmark examples, such as Tennessee Eastman process, and randomly generated cases.     

An experimental comparison of the new goal programming and the linear programming approaches in the two-group discriminant problems

The aim of this article is to consider a new linear programming and two goal programming models for two-group classification problems. When these approaches are applied to the data of real life or of simulation, our proposed new models perform well both in separating the groups and the group–membership predictions of new objects. In discriminant analysis some linear programming models determine the attribute weights and the cut-off value in two steps, but our models determine simultaneously all of these values in one step. Moreover, the results of simulation experiments show that our proposed models outperform significantly than existing linear programming and statistical approaches in attaining higher average hit-ratios.     

Approximate linear programming for networks: Average cost bounds

This paper uses approximate linear programming (ALP) to compute average cost bounds for queueing network control problems. Like most approximate dynamic programming (ADP) methods, ALP approximates the differential cost by a linear form. New types of approximating functions are identified that offer more accuracy than previous ALP studies or other performance bound methods. The structure of the infinite constraint set is exploited to reduce it to a more manageable set. When needed, constraint sampling and truncation methods are also developed. Numerical experiments show that the LPs using quadratic approximating functions can be easily solved on examples with up to 17 buffers. Using additional functions reduced the error to 1–5% at the cost of larger LPs. These ALPs were solved for systems with up to 6–11 buffers, depending on the functions used. The method computes bounds much faster than value iteration. It also gives some insights into policies. The ALPs do not scale to very large problems, but they offer more accurate bounds than other methods and the simplicity of just solving an LP.     

A linear programming approximation to the eigenvector method in the analytic hierarchy process

Eigenvector method (EM) is a well-known approach to deriving priorities from pairwise comparison matrices in the analytic hierarchy process (AHP), which requires the solution of a set of nonlinear eigenvalue equations. This paper proposes an approximate solution approach to the EM to facilitate its computation. We refer to the approach as a linear programming approximation to the EM, or LPAEM for short. As the name implies, the LPAEM simplifies the nonlinear eigenvalue equations as a linear programming for solution. It produces true weights for perfectly consistent pairwise comparison matrices. Numerical examples are examined to show the validity and effectiveness of the proposed LPAEM and its significant advantages over a recently developed linear programming method entitled LP-GW-AHP in rank preservation.