On the reduced-set pareto-lipschitzian optimization

Jonas Mockus, Remigijus Paulavičius


A well-known example of global optimization that provides solutions within fixed error limits is optimization of functions with a known Lipschitz constant. In many real-life problems this constant is unknown.

To address that a method called Pareto-Lipschitzian Optimization (PLO) was described that provides solutions within fixed error limits for functions with unknown Lipschitz constants. In this approach, a set of all unknown Lipschitz constants is regarded as multiple criteria using the concept of Pareto Optimality (PO).

In this paper, a new version of the Pareto-Lipschitzian Optimization method (PLOR) is proposed where a set of unknown Lipschitzian constants is reduced just to the minimal and maximal ones. In the both methods, partition patterns are similar to those of DIRECT. The difference is in the rules of sequential partitions defining non-dominated sets. In PLO, it includes all Pareto-Optimal sets defined by all Lipschitz constants. In PLOR, it considers just two elements corresponding to the maximal and minimal Lipschitz constant. in DIRECT, it selects a part of the Pareto-Optimal set which is determined by some heuristic parameter .


Evtushenko, Y. G. (1985). Numerical optimization techniques. New York: Optimization software, Inc.

Figueira, J., Greco, S., & Ehrgott, M. (2004). Multiple Criteria Decision Analysis:State of the Art Surveys. Berlin: Springer.

Finkel, D., & Kelley, C. (2006). Additive Scaling and the DIRECT Algorithm. Journal of Global Optimization , 36, 597-608.

Gablonsky, J., & Kelley, C. (2001). A Locally-Biased form of the DIRECT Algorithm. Journal of Global Optimization , 21, 27-37.

Hedar, A. (2005). Hedar, A. Retrieved from http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm

Jones, D., Perttunen, C., & Stuckman, B. (1993). Lipschitzian Optimization Without the Lipschitz Constant. Journal of Optimization Theory and Application, , 79, 157-181.

Ko, K.-I. (1991). Complexity Theory of Real Functions. Boston: Birkhauser.

Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Boston: Kluwer Academic Publishers.

Mockus., J. (2011). On the Pareto-Lipschitzian Optimization. Informatica , 22, 521–536.

Pardalos, P., & Siskos, Y. (1995). A Historical Perspective. In Advances in Multi-criteria Analysis. Kluwer Academic Publishers.

Paulavičius, R., & Žilinskas, J. (2007). Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case. Information Technology and Control , 36 (4), 383-387.

Paulavičius, R., Žilinskas, J., & Grothey, A. (2010). Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. Optimization Letters , 4 (2), 173-183.

Pijavskij, S. A. (1972). An Algorithm for finding the absolute extremum of function. Computational Mathematics and Mathematical Physics , 57-67.

Sergeyev, Y., & Kvasov, D. (2006). Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM Journal on Optimization , 16 (3), 910-937.

Shubert, G. (1972). A sequential method seeking the global maximum of function. SIAM Journal on Numerical Analysis , 9, 379-388.

Sukharev, A. (1971). On optimal strategies of search of extremum. Computational Mathematics and Mathematical Physics , 910-924.

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

eISSN: 2029-9966