Chinese Journal of Computers   Full Text
Title	Research Advances on Pattern Searches in Constrained Optimization
Authors	HUANG Tian-Yun
Address	(School of Computer Science and Technology, Southwest University for Nationalities, Chengdu 610041)
Year	2008
Issue	No.7(1200—1215)
Abstract &   Background	Abstract Many complicated optimization models in engineering are mixed-variable constrained, containing high-dimensional continuous, discrete or even categorical variables. The objectives may be non-differentiable and contaminated by random noises, i.e., the problem is non-smooth. No information of the gradient is available or trustworthy. The constraints may be linear or non-linear, discrete sets, or even black-box functions generated from stochastic simulations or codes. Hence, direct searches that need no recourse to explicit derivatives are revived and become popular since the new century. A historical overview of the direct searches is given in this paper. Specially, the unified mathematical description and convergence analysis of pattern searches in recent years are discussed. Pattern searches in constrained optimization are thoroughly analyzed, from bound and linear constrained problems(Generalized Pattern Searches,GPS), to non-linear constrained(GPS Filter) and mixed variables constrained programming(GMVP). The new extension on the poll directions to a dense space in Mesh Adaptive Direct Search(MADS) is also identified. Some existing problems and future directions in this field are pointed out with thoughtful discussions. Keywords constrained optimization; direct search; pattern search; generalized pattern search; GPS filter; generalized mixed variables programming; mesh adaptive direct search Background The modern constrained optimization problems in engineering are becoming more and more complex, most of them are simulation-driven stochastic models, the objectives may be non-smooth, thus no information of the derivatives are available or trustworthy. The constraints may be linear or non-linear, discrete sets, or even black-box functions generated from stochastic simulations or codes. However, many conventional optimization techniques are only applicable to continuous and differentiable convex functions, and they have no use in these cases. The purpose of this work is to reveal another end of the spectrum in the optimization community: Direct searches, especially pattern searches and their evolutions. The direct searches can be traced back to 1950s, from the Evolutionary Operation(EVOP) of Box to the Simplex of Nelder and Mead, from coordinate search of Davidon to the direct search of Hooke and Jeeves. Direct searches, especially pattern searches are always used as the first resort to many non-linear programming(NLP) problems in engineering. Actually, they work very well in practice, but lack of the theoretical fundamentals till 1990s, only as heuristics. The direct searches seem to be revived since the new century, some elaborate theories are constructed and provide rigorous guarantees of convergence for a large number of direct search methods, such as generalized pattern searches(GPS), generalized mixed variables programming(GMVP) and mesh adaptive direct search(MADS), etc. Always, the direct searches remain effective choices, and sometimes the only choice, for several difficult optimization problems. The authors gives a unified mathematical description and convergence analysis of pattern searches in this work, from bound and linear constrained(GPS), to non-linear constrained problems(GPS Filter), from mixed-variable constrained programming(GMVP), to the new extension on the poll directions to a dense space in mesh adaptive direct search(MADS). In the past three years, the author and his students had paid more attentions on optimal video transmission, quality of streaming video and media adaptation over IP and wireless. In order to find the optimal scheduling and transmitting strategies for streaming video such as MPEG-4 finer granularity scalability(FGS), MPEG-4 video objects(VOs), they had proposed some elaborate algorithms. This paper is carried out in order to solve the media adaptation model in the framework of MPEG-21 Digital Items Adaptation(DIA), which was proposed and solved by the authors in related paper. This work is partly supported by the research fund for the State Ethnic Affairs Commission of China(05XN09).