11
$\begingroup$

So I am new to OR (not my field, but I have found myself working in it for a thesis project). My problem is a non-linear problem by design and unfortunately I cannot linearize everything, however, there are parts of my problem that I can linearize such as the product of two continuous variables.

What I am not certain about is how linearization helps in the context of a non-linear problem. For example, if I were to linearize the product of the two continuous variables, would the linearization get the solution closer to a global optimum if it exists or would the problem just compute faster such that the problem can be made larger in scale.

What exactly are the benefits of performing linearization in math programming, and in particular, to NLPs?

$\endgroup$
3
$\begingroup$

What I am not certain about is how linearization helps in the context of a non-linear problem. ... would the linearization get the solution closer to a global optimum if it exists or would the problem just compute faster such that the problem can be made larger in scale.

If a portion of the equation has a linear section this can be partitioned from the non-linear sections and solved using simpler equations, this will be faster; especially if the area is large or is involved in a complex analysis or optimization.

If the partitioned section can only be approximated using linear equations this will still be faster, but with a loss of accuracy.

It is possible to approximate, optimize, and for a final pass use exact equations. In a complex system this can result in a huge speedup without loss of accuracy, but possibly at the cost of missing the most optimal solution due to missing the true global optimum and relying on the approximations of local optimums to hopefully arrive at a global optimum. That is called the Hartman–Grobman theorem.

Where a small smooth change made to the parameter values (the bifurcation parameters) of a system causes a sudden 'qualitative' or topological change in its behavior that is called bifurcation theory or a crisis.

The Wikipedia explanation of a non-linear system is:

"Typically, the behavior of a nonlinear system is described in mathematics by a nonlinear system of equations, which is a set of simultaneous equations in which the unknowns (or the unknown functions in the case of differential equations) appear as variables of a polynomial of degree higher than one or in the argument of a function which is not a polynomial of degree one. In other words, in a nonlinear system of equations, the equation(s) to be solved cannot be written as a linear combination of the unknown variables or functions that appear in them. Systems can be defined as nonlinear, regardless of whether known linear functions appear in the equations. In particular, a differential equation is linear if it is linear in terms of the unknown function and its derivatives, even if nonlinear in terms of the other variables appearing in it.

Linearization of a non-linear equation allows the use of linear equations to estimate a point of a non-linear function, the further from that point the greater the likelihood of error. An iteration of linear approximations applied to a non-linear functions necessitates choosing a step size, too small a step size will be slow but more accurate while larger steps will be faster but may lead to instabilities.

For example a well-posed ordinary differential equation can be processed using a finite difference method and solved using matrix differential equations. A matrix of small simple equations is easier, and faster, to solve than a matrix of polynomials.

For much easier to follow examples see:

  • "What Is the Difference between Linear and Nonlinear Equations in Regression Analysis?"

    Compare a linear versus a nonlinear regression model of the relationship between density and electron mobility. The nonlinear equation is so long it that it doesn't fit on the graph:

    $$\Tiny{\begin{align} \text{Linear equation (left side)} & \qquad \qquad \qquad \qquad \\ \text{Mobility } = & \text{ } 1243 + 412.3 \times \text{Density Ln} - 94.29 \times \text{Density Ln}^2 - 32.90 \times \text{Density Ln}^3 \qquad \quad \\ & \\ \text{Non-linear equation (right side)} & \\ \text{Mobility } = & (1288.14 + 1491.08 \times \text{Density Ln} + 583.238 \times \text{Density Ln}^2 + 75.4167 \times \text{Density Ln}^3) / (1 + 0.966295 \times \text{Density Ln} + 0.397973 \times \text{Density Ln}^2 + 0.0497273 \times \text{Density Ln}^3) \quad \\ \end{align}}$$

Linear versus Non-linear

On the left:

"The fitted line plot shows that the raw data follow a nice tight function and the R-squared is 98.5%, which looks pretty good. However, look closer and the regression line systematically over and under-predicts the data at different points in the curve. When you check the residuals plots (which you always do, right?), you see patterns in the Residuals versus Fits plot, rather than the randomness that you want to see. This indicates a bad fit, but it’s the best that linear regression can do.".

