Search

For the nonconvex quadratic programming problem, a new linear programming relaxation bound-and-reduce algorithm is proposed and its convergence is proved. In this algorithm, a new hyper-rectangle partition technique and a new linear programming relaxation tactics are used. At the same time, the hyper-rectangular reduction method is used to raise its convergent speed. The numerical results demonstrate the effectiveness and feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm. [Copyright &y& Elsevier]

In this paper, a new relaxation bounding method is proposed for a class of linear multiplicative programs. Although the 2 p − 1 variable is introduced in the construction of equivalence problem, the branch process of the algorithm is only carried out in p − dimensional space. In addition, a super-rectangular reduction technique is also given to greatly improve the convergence rate. Furthermore, we construct an output-space branch-and-bound reduction algorithm based on solving a series of linear programming sub-problems, and prove the convergence and computational complexity of the algorithm. Finally, to verify the feasibility and effectiveness of the algorithm, we carried out a series of numerical experiments and analyzed the advantages and disadvantages of the algorithm by numerical results. [ABSTRACT FROM AUTHOR]