Optimization

Optimization refers to the task of selecting the appropriate point in the domain of a function, where the value of that function is minimized or maximized. Consider a function of the form f(x,y) = x² + y². This function has a minimum value of zero, at *(x,y) = (0,0)*. Optimization refers to the identification of the minima point *(x,y)=(0,0)*, by examining the structure of the function f(x,y), which is known as the objective function.

Optimization problems in general can be constrained or unconstrained. In constrained optimization problems, the optimal point is subject to restrictions, which are referred to as constraints. The general form of a constrained optimization problem is: Maximize/minimize f(x,y), subject to some restrictions on (x,y) . We shall review the forms which an optimization problem take gradually.

Convex optimization

A convex function is a function defined on a convex set such that for any two points x,y in the set f(λx + (1-λ)y) <= λf(x) + (1-λ)f(y). In other words, any weighted mean of the function at any two points is always higher than value of the function in the weighted mean. This is shown in the image below, for the convex function f(x) = x².
.
A linear function is a special class of convex functions, because the relationship is strictly equal i.e.f(λx + (1-λ)y) = λf(x) + (1-λ)f(y) if f() is linear. Any function of the type x^p, p >= 1 is a convex function. Likewise any polynomial in x i.e. f(x) = ax³ + bx² + cx +d is a convex function.

A convex optimization problem is given as:
maximize/minimize f(x) subject to g(x) = 0, h(x) <= 0, where all functions f(), g() and h() are convex functions. The function to be optimized is called the objective function and the restrictions in the form of g() and h() are called constraint functions. The constraint functions create a feasible set within which we have to search for the optimal point, as shown here

A large variety of optimization problems can be suitably converted to a convex optimization problem, for example, the least squares problem which is at the heart of regression based statistical analysis. Industrial applications routinely solve convex optimization problems involving thousands of dimensions and hundreds of variables, using numerical optimization solvers.

Linear programing

Linear programing is a sub-set of convex programming, where both the constraint functions and the objective functions are of the form ax+b, a,b being constants. While linear programs technically meet the criterion of being convex, it is in many senses, a special subset with its own specialized techniques. Linear programs are widely used in the fields of operation research, logistics, etc.

Semi-definite Programing

Semi-definite programing refers to a class of convex optimization problems where the objective function is linear and the constraint function can be written in terms of a semi-definite matrix, i.e. a matrix whose eigenvalues are non-zero.

A surprisingly large number of problems can be cast as semi-definite programing problems. For example:
a. Minimize the quadratic function (ax + b)² - cx - d, subject to the quadratic constraints (a₀x + b₀)² - c₀x - d₀ <= 0, (a₁x + b₁)² - c₁x - d₁ <= 0 . This problem can be re-written as:

Minimize t .

Note that any quadratic in x can be written in the form (ax + b)²x - cx - d, so this conversion is appropriate for a vast class of problems. This category of problem is called a Quadratically Constrained Quadratic Programming problem (QCQP). While standard SDPs do work for QCQPs, there are also specialized techniques available.

b. Minimize the maximum eigen-value of a symmetric matrix. Consider a matrix A(x,y) = A + xA₁ + yA₂. We have to find x,y so as to minimize the maximum eigen-value of A(x,y). This problem occurs frequently in control theory and can be expressed as

BoydSDP contains numerous examples of application of SDPs, including problems of non-convex optimization and even NP-hard combinatorial problems. SDPs are solved using Interior_Point_Methods.

Techniques of convex optimization - Lagrangian method

Consider the problem of optimizing f(x,y,z), subject to the constraint g(x,y,z) = c
The standard technique for solving convex optimization problem given above is to construct a Lagrangian of the form k(x,y,z,λ) = f(x,y,z) + λ(g(x,y,z) - c) and then solve the set of equations ∇k_x,y,z,λ = 0
i.e.
The value of x* which satisfies the Lagrangian is the optimal solution. The Lagrangian technique is sometimes misunderstood as a clever mathematical trick; in reality, the values of the Lagrangian multiplier &lambda has deep physical significance, as it captures the relative 'tightness/slackness' of the associated constraint. See [Simon and Blume] for more details.

A variation of the Lagrangian technique is the Kuhn Tucker formulation, which takes into account constraints with inequalities as well. See [Simon and Blume] among others for more details.

Simplex

The simplex algorithm is a technique for solving linear programing problems. Invented in the 1930s by the mathematician Dantzig, the simplex algorithm is one of the most used applications currently.

The simplex program works as follows: if we construct the 'feasible set' of a linear optimization problem by taking the intersections of all constraints, the maximum value has to arrive at one of the vertices (this can be easily proved as in Simon and Blume). However, given 'n' constraints, the number of vertices is O(nⁿ), so a brute force search of all constraints is impossible. The simplex algorithm provides a technique for starting at one vertex and finding the 'most likely' neighbouring vertex which will give a more optimal value. While in the worst case you can end up searching every possible vertex, typically simplex algorithms give much better search performance.

In the figure below, we show the constraint set as an interior of the polytope (in blue) and the search path in red.

Interior point methods

Interior_Point_Methods are an alternate method of solving convex optimization problems. Instead of searching the boundary of the feasible set, these techniques start with an interior point and gradually converge to the boundary. The attraction of these methods is that a) all points are feasible and each point gives a better solution than the previous b) there are well studied theoretical proofs about the rate of convergence and c) the algorithm has been proven to work in polynomial time. A final advantage is that interior point methods work well both with linear and non-linear problems of convex optimization. See Interior_Point_Methods for more details.

 Create your own educational wiki!Help Add to Del.ici.ous Add to Digg Add to Reddit Add to fUrl Add to Spurl Privacy Policy RSS