Search

In this paper, we consider the min–max linear fractional programming problem (MLFP) which is NP-hard. We first introduce some auxiliary variables to derive an equivalent problem of the problem (MLFP). An outer space branch-and-bound algorithm is then designed by integrating some basic operations such as the linear relaxation method and branching rule. The global convergence of the proposed algorithm is proved by means of the subsequent solutions of a series of linear relaxation programming problems, and the computational complexity of the proposed algorithm is estimated based on the branching rule. Finally, numerical experimental results demonstrate the proposed algorithm can be used to efficiently compute the globally optimal solutions of test examples. [ABSTRACT FROM AUTHOR]

This paper presents an image space branch-reduction-bound algorithm for solving a class of multiplicative problems (MP). First of all, by introducing auxiliary variables and taking the logarithm of the objective function, an equivalent problem (EP) of the problem (MP) is obtained. Next, by using a new linear relaxation technique, the parametric linear relaxation programming (PLRP) of the equivalence problem (EP) can be established for acquiring the lower bound of the optimal value to the problem (EP). Based on the characteristics of the objective function of the equivalent problem and the structure of the branch-and-bound algorithm, some region reduction techniques are constructed for improving the convergence speed of the algorithm. Finally, the global convergence of the algorithm is proved and its computational complexity is estimated, and numerical experiments are reported to indicate the higher computational performance of the algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an efficient outer space branch-and-bound algorithm for globally solving a minimax linear fractional programming problem (MLFP), which has a wide range of applications in data envelopment analysis, engineering optimization, management optimization, and so on. In this algorithm, by introducing auxiliary variables, we first equivalently transform the problem (MLFP) into the problem (EP). By using a new linear relaxation technique, the problem (EP) is reduced to a sequence of linear relaxation problems over the outer space rectangle, which provides the valid lower bound for the optimal value of the problem (EP). Based on the outer space branch-and-bound search and the linear relaxation problem, an outer space branch-and-bound algorithm is constructed for globally solving the problem (MLFP). In addition, the convergence and complexity of the presented algorithm are given. Finally, numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The quadratic sum-of-ratios fractional program problem has a broad range of applications in practical problems. This article will present an efficient branch-and-bound algorithm for globally solving the quadratic sum-of-ratios fractional program problem. In this algorithm, lower bounds are computed by solving a series of parametric relaxation linear programming problems, which are established by utilizing new parametric linearizing technique. To enhance the computational speed of the proposed algorithm, a rectangle reducing tactic is used to reject a part of the investigated rectangle or the whole rectangle where there does not contain any global optimal solution of the quadratic sum-of-ratios fractional program problem. Compared with the known approaches, the proposed algorithm does not need to introduce new variables and constraints. Therefore, the proposed algorithm is more suitable for application in engineering. [ABSTRACT FROM PUBLISHER]

In this paper, we present a range division and compression algorithm for effectively solving quadratically constrained sum of quadratic ratios problem. In this algorithm, a novel linear relaxation approach is proposed for deriving linear relaxation programming, which is used to obtain a lower bound of the optimal value of this problem. By utilizing the known upper bound and the constructed linear relaxation programming, a range compression technique is presented to contract the investigated range. Thus, a range division and compression algorithm is constructed and its convergence is proved. Compared with the current approaches, the proposed algorithm does not need to introduce new variables and constraints and it does not need to employ additional procedure to calculate the intervals of numerator and denominator of each ratio, so that this will facilitate the implementation of this algorithm. Finally, numerical comparisons with the known algorithms demonstrate the advantage of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a novel range division and contraction approach for globally solving nonconvex quadratic program with quadratic constraints. By constructing new underestimating linear relaxation functions, we can transform the initial nonconvex quadratic program problem into a linear program relaxation problem. By employing a branch and bound scheme with a range contraction approach, we describe a novel global optimization algorithm for effectively solving nonconvex quadratic program with quadratic constraints. Finally, the global convergence of the proposed algorithm is proved and numerical experimental results demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents a deterministic global optimization algorithm for solving minimax linear fractional programming (MLFP). In this algorithm, a new linearization technique is proposed, which uses more information of the objective function of the (MLFP) than other techniques. By utilizing this new linearization technique, the initial nonconvex programming problem (MLFP) is reduced to a sequence of linear relaxation programming (LRP) problems, which can provide reliable lower bound of the optimal value. The proposed algorithm is convergent to the global minimum of the (MLFP) through the successive refinement of the feasible region and solutions of a series of the (LRP). Compared with the known algorithms, numerical results show that the proposed algorithm is robust and effective. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ϵ-global optimum. [Copyright &y& Elsevier]

Abstract: A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this technical note, we give a short extension application for a deterministic global optimization algorithm proposed in [Y. Ji, K.-C. Zhang, S.-J. Qu, A deterministic global optimization algorithm, Applied Mathematics and Computation 185 (2007) 382–387]. Actually our result is slightly more general, since it does not impose any special sign restrictions on numerators and denominators of the ratios. The only assumption is that the denominators of the ratios are nonzero over the feasible region of the problem. For clarity we use the same notations for the different equivalent problems and the corresponding relaxation linear programming (RLP) as done in Ji et al. (2007). [Copyright &y& Elsevier]

Abstract: This paper presents a global optimization algorithm for a class of multiplicative programming with exponent under multiplicative constraints (MPE). By utilizing equivalent problem of MPE in the sense that they have the same optimal solution, tangential hypersurfaces and concave envelope approximations a linear relaxation of equivalent problem is received. Thus the initial nonconvex programming problem (MPE) is reduced to a sequence of linear programming problems through the successive refinement of a linear relaxation of feasible region of the objective function. The proposed algorithm is convergent to the globally optimal solution of MPE by means of the subsequent solutions of a series of linear programming problems. Numerical results indicate that the proposed algorithm is extremely robust and can be used successfully to solve global minimum of MPE on microcomputer. [Copyright &y& Elsevier]