3
$\begingroup$

In the realm of statistical modelling, creating a statistical model with respect to some data involves optimizing some mathematical function (e.g. Loss Function, OLS Equation, Maximum Likelihood Equation, etc. ) : Determining the final beta regression coefficients involves solving an optimization equation.

From what I see:

  • Sometimes, the equation to be optimized has a "closed form solution". For example, estimating the coefficients for a Linear Regression model involves optimizing an OLS or an MLE equation - but this optimization equation has a "closed form solution". This means that we can directly estimate the regression coefficients and do not require an iterative optimization algorithm. I have noticed that many of these instances where the optimization problem has a "closed form solution", the equation (i.e. the mathematical function being optimized) is usually "Convex".

  • However, in most cases these optimization equations do not have "closed form solutions" (e.g. Neural Networks, Logistic Regression, etc.). In these cases, an iterative optimization algorithm (e.g. Gradient Descent) has to be used to estimate the model parameters (e.g. weights of a Neural Network). I have also noticed that when this is the case, the optimization equation (i.e. the mathematical function being optimized) is usually "Non-Convex".

I understand that optimizing some Convex Functions have "closed form solutions" while other Convex Functions do not have "closed form solutions".

But:

  • Can a mathematical problem that is Non-Convex (i.e. a Non-Convex Function) ever have a "closed form solution"? Or is this never the case?

Thank you!

$\endgroup$
1
  • 2
    $\begingroup$ Even convex optimization problems typically don’t have closed form solutions. $\endgroup$
    – littleO
    Mar 25, 2022 at 6:12

1 Answer 1

5
$\begingroup$

Certainly, nonconvex optimization problems can have a closed-form solution, but, in general, they do not. Nonconvex optimization is, in general, NP-hard. This means, loosely speaking, that the time it takes to find a global minimum grows exponentially with the problem size. This exponential growth can often render finding a global minimum an infeasible goal (sometimes could take years on supercomputers), so we often settle for finding a local minimum. Problem size in this context could mean the number of dimensions of the domain of the function, how many grid points you have in a numerical approximation to the function, etc.

A simple example of a nonconvex optimization problem with a closed-form solution is

\begin{align} \min_{ x \in [0,2\pi] } \cos(x). \end{align}

$\cos(x)$ is nonconvex, but clearly the answer to this particular nonconvex problem is $\cos(\pi)=-1$ at $x=\pi$. But note that this is a somewhat contrived example; whenever you see "nonconvex optimization," you should think "that's probably a hard problem unless there is some special structure to the particular problem that I'm looking at."

$\endgroup$
5
  • $\begingroup$ While NP-hard problems are difficult to solve, it is not necessarily true that it takes billions of years to solve them. The complexity of algorithm (which is actually not understood very well by most people) is essentially an asymptotic asymptotic. NP-hard problems of small size can still be solved. Even algorithms/problems with linear complexity can become unsolvable at some point and worst-case exponential algorithms may still perform well in practice. $\endgroup$
    – KBS
    Mar 25, 2022 at 11:15
  • $\begingroup$ Yes...I just didn't want to get into the weeds of the definition of NP-hardness in case the OP isn't familiar with it, and if OP is familiar with, they'd know that my statement in parentheses is pretty far from what NP-hard really means. I'll edit it to avoid this inaccuracy but still try to not go into weeds. Let me know if you think this could be improved further. $\endgroup$ Mar 25, 2022 at 14:59
  • $\begingroup$ You can just say that the time to solve certain problems may be prohibitive. $\endgroup$
    – KBS
    Mar 25, 2022 at 15:09
  • $\begingroup$ TylerMasthay :Great answer! You have clearly demonstrated a single counterexample in which a Non Convex Function has a "Closed Form Solution"! I guess this settles it! $\endgroup$
    – stats_noob
    Mar 25, 2022 at 15:32
  • $\begingroup$ It's nice to see the optimization growing here in this site. Well discussed problems is a hard to see thing. $\endgroup$ Mar 27, 2022 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .