The idea behind optimization algorithms is not complex. In primary school, there is fundamental concept in mathematics: division, which can be seen as the inverse of multiplication.
The function $y = f(x) = a x$ represents multiplication. Its inverse, $f^{-1}(y)$, performs the division which is the reverse operation, given by $x = {y}\div{a}$.
For example, in the division $5 \div 9$, with $y=5$ and $a=9$, essentially, it means we find $x$ such that $f(x)=9x = 5$.
This inverse process can be reinterpreted as an optimization problem. The equation $9\times x = 5$ is equivalent to minimizing the difference between $5$ and $9x$. This scenario can be framed as an optimization problem in the following way:
$$ \begin{aligned}\arg\min_{x} \quad &5 - 9x \\\text{s.t.} \quad &5 - 9x \geq 0\end{aligned} $$
The beauty of this optimization problem lies in the interaction between the minimization goal and the constraint, ensuring that the sole valid solution is $5-9x=0$.
This outcome can be deduced through reductio ad absurdum.
Simplified "Proof": The objective function $5−9x$ monotonically decreases as $x$ increases, theoretically reaching a minimum at $-\infty$. However, the constraint establishes a lower boundary for $5−9x$, which is $0$. This effectively prevents the function from decreasing indefinitely and ensures that the minimum value aligns with the solution of $5−9x=0$.
By framing this problem as an optimization problem, we introduce a flexible approach to finding a solution without needing explicit division or equation solving. This approach is more adaptable to complex scenarios where multiple constraints or objectives are present.
The essence of optimization is fundamentally about starting with a basic $x$ (which might be randomly selected and initially perform poorly when plugging into the objective function) and continuously adjusting $x$. This process must ensure that after each adjustment, $x$ achieves a progressively better value of the objective function.
# Initialize x with a random value
x = rand_init()
# Continue the loop until convergence criteria is met
while not converged:
# Forward: Evaluate the function f at the current value of x
f_x = evaluate_f(x)
# Backward: Adjust x to a new value (x_new) in such a way that
# f(x_new) is greater than or equal to f(x)
x_new = adjust_x(x, f_x) , so that f(x_new) > f(x)
# Update x to the new value for the next iteration
x = x_new
"Long Division" is an iterative algorithm to find a positive integer $x$ such that $5 - 9x$ is minimized, while also maintaining the condition $5 - 9x \geq 0$ at each step of the optimization. This algorithm involves dividing a larger number (the dividend) by a smaller number (the divisor) to find a quotient and a remainder.
Long division is a step-by-step procedure (step 1: purple, step 2: green) that breaks down the division process into a series of multiplication and subtraction calculations.
If we plot the update of quotients for different iterations, they can be visualized as follows,
Here, the blue line represents the objective function $5-9x$, while the gray area indicates the feasible solution space for $x$. The task is to determine the value of $x$ which results in the minimum $y$ on the blue line, while ensuring that it never falls within the infeasible area $5-9x<0$.