On the right:

"The fitted line plot shows that the regression line follows the data almost exactly -- there are no systematic deviations. It’s impossible to calculate R-squared for nonlinear regression, but the S value (roughly speaking, the average absolute distance from the data points to the regression line) improves from 72.4 (linear) to just 13.7 for nonlinear regression. You want a lower S value because it means the data points are closer to the fit line. What's more, the Residual versus Fits plot shows the randomness that you want to see. It’s a good fit!".

Beginner level references:

"Linear or Nonlinear Regression? That Is the Question."

"How to Predict with Minitab: Using BMI to Predict the Body Fat Percentage, Part 1"

"How to Predict with Minitab: Using BMI to Predict the Body Fat Percentage, Part 2"

"What Is the Difference between Linear and Nonlinear Equations in Regression Analysis?"

$\endgroup$
6
$\begingroup$

In Operations Research, we have very good algorithms for solving certain classes of well-structured convex optimization problems. Our specialty is the class of linear programs, which is discussed by Oguz Toragay. Other classes are listed by ErlingMOSEK in this answer. These optimization problems can be solved efficiently in practice.

Operations Research also provides good algorithms for optimization problems in which some or all of the variables are integer, but would otherwise be well-structured and convex. This includes mixed-integer programs, which are linear programs that include integer variables. These problems are more difficult to solve.

So given that we are very good at solving linear programs and mixed-integer programs, it makes sense to attempt to linearize non-linear problems to make them fit in this framework. This allows us to solve these problems with the existing machinery.

If the non-linear problem is not convex, it is probably not possible to find an equivalent linear program. However, we might be able to obtain an equivalent mixed-integer problem. On this site, there are plenty of questions about linearization in which the answers introduce binary variables to model the non-linearity.

In the above, I have assumed that you are interested in finding an equivalent representation of your non-linear program. Linearization then allows you to get the same global optimum, but faster. If you approximate non-linear functions by (piece-wise) linear ones, global optimality is no longer guaranteed.

$\endgroup$
  • $\begingroup$ My NLP is non-convex by nature. I am modelling biological constraints which creates a trade-off between realism and tractability. What I was getting at a bit earlier though is this: Suppose my model has 3 constraints, one which cannot be linearized while the other two can. Is there any benefit associated with linearizing the two constraints even though my other constraint must remain non-linear? $\endgroup$ – GrayLiterature Oct 23 '19 at 4:27
  • $\begingroup$ If all 3 constraints could be linearized then the problem could be transformed into an MIP. But if only 2/3 constraints are linearized, the problem would still be NLP but would be "closer" to an MIP than if we had not chosen to linearize them. $\endgroup$ – GrayLiterature Oct 23 '19 at 4:28
  • $\begingroup$ That completely depends on how you want to solve the problem. If you want to make an approximate MIP, for example, it makes sense to first linearize what you can, and only approximate the remaining non-linear parts. If you are using a non-linear solvers it depends, and the easiest way to test is by trying. $\endgroup$ – Kevin Dalmeijer Oct 23 '19 at 12:57
  • $\begingroup$ @KevinDalmeijer could you provide a concrete simple example/graph that illustrates this statement "Linearization allows you to get the same global optimum, but faster. But when approximating non-linear functions by (piece-wise) linear ones, global optimality is no longer guaranteed." $\endgroup$ – Amira Zarglayoun Nov 6 '19 at 3:41
  • $\begingroup$ @AmiraZarglayoun Say that I have a constraint $ z \ge \max\{x,y\}$. This is a non-linear constraint which I could feed to a non-linear solver. However, I could equivalently write $z\ge x$ and $z\ge y$. These are linear constraints, which means I can now use my fast linear programming solver. $\endgroup$ – Kevin Dalmeijer Nov 7 '19 at 15:49
3
$\begingroup$

