An outcome branch and bound algorithm for affine multiplicative problems using piecewise linear approximation techniques

The affine multiplicative programming problem, as a non-convex optimization problem with a strong practical background, is both meaningful and challenging. This paper proposes an effective algorithm capable of obtaining the global optimal solution. First, we transform the problem into an equivalent one through variable substitution. Second, to obtain an easily computable lower bound for the optimal solution, we employ a novel piecewise linear approximation technique to convert the problem into a linear relaxation programming problem. Subsequently, the paper introduces an algorithm based on the branch-and-bound framework, incorporating various outcome space acceleration techniques to enhance convergence speed. Additionally, we provide a convergence proof of the algorithm to ensure its reliability and analyse its computational complexity. Finally, numerical experiments are conducted to verify the algorithm's effectiveness and robustness.