I am looking at using Interior Point method for optimizing a convex function. The convex function is basically the log-likelihood of a binary logistic regression model. Can I use this technique ?

In generally, is there anything that prevents applying a constrained optimization technique to an unconstrained problem ? From what I think, an unconstrained problem is just a constrained problem without the constraints and thus should be solvable using these techniques.

asked Nov 21 '10 at 18:07

Aman's gravatar image

Aman
2614916


2 Answers:

You are absolutely right about being able to use an optimization toolkit designed for constrained problems in an unconstrained setting, but first you should understand what Interior Point Methods are.

The purpose of "interior point methods" is to provide smoothing to an otherwise unsmooth problem, particularly for the case of constraints. An optimization problem of the form

min_{x}{ f_{0}(x) } : f_{i}(x) <= 0

can be phrased equivalently as

min_{x} { max_{lambda >= 0} { f_{0}(x) + sum_{i}{lambda_{i}*f_{i}(x)} } }

where the function inside the max is the Lagrangian of the problem. This is easy to see as if f_{i}(x) > 0, then lambda_{i} = infinity makes the problem's value go to infinity. Interior point methods approximate this min-max with

min_{x} { f_{0}(x) - (1/t)*sum_{i}{log(-f_{i}(x)} }

where t is a chosen constant such that as t goes to infinity, the original constrained problem is recovered. Interior point methods refers to the concept of using approximations with increasing values of t such that a "good enough" near-optimal solution can be found. In the unconstrained problem, nothing will ever enter the negative sum of logs, so using an interior point method is moot.

What actually happens for each of these minimizations with negative logs for a chosen t is often the Newton Method, which is what I believe you would like to use. If you are not familiar with it, the Newton Method is:

while not converged
    x_{t+1} = x_{t} - alpha_{t} * inv( Hessian(f,x_{t}) ) * gradient(f, x_{t} )

where alpha_{t} is a step size, for example, alpha_{t} = (1/t). Keep in mind that this method requires the inverse of the Hessian of function f to be evaluated at each candidate solution x_{t}, so if you have many variables, this can be very, very expensive. Alternatively, you can use first-order methods such as gradient descent (smooth), subgradient descent (non-smooth), or Nesterov's Optimal Gradient Descent (smooth, but can be applied to unsmooth via "proximal methods") which do not require the computation of the Hessian or its inverse.

Finally, if your problem is fairly small, I would advise you to try out CVX for MATLAB, an interior point / newton method solver for general convex problems. The syntax is simple, and literally all you need to do is supply data and the function you wish to minimize and it will do the rest.

For further reading, I advise you to check out Stanford's ee364a/b lecture slides. I've already linked to a couple, but there's much more to be found. If you would really like to dive into how all the proofs work, the Convex Optimization textbook is top notch and fairly easy to understand once you understand the definition of convex sets/functions. Best of luck!

answered Nov 22 '10 at 02:17

Daniel%20Duckwoth's gravatar image

Daniel Duckwoth
954222938

Your answer is very technical, which is good. I have to spend some time reading up before I can fully appreciate it. Thanks for spending time to elaborate in such detail.

(Nov 22 '10 at 12:58) Aman
1

Sorry if I was too difficult to understand. The gist of it is, you don't want an "Interior Point Method" to solve a problem, but if you're using a software package that uses "Interior Point Methods" it will work just fine because "Interior Point Methods" only mean "approximate constraints." CVX is very easy to use! Use it if you can :3

(Nov 23 '10 at 04:03) Daniel Duckwoth

If you have an l1 constraint on the weight vector then using the interior point method can be a good idea. See this paper A Method for Large-Scale l1-Regularized Logistic Regression.

But I'm not sure if you have a constrained problem in which case you can just take a simple maximum likelihood approach (MLE) for logistic regression. There are in fact a host of optimization methods that you can use for this. See these notes by Tom Minka: Algorithms for maximum-likelihood logistic regression for the unconstrained (i.e., unregularized) case and you want to do MLE, and A comparison of numerical optimizers for logistic regression for the case when you have l2 regularization on the weights and want to do MAP estimation.

answered Nov 21 '10 at 19:25

spinxl39's gravatar image

spinxl39
3698114869

edited Nov 21 '10 at 19:26

Thanks for the pointer.

(Nov 22 '10 at 12:57) Aman
Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.