Return to search
## A class of Increasing Positively Homogeneous functions for which global optimization problem is NP-hard

It is well known that global optimization problems are, generally speaking, computationally infeasible, that is solving them would require an unreasonably large amount of time and/or space. In certain cases, for example, when objective functions and constraints are convex, it is possible to construct a feasible algorithm for solving global optimization problem successfully. Convexity, however, is not a phenomenon to be often expected in the applications. Nonconvex problems frequently arise in many industrial and scienti¯c areas. Therefore, it is only natural to try to replace convexity with some other structure at least for some classes of nonconvex optimization problems to render the global optimization problem feasible. A theory of abstract convexity has been developed as a result of the above considerations. Monotonic analysis, a branch of abstract convex analysis, is analogous in many ways to convex analysis, and sometimes is even simpler. It turned out that many problems of nonconvex optimization encountered in applications can be described in terms of monotonic functions. The analogies with convex analysis were considered to aid in solving some classes of nonconvex optimization problems. In this thesis we will focus on one of the elements of monotonic analysis - Increasing Positively Homogeneous functions of degree one or in short IPH functions. The aim of present research is to show that finding the solution and ²-approximation to the solution of the global optimization problem for IPH functions restricted to a unit simplex is an NP-hard problem. These results can be further extended to positively homogeneous functions of degree ´, ´ > 0. / Master of Mathematical Sciences (Research)

Identifer | oai:union.ndltd.org:ADTP/266028 |

Date | January 2009 |

Creators | Sultanova, Nargiz |

Publisher | University of Ballarat |

Source Sets | Australiasian Digital Theses Program |

Detected Language | English |

Rights | Copyright Nargiz Sultanova |

Page generated in 0.0074 seconds