HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
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^2 + y^2. 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)
.
A linear function is a special class of convex functions, because the relationship is strictly equal i.e.
f(\lambda x + (1-\lambda)y) = \lambda f(x) + (1-\lambda)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^3 + bx^2 + cx +d is a convex function.
A semidefinite convex optimization problem is given as:
maximize/minimize f(x) subject to g(x) = 0, h(x) \le 0
A surprisingly large number of problems can be cast as semi-definite programing problems. For example:
a. Minimize the quadratic function (ax + b)^2 - cx - d, subject to the quadratic constraints (a_i x + b_i )^2 - c_i x - d_i \le 0 can be written as:
Minimize t such that
\begin{eqnarray}
\left[\begin{array}{cc} 1 & ax+b \\ ax+b & cx+d+t \end{array}\right] \ge 0 \\
\left[\begin{array}{cc} 1 & ax_i+b \\ ax_i+b & cx_i+d \end{array}\right]
\end{eqnarray}
Note that any quadratic in x can be written in the form (ax + b)^2 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_1 + yA_2 . 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 minimize t, subject to tI - A(x) \ge 0, where I is the identity matrix.
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,\lambda) = f(x,y,z) + \lambda(g(x,y,z) - c) and then solve the set of equations \nabla k_{x,y,z,\lambda} = 0
i.e.
\begin{array}{c}
\frac{\partial f(x,y)}{\partial x} + \lambda \frac{\partial f(x,y)}{\partial x} = 0 \\
\frac{\partial f(x,y)}{\partial y} + \lambda \frac{\partial f(x,y)}{\partial y} = 0 \\
g(x) = c
\end{array}
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^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.
Comments
