Approximation Schemes For Generalized Multiplicative Programming Problems

Generalized multiplicative programming problems are classified as non-convex opti-mization problems, and may have several local minima, which makes solving this class of problems more challenging. Meanwhile, generalized multiplicative programming problems play an important role in many aspects such as economics?engineering and so on. In re-cent years, some researchers utilize heuristic algorithms to solve these problems. Heuristic algorithms may solve problems to obtain their optimal solutions. However, heuristic algo-rithm can not guarantee the quality of its execution efficiency. Therefore, it has become an exploration direction of current researchers for searching an algorithm, both ensuring execution efficiency and providing theoretical analysis of operation time, for solving global optimization problems. In this paper, two special multiplicative programming problems are solved by exploiting different approximation algorithms based on the characteristics of problems themselves. Main content is summarized as follows.In Chapter 1, we introduce the global optimization problems considered in this paper and research status, background and significance of these issues. And the main work is given finally.In Chapter 2, we consider a class of generalized linear multiplicative problems. The original problems are transformed as their equivalent problems firstly. And then estimate the upper and lower bounds of the selected objective functions in the feasible region, and sub-divide the box(or hyper-rectangle) such that in each dimension, the cutting- ratio is same. Thus, a polynomial size non-uniform grid is constructed. According to characteristics of problems themselves, combining the non-uniform grid with parametric linear method, we propose an approximate algorithm. The feasibility and effectiveness of the algorithm is proved by numerical results. And we also provide computational complexity of the algorithm.In Chapter 3, a class of generalized fractional programming problems are considered. Firstly, an appropriate box is constructed on account of the upper estimation and lower estimation of the chosen objective function in the feasible region, depending on natures of problems themselves. And then search grid nodes along diagonal of the box, starting from the lower bound of the box. Thus, transform the original problem as a limit of subproblems with related to grid nodes. Finally, we get the global approximate optimal solution by solving every subproblem associated with each grid node. Thus, an approx-imate scheme is developed. Numerical results show that the algorithm is feasible and effective. And the computational complexity of the algorithm is provided.