Solving fractional problems with dynamic multistart improving hit-and-run

Fractional programming has numerous applications in economy and engineering. While some fractional problems are easy in the sense that they are equivalent to an ordinary linear program, other problems like maximizing a sum or product of several ratios are known to be hard, as these functions are highly nonconvex and multimodal. In contrast to the standard Branch-and-Bound type algorithms proposed for specific types of fractional problems, we treat general fractional problems with stochastic algorithms developed for multimodal global optimization. Specifically, we propose Improving Hit-and-Run with restarts, based on a theoretical analysis of Multistart Pure Adaptive Search (cf. the dissertation of Khompatraporn (2004)) which prescribes a way to utilize problem specific information to sample until a certain level α of confidence is achieved. For this purpose, we analyze the Lipschitz properties of fractional functions, and then utilize a unified method to solve general fractional problems. The paper ends with a report on numerical experiments. This work was initiated while Mirjam Dür was spending a three-month research visit at the University of Washington. She would like to thank the Fulbright Commission for financial support and the optimization group at UW for their warm hospitality. The work of C. Khompatraporn and Z.B. Zabinsky was partially supported by the NSF grant DMI-0244286.     

On when to stop sampling for the maximum

Suppose a sequential sample is taken from an unknown discrete probability distribution on an unknown range of integers, in an effort to sample its maximum. A crucial issue is an appropriate stopping rude determining when to terminate the sampling process. We approach this problem from a Bayesian perspective, and derive stopping rules that minimize loss functions which assign a loss to the sample size and to the deviation between the maximum in the sample and the true (unknown) maximum. We will show that our rules offer an extremely simple approximate solution to the well-known problem to terminate the Multistart method for continuous global optimization.     

A Population-based Approach for Hard Global Optimization Problems based on Dissimilarity Measures

When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be adopted like, e.g.: