Allow us to take into account a nonlinear perform f(x), the place x is a steady variable. We wish to discover the minimal worth of this perform f(x) by altering our determination variable x. The optimization drawback can mathematically be formulated within the following method:

Usually, the consumer comes throughout some constraints that should be thought of. That may for instance be a minimal required temperature in a room, a constraint on how a lot stress is placed on a cloth, or the minimal period of time you need/want to attend till you drink your subsequent espresso.

These constraints come both within the type of equalities or inequalities. For the sake of simplicity, we’ll assume that now we have solely inequality constraints, described by g(x)≤0. We are able to subsequently add this constraint to the optimization drawback as as follows:

If the features (f(x) and g(x), or solely one among them) are nonlinear, we would want to make use of nonlinear solvers. We attempt to keep away from this, which is the place a linearization step comes into play. So let’s pause our dialogue about optimization and first have a look at a way that permits us to approximate a nonlinear perform.

To visualise and higher perceive this half, take into account a logarithmic perform f(x)=log(x) within the vary of x=[1,6]:

# Get some packages
import numpy as np
import matplotlib.pyplot as plt
# Create nonlinear perform
def f(x):
return np.log(x)
# Outline decrease and higher values and an x-range
xlb = 1
xub = 6
numx = 100
x = np.linspace(xlb, xub, numx)
y = f(x)
# Plot the perform
plt.determine()
plt.plot(x, y, coloration='blue', linestyle='--', label='Nonlinear f(x)')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.legend(frameon=False, loc='decrease proper')
plt.present()

With this piece of code, we are able to produce the next plot:

Now, we begin with the definition of a linear perform, which has the next basic kind (with slope a and an intersection b):

Capabilities are right here to explain one thing. That would for instance be a phyical behaviour or system. This method can in all probability be sampled, so we are able to select our x and might observe what our f(x) is (impartial of the very fact if the system is linear or nonlinear). Instance. If we cook dinner Spaghetti in a pot of water, we might wait 1 minute (x1) and observe how effectively our Spaghetti are cooked (f(x1)). We are able to wait one other 5 minutes (x2) and examine once more how effectively the Spaghetti are executed (f(x2)). I assume what I imply. 😄 🍝

If now we have an setting the place we get some pattern factors out of it, we are able to use them to calculate the corresponding slope a and the intersection b of the road that connects these two factors. Let’s say now we have 2 factors, f(x1) and f(x2). This implies, for the reason that linear mannequin ought to maintain in each factors, we all know that these two equations maintain in each factors as effectively:

We now have two unknowns (a and b) and two equations, so we are able to clear up for a and b:

Utilizing these expressions, we are able to attempt to approximate our thought of perform f(x)=log(x) within the vary of x=[1,6].

Let’s do this in Python. First, we take the decrease and higher bounds as our two factors to outline the section (keep in mind, Python begins indexing at zero, so don’t be confused if it says “section 0”, which is simply our first thought of section):

num_segments = 1
x_segments = np.linspace(xlb, xub, num_segments+1)
for i in vary(num_segments):
print(f'[+] Phase {i} goes from x={x_segments[i]:.2f} to x={x_segments[i+1]:.2f}.')

[+] Phase 0 goes from x=1.00 to x=6.00.

Then, we write a perform that returns the slope and the intersection given two supporting factors (typically additionally referred to as “nodes”), specifically x=[x1,x2] and y=[f(x1),f(x2)]:

def calc_slope_and_intersection(x, y):
slope = (y[1:] - y[:-1])/(x[1:] - x[:-1])
intersection = y[:-1] - slope*x[:-1]
return float(slope), float(intersection)

We then calculate the slopes and intersections and retailer the values in lists:

slope, intersection = [], []
for i in vary(num_segments):
x_segment = x_segments[i:i+2]   # Get the x values for the section
y_segment = f(x_segment)        # Pattern from nonlinear setting
slope_, intersection_ = calc_slope_and_intersection(x_segment, y_segment)
slope.append(slope_)
intersection.append(intersection_)
print(f'[+] Linear perform of section {i}: x*{slope[i]:.2f}+({intersection[i]:.2f}).')

[+] Linear perform of section 0: x*0.36+(-0.36).

The slope is calculated to be a=0.36, the place the intersection has the identical worth of b=0.36. This brings us to the next linear equation as approximation:

We are able to plot this along with the unique logarithmic perform:

# Operate that creates a linear perform from slope and intersection
def get_linear(slope, intersection, xlb, xub):
x_ = np.array([xlb, xub])
return slope*x_ + intersection
# Plot the linear features
plt.determine()
plt.plot(x, y, coloration='blue', linestyle='--', label='Nonlinear f(x)') # Nonlinear perform
for i in vary(num_segments):
x_segment = x_segments[i:i+2]
y_segment = get_linear(slope[i], intersection[i], x_segment[0], x_segment[1])
plt.plot(x_segment, y_segment, coloration='orange', linestyle='-', label='Linear section' if i==0 else '__nolabel__')    # Linear segments
plt.plot(x_segment, y_segment, coloration='black', linestyle='', marker='x', label='Nodes' if i==0 else '__nolabel__')   # Nodes
plt.xlabel('x')
plt.ylabel('f(x)')
plt.legend(frameon=False, loc='decrease proper')
plt.present()

Effectively. That’s not very correct. But it surely’s linear, and it goes by means of the 2 nodes we used. So in essence, it does what we wish. Now we are able to pattern the perform a bit extra typically (use extra of those nodes), which brings us to the piecewise linearization method.

Allow us to break up the complete x-range into n segments (i=1,2,…,n), and carry out the above-shown linearization of the perform f(x) in every section. Within the equations under, the notation N describes the set of those segments, which means N={1,2,…,n}. For every linear perform, we’d like its particular person slope and intersection:

Since we are able to outline numerous desired values for x after which pattern the corresponding values for f(x) from our (unknown) perform, we are able to once more calculate the slopes and intersections. Allow us to subsequently outline some extra x-values for the totally different segments (the nodes). Say we use n=3.

The identical code snippets from above can be utilized, simply modify the variable num_segments to three. The x-ranges of the segments and their equations are given as follows:

[+] Phase 0 goes from x=1.00 to x=2.67.
[+] Phase 1 goes from x=2.67 to x=4.33.
[+] Phase 2 goes from x=4.33 to x=6.00.
[+] Linear perform of section 0: x*0.59+(-0.59).
[+] Linear perform of section 1: x*0.29+(0.20).
[+] Linear perform of section 2: x*0.20+(0.62).

Seems to be a bit higher. We might additional improve the variety of segments, however dwelling at limits is just not at all times what we wish, so let’s follow n=3 in the intervening time. 😎

With this, we recognized a attainable approximation of the nonlinear perform f(x). Let’s return and substitute this nonlinearity in our unique optimization drawback.

Once more, the objective is to search out the minimal of the perform f(x), contemplating that it must be above a given specification Okay. We are able to formulate this as proven above, the place our inequality constraint g(x)≤0 is mainly Okay-f(x)≤0:

Since now we have linearized our perform in segments, all segments the optimization drawback should be thought of. That is attainable by creating one other variable z for every section. This variable needs to be binary (both 0 or 1). It’s 0 if the section is inactive, and 1 if the section is lively (which means our minimal resolution we’re on the lookout for is positioned on this section).

We are able to now sum up all of the linear features of the segments and multiply them with the corresponding z variable.

We additionally take into account that our optimum resolution can solely be in a single section on the time. In different phrases, just one section could be lively, which means the sum of all z variables must be 1:

Or in a barely totally different kind:

Effectively, it seems to be like we didn’t an excellent job. This drawback formulation is now nonlinear (as a result of multiplication of x with z within the goal perform and the constraint) and even has integer variables (z).

Nevertheless, there’s a easy trick that permits us rewriting such a “pseudo bilinear time period” (which is a nonlinearity). First, we outline an auxiliary variable x-tilde, which is the multiplication of the continual variable (x) with the binary variable (z):

Subsequent, we have to outline the area by which x-tilde could be legitimate for the circumstances when z=0 (inactive section) and z=1 (lively section). If the section is inactive, our auxiliary variable must be zero. We obtain this by the next inequalities:

The place xmin and xmax are the lower- and higher “nodes” which we calculated above. You’ll be able to simply confirm that if z is zero, x-tilde is pressured to be zero as effectively.

As well as, if z=1, the auxilary variable x-tilde needs to be bounded by the “true” steady variable x:

It’s price to say right here that xub is the higher certain of the continual variable x (not those of the intermediate nodes). With this, we are able to rewrite our optimization drawback from above:

You would possibly wish to undergo it once more with a cup of espresso ☕