Convex Optimization - Convex Optimization

Wikimization Meboo Video News Contact See

Convex Optimization

"Prior to 1984 [nascence of interior-point methods of solution] linear and nonlinear programming, one a subset of the other, had evolved for the most part along unconnected paths, without even a common terminology. The use of programming to mean optimization serves as a persistent reminder of these differences."

Given some application of convex analysis, it may at first seem puzzling why the search for its solution ends abruptly with a formalized statement of the problem itself as a constrained optimization. The explanation is: typically we do not seek analytical solution because there are relatively few. If a problem can be expressed in convex form, rather, then there exist computer programs providing efficient numerical global solution.

The goal, then, becomes conversion of a given problem (perhaps a nonconvex problem statement) to an equivalent convex form or to an alternation of convex subproblems convergent to a solution of the original problem: A fundamental property of convex optimization problems is that any locally optimal point is also globally optimal. Given convex real objective function g and convex feasible set C
(a subset of dom g), which is the set of all variable values satisfying the problem constraints, we have the generic convex optimization problem

minimize g(X)
subject to X in C

where constraints are abstract here in the membership of variable X to feasible set C. Inequality constraint functions of a convex optimization problem are convex while equality constraint functions are conventionally affine, but not necessarily so. Affine equality constraint functions (necessarily convex), as opposed to the larger set of all convex equality constraint functions having convex level sets, make convex optimization tractable.

Similarly, the problem

maximize g(X)
subject to X in C

is convex were g a real concave function. As conversion to convex form is not always possible, there is much ongoing research to determine which problem classes have convex expression or relaxation.