Convex optimization
Convex optimization for dummies
In an optimization problem one searches the value of a design variable x that minimizes some objective f(x) and complies with some given constraints. Most optimization problems do not have an analytical solution and hence need to be solved numerically. In this simplifying discussion concerning convex optimization, we divide numerical optimization algorithms in two classes: gradient-based algorithms (i.e., algorithms based on calculating derivatives) and gradient-free algorithms.
The basic working principle of gradient-based algorithms is graphically illustrated in Fig. 1 and can be compared with rain that gathers in one spot or another, depending on the place where it drops (depending on the initial numerical value with which the algorithm is initialized). The three places a, b, and c where the water gathers in Fig. 1(a), are the three local optima of the considered optimization problem, of which b constitutes the global optimum (the ’best’ design). The main problem when numerically solving optimization problems is that the exact number and location of the various local optima are never known beforehand. Hence, the algorithm always finds a solution that depends on the chosen initial guess and that can be very suboptimal (like the point a in Fig 1(a)).
Figure 1 Optimization problem with nonconvex objective f(x) (a) and convex objective (b). In the nonconvex problem, a gradient-based method finds a local optimum in a (initial guesses 1 and 2), in b (initial guesses 3 and 4), or in c (initial guess 5). In the convex problem, the optimum d is found regardless of the initial guess.
In Fig 1(b) one observes an obviously much more beneficial situation: here the rain gathers, independently of the chosen initial guess, in the same spot d that hence automatically constitutes the global optimum. Such a problem, with a unique (and hence global) optimum is a convex optimization problem, while the problem displayed in Fig. 1(a) is nonconvex. Convexity of a problem follows from the mathematical properties of the functions that describe the objective and the constraints and these properties can be verified beforehand.
Not convex, so what?
The standard way of dealing with nonconvex problems is to try many initial guesses for gradient-based methods, or to use gradient-free algorithms such as the popular genetic algorithms. Currently, some successful software products are commercially available to apply such strategies to industrial processes and design problems. While these software products are obviously useful and often yield good designs, the end-user does need to be aware that the final result generally is a local optimum with an unknown degree of suboptimality. Moreover, finding these suboptimal designs might require a substantial amount of computational time, and definitely so if the number of design variables is large.
A radically different way of dealing with nonconvex problems is to convert the optimization problem to such a form that is becomes convex. If that is possible, the designer gets a lot of things for free: the guarantee to find a global optimum, on top of algorithms that solve the problem in a few CPU seconds’ time. Moreover, these algorithms are often freely available on the Internet. This approach emphasizes properly formulating optimization problems, that is, as convex problems, and is the basic idea that underlies mechatronic programming.
Quite often a change of variables is needed to make nonconvex problems convex. This ’trick’ can be compared with a well-known way to analytically solve difficult problems from integral calculus: through an appropriate change of the independent variable, a complicated integral calculus problem might be reduced to a simple problem with a known solution. However, no automatic algorithms exists to find such a change of variables, nor theorems that guarantee that it exists altogether. On the other hand, since the early nineties many such changes of variables have been found in applications ranging from design of large-scale electronic circuits to truss structure design and quantum physics, such that we anticipate that many more applications are still waiting to be found (see this excellent and freely available book on convex optimization and its engineering applications).
If an appropriate change of variables cannot be found, not everything is lost. There do exists techniques that are much more efficient than, for instance, genetic algorithms to find good local optima for nonconvex problems. These techniques cannot guarantee finding the global optimum, but do have in common with convex optimization that the main emphasis lies on properly formulating problems such that they have a specific structure (specific mathematical properties) that can efficiently be exploited by the numerical algorithm. If, for instance, optimization is needed of the dynamic behavior of a system that is described by differential or differential-algebraic equations, so-called optimal control techniques may be highly effective. In chemical process industry, for instance, these techniques have already been highly successful, while applications in mechatronic system design are currently rather scarce.