Non-Convex Problems

Many practical problems of importance are non-convex, and most non-convex problems are hard (if not impossible) to solve exactly in a reasonable time. Indeed, most non-convex problems suffer from the ‘‘curse’’ of local minima, which may trap algorithms into a spurious solution. Hence the idea of using heuristic algorithms, which may or may not produce desired solutions.

In alternate minimization techniques, the optimization is carried out with some variables are held fixed in cyclical fashion; and linearization techniques, in which the objectives and constraints are linearized (or approximated by a convex function). Other techniques include search algorithms (such as genetic algorithms), which rely on simple solution update rules to progress. Another idea is to use approximation algorithms, which typically produce a bound on the problem (and sometimes, a feasible solution that achieves the bound).

An important class of non-convex problems deserves special treatment: Boolean problems, or more generally, problems with discrete (say, integer) variables. We only devote a brief space to these problems.

In contrast to convex problems, for which the landscape is more or less understood, there is no easy classification of non-convex problems; nor is there a short way to summarize the vast range of possibilities and heuristics. In this Chapter we only provide a small sample of solution techniques and of applications.

Outline