Application of isoperimetry and measure concentration to analysis of heuristics

Abstract

Optimization is selection of (some of the) best among many alternatives newlinecompared using some utility or preference objectives. Optimization newlinecomputation is the process of searching for possible choices, trade-offs, and newlinerelaxation procedures guided by various total, partial or quasi orders induced newlineby the objectives that represent the utility or preference between newlinedifferent solutions. Multiobjective optimization is arguably the most general newlineform of optimization, and the hardest for computation. Except for newlinetrivial problems, there will be a set of solutions to a multiobjective optimization newlineproblem. Myriad possible complex structures of the solution sets newlinein the general case render complete algorithmic solutions nearly impossible. newlineClassical mathematical programming seeks to solve such optimization newlineproblems using calculus and iterations. However, various structural properties newlinesuch as convexity, which is a geometric property, need to be satisfied newlineby the objective functions in order to be amenable to such classical solutions. newlineEven when such properties are satisfied by the objectives, there is newlineno way to choose initial conditions for ensuring convergence of classical newlinemethods, and even when they do converge, they give a one-point solution newlineat a time. All this makes classical methods unsuitable for complicated multiobjective newlineoptimization problems in which the objective functions may be newlineonly piecewise differentiable, and when many competing solutions at once newlineare sought from one algorithmic run to express the actual trade-off options newlineat the disposal of the planner-designer. Heuristics such as evolutionary algorithms newlinedo not demand any special nice behaviour of objectives and offer newlinemany competing solutions in one run. In the last 4 decades practitioners newlinehave proposed and fruitfully used such heuristics for countless optimization newlineproblems. Heuristics are also found to be robust in practice, in that newlinethey can be easily adapted to retrofit a new kind of optimization problems newlineeven when not designed for the latter. This has resulted in th