5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

As far as I'm concerned, constrained optimization is a less-than-optimal way of avoiding strong fluctuations in your parameters for the independents due to a bad model-specification. Pretty often a constraint is "needed" when the variance-covariance matrix is ill-structured, when there is a lot of (unaccounted) correlation between independents, when you have aliasing or near-aliasing in datasets, when you gave the model too many degrees of freedom, and so on. Basically, every condition that inflates the variance on the parameter estimates will cause an unconstrained method to behave poorly.

You can look at constrained optimization, but I reckon you should first take a look at your model if you believe constrained optimization is necessary. This for two reasons :

  • There's no way you can still rely on the inference, even on the estimated variances for your parameters
  • You have no control over the amount of bias you introduce.

So depending on the goal of the analysis, constrained optimization can be a sub-optimal solution (purely estimating the parameters) or inappropriate (when inference is needed).

On a side note, penalized methods (in this case penalized likelihoods) are specifically designed for these cases, and introduce the bias in a controlled manner where it is accounted for (mostly). Using these, there is no need to go into constrained methods, as the classic optimization algorithms will do a pretty good job. And with the correct penalization, inference is still valid in many cases. So I'd rather go for such a method instead of putting arbitrary constraints that are not backed up with an inferential framework.

My 2 cents, YMMV.

$\endgroup$
  • 3
    $\begingroup$ +1 for good advice. But it's unclear whether the implicit assumptions in your reply match the question: it sounds like the OP is not actually adding any constraints, but only is asking whether methods of constrained optimization could be used to solve the unconstrained problem. (Of course my interpretation could be wrong, too...) $\endgroup$ – whuber Nov 22 '10 at 15:02
  • 2
    $\begingroup$ @whuber: It's a bit difficult. He refers to the Interior point method, which is a constrained optimization in the sense that it constrains the search space. But penalty methods are also considered constrained methods, and actually one can say that a binary logistic regression is constrained as well, in the sense that it is built upon a set of assumptions. So I find the question of OP a bit confusing. $\endgroup$ – Joris Meys Nov 22 '10 at 16:51
  • $\begingroup$ Thank you: that perspective helps me appreciate your answer even more. $\endgroup$ – whuber Nov 22 '10 at 17:00
  • $\begingroup$ I am not an expert in constrained methods, but from what I have read till now, the constraints in constrained optimization problems are hard inequalities defined by Ax < b, where A is a matrix and b is a vector. Penalized log likelihood (I understand you mean, regularization) does not cut the space, it just modifies the contours of the objective function. The objective function is still defined for all values, even Infinity. But the hard constraints that generally are part of constrained problems will not allow all points in the space to be a valid solution. $\endgroup$ – euphoria83 Nov 22 '10 at 17:56
  • $\begingroup$ @euphoria83 That's how I understood it as well, which is why I con't consider penalized methods constrained methods. But they tend to end up under the constrained methods in some textbooks, together with Lagrange multipliers and the likes. $\endgroup$ – Joris Meys Nov 22 '10 at 18:25
3
$\begingroup$

The general sense in optimization is that if you have a convex function and no constraints, you want to use the "powerful stuff", gradient descent, Newton, etc. Without constraints interior point methods are not very good (competitive).

In particular for the problem you're studying (binary logistic regression) you should consider trying simple stochastic gradient descent.

Nothing really stops you from applying constrained optimization techniques to unconstrained problems. The same way nothing stops from pushing (instead of riding) your car to work. But you should definitely try interior point methods w/o constraints and convince yourself about it.

Finally you mention that you want to try linear programming-based methods presumably without constraints, what you plan to do in this case I don't quite understand.

$\endgroup$
  • 1
    $\begingroup$ Interior point can be applied to nonlinear problems as well. (wikipedia). This is not an exercise to find the best solution. It is more of an exercise in exploration. May be if I knew as much as you do, I won't even try it. But I don't. And this is how I will. :) $\endgroup$ – euphoria83 Nov 22 '10 at 7:50
  • $\begingroup$ @euphoria83, sorry I didn't mean to be obnoxious or anything. I've edited my answer. $\endgroup$ – carlosdc Nov 22 '10 at 8:54
2
$\begingroup$

As far as I know, there is no reason to stop you from applying constrained optimization to an unconstrainted problem. However, this may not be a great idea in terms of computational complexity and convergence. For example, fitting a logistic regression model can done efficiently with the Newton-Raphson approach (or the Fisher scoring variant). I am not sure if there is much to gain with the interior point approach in this particular case.

$\endgroup$
  • $\begingroup$ I know the various methods (gradient based) that can be applied. I am working on comparing various optimization methods for this model for a comprehensive theoretical evaluation. Therefore, I want to try LP-based methods as well. $\endgroup$ – euphoria83 Nov 22 '10 at 3:43
  • $\begingroup$ Sounds interesting. In regards to Fisher scoring, you may want to check out "Meenakshi Devidas and E. Olusegun George, Monotonic Algorithms for Maximum Likelihood Estimation in Generalized Linear Models. Sankhy\-{a}: The Indian Journal of Statistics (Series B), Vol. 61, 382--396, 1999." $\endgroup$ – emakalic Nov 22 '10 at 5:21
  • $\begingroup$ @euphoria83: by 'LP based methods' do you just mean interior points or also the 'regular' simplex? $\endgroup$ – user603 Nov 22 '10 at 10:09
  • $\begingroup$ @user one of those. mostly interior point. $\endgroup$ – euphoria83 Nov 22 '10 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.