Convex Optimization

Convex optimization problems are problems of the kind - 
min f(x)
subject to g_i(x) ≤ b ∀ i=1...n
           h_i(x) = 0 ∀ i=1...m
where the both the objective function and the inequality constraints are convex and the equality constraints are affine. A simple definition of a convex function is that if we consider two points on the function the line segment is contained in the function. An alternate definition is that a tangent at any point on the function always lies below the function. In simple words, a convex function is a function with positive curvature as shown in the figure below.

Some example convex functions are as follows:
  1. An affine function. (Actually it is both convex and concave)
  2. Power of x, x^α α ≥ 1 or α ≤ 0 (Note that if α is between 0-1 the function is concave)
  3. Exponential (Logarithm is concave)
  4. Norms
How to systematically determine if a function is convex ?
  1. Jensen's inequality: A function f is convex if 
    f(θx + (1 - θ)y) ≤ θf(x) + (1 - θ)f(y)  for 0 ≤ θ ≤ 1
  2. If we consider any two points x & y on the function, then the Bregman divergence is a positive quantity if the function is convex and x is the optimal point. (Note that the Bregman divergence computes the difference between the first order taylor approximation of f at x as a function of y) 
    D(x,y) = f(y) - (f(x) + ∇f(x)(y-x)) ≥ 0
  3. A function is convex if and only if it is 2nd differentiable then the Hessian (2nd derivative) is positive semi-definite.
  4. If the function is composed of simple convex functions with operations that preserve convexity.
The advantage of convex formulation is that there is a global optimal solution available. Lets talk about how to solve these problems. Let us first consider problems of the kind: 
min f(x)
subject to g_i(x) ≤ b ∀ i=1...n
           h_i(x) = 0 ∀ i=1...m
The Lagrangian of this standard form of problems which are not necessarily convex is defined by 
L(x, λ, ν) = f(x) + ∑λ_i(g_i(x) -b) + ∑ν_i(h_i(x))
where λ_i and ν_i are called as the Lagrangian multipliers. Now, the dual function of the Lagrangian is defined as the infimum over x of the Lagrangian function and is defined as follows. 
d(λ, ν) = inf x ∈ D L(x, λ, ν)
The dual function of the Lagrangian is necessarily a concave function. In order to prove this, let us first understand that the dual is affine in λ and ν. The infimum of a set of affine functions is a concave function and hence the dual is a concave function. Next, we claim that the optimal value of the dual function is a lower bound on the optimal value of the original function f if λ_i ≥ 0. This can be proved trivially as the term g_i(x) - b ≤ 0 and h_i(x) = 0 and hence the last term does not matter.
Useful Links:
  1. Stephen Boyd's lectures on Convex Optimization are really awesome.
  2. His entire book is available online.
  3. CVX matlab toolbox for convex programming. This makes writing programs for convex optimization very easy.

Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya...
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all...
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although w...
Read more