Definition(from Wikipedia): In a mathematical programming model, if the objective functions and constraints are represented entirely by linear equations, then the model is regarded as a linear model. If one or more of the objective functions or constraints are represented with a nonlinear equation, then the model is known as a nonlinear model. In optimization, cost functions and non-linear components within can be linearized in order to apply a linear solving method such as the Simplex algorithm. The optimized result is reached much more efficiently and is deterministic as a global optimum.

Note that: I googled but couldn't find any paper in which the authors compare the performance of linear vs. non-linear models for a specific problem. Without loss of generality, this can be inferred that:

  1. The two modeling approaches (for the same problem) are not comparable because different algorithms with totally different complexity have been used in modeling and in the solving process.
  2. In all possible situations(if you have the opportunity to model the problem as an LP), some linearization techniques have been used to avoid nonlinearity in the model and convert the NLP to an LP model.
$\endgroup$
  • $\begingroup$ So if you can fully convert the NLP to an LP then you can use a different algorithm and reach a deterministic global optimum more efficiently. So would it also be true that if you can only linearize a portion of the problem that you would also be getting a step closer to solving for a global optimum? $\endgroup$ – GrayLiterature Oct 22 '19 at 22:25
  • $\begingroup$ @D.Gray, first part of your statement is correct but generally, it can not be proven that partially linearization has effects on the solving process, neither on the solving time nor on the characteristics of the obtained solution. $\endgroup$ – Oguz Toragay Oct 22 '19 at 22:29
  • 1
    $\begingroup$ @OguzToragay I agree that linear is typically easier to solve than non-linear, but this is not always the case. Interior point methods for LP, for example, introduce a non-linear barrier function, but can still outperform simplex. $\endgroup$ – Kevin Dalmeijer Oct 23 '19 at 3:43
  • 1
    $\begingroup$ @KevinDalmeijer thanks Kevin to point out that important aspect of solving methods to be used for both LPs and NLPs. Although it highly depends on the problem but as you mentioned some general behavior can be expected from the solution methods. $\endgroup$ – Oguz Toragay Oct 23 '19 at 4:22
0
$\begingroup$

This is a complicated question with a complicated answer. Linearisations are a powerful tool when used correctly, but can also have massive drawbacks.

Others have covered a lot of the theoretical implications, so I will share what I have seen in applied problems.

Because we (Octeract) sell nonlinear optimisation technology we spend a lot of time studying whether a client needs nonlinear optimisation, or if they are better off using linear approximations. Our conclusion so far has been it depends on the math and the people writing the math.

Certain problems are just not amenable to linearisations. These predominantly tend to be problems where the price of things is a dependent variable. In these cases we have seen linearised models (that our clients were using at the time) diverge by up to 10,000% from where the global solution actually was. In other cases, where clients were using massive linear models with only a few nonlinear terms, linearisations were just fine. In process design problems, we have seen deviations up to 2,000%. When it comes to modelling risk, we have seen that linearising inherently nonlinear dependencies is basically equivalent to making random decisions - solutions tend to be at least 10x the noise in the data.

If I was to distil these down to rules of thumb, then I would say that:

  • linearisations work well for problems that are mostly linear

  • linearisations work well if variable dependencies are not critical to performance

  • linearisations work well as long as they produce sub-million variable MILPs

  • linearisations make (partial) sense if someone has already paid for a license for an expensive linear solver

  • linearisations make sense for applications where accuracy is not that important, but getting a feasible solution quickly is (e.g. certain control problems).

  • linearisations make sense if you know there is little noise in the data. Otherwise it is impossible to tell how good the solution of the linearisation is.

  • linearisations make sense when doing soft constraint modelling, or linearising fairly smooth parts of nonlinear problems to make them more easy to solve.

  • linearisations make sense in cases where we empirically know that they work well.

  • linearisations make sense as long as the person performing them is experienced enough to avoid a combinatorial explosion.

In all other cases it is worth at least trying to solve the MINLP and measure the difference in quality of solution, performance, and consistency.

$\endgroup$

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.