Introduction to Optimization

A deep dive into optimization must begin with an understanding of the optimization problem itself, which originates from calculating the derivatives of continuous functions, familiar from high school mathematics. Optimization generalizes and deepens these mathematical problems in engineering modeling.

During this tutorial you will learn:

1. What is optimization and what does a formal statement of an optimization problem look like;

2. What types of optimization problems are there?

3. What is an objective function and why is it needed to solve an optimization problem;

1.  Definition of optimization

Optimization is the process of searching for the best (optimal) solution to a problem with a given objective function, constraint functions, and convergence criteria for the solution.

Next, the concept of an objective function will be introduced. This tutorial will examine various types of objective functions that require the use of a particular optimization algorithm.

2.  Statement of the optimization problem

The optimization problem is mathematically formulated as follows:

(1)\[\begin{split}\left\{ \begin{aligned} & \min_{x} f(x) \\ & x \in \chi \end{aligned} \right.\end{split}\]

In the optimization problem (1) the following notations are used:

• \(f\) is the objective function for solving the optimization problem,

• \(x\) - function parameter (or design point),

• \(\chi\) is the set of admissible values ​​of the function parameter.

The value \(x\) that belongs to \(\chi\) and that minimizes the objective function \(f\) is the solution to the optimization problem or the minimum parameter (point), denoted by \(x^{*}\).

In the optimization problem (1), the parameter \(x\) can be either a scalar represented as a real number (double in Java) or a vector represented as a set of \(n\) real numbers (3).

(2)\[x = [x_1, x_2, ..., x_n]\]

Objective function is a function \(f\) whose parameter \(x\) is changed by an optimization algorithm in order to achieve the minimum value of the function.

3.  Critical points

Solving an optimization problem involves the concept of critical points. To introduce this concept, we need to consider a one-dimensional objective function, shown in the graph below.

Critical points of a one-dimensional function

The following notations are used in the graph above.

Lines, points	Description
Blue line	Objective function \(f(x) = 5 \cdot \cos(x) + 0.5 \cdot (x - 1.5 \cdot \pi)^2\), \(x \in [0; 11]\)
Orange point	Local minimum point
Green point	Global minimum point

Critical points are the points of the objective function \(f(x)\) at which the derivative \(f'(x^{*})\) is zero. At a local minimum point, \(f'(x^{*}) = 0\) and \(f''(x^{*}) > 0\). A global minimum point has the smallest value of \(f(x)\) on a given set \(x \in \chi\).

Note

The following points are also considered critical points:

• Points of inflection of the function, where \(f''(x^{*}) = 0\) and \(f''\) changes sign in the region of this point;

• Points where the derivative does not exist.

Such points will not be considered within the framework of this tutorial.

If an optimization algorithm is designed to find a local minimum, then it solves a local optimization problem. A global optimization algorithm aims to find a global minimum.

Optimization also includes the common problem of finding the root of an objective function, where it is necessary to determine an \(x\) for which the condition \(f(x) = \text{const}\) is satisfied. This problem will be discussed in a separate tutorial.

The next section discusses the search for a local minimum point using the example of a parabola equation chosen as a simple objective function for solving a local optimization problem.

4.  An example of finding a local minimum of a parabola

Let objective function have the form of the following polynomial \(f(x) = (x - 5)^2 - 20\), for which the analytical solution is known. This simple feature will allow you to focus on gaining skills in working with the Optimization of the REPEAT VISION platform.

Parabola with offset

The following notations are used in the graph above.

Lines, points	Description
Blue line	The objective function \(f(x) = (x - 5)^2 - 20\), \(x \in [0; 10]\)
Orange point	Local minimum point

4.1.  Analytical solution

The parabola has a derivative \(f'(x) = 2 \cdot (x - 5)\), which is zero when \(x^{*} = 5\), and the condition \(f''(x^{*}) > 0\) is also satisfied. The minimum of the objective function \(f(x^{*})\) is -20.

4.2.  Creating a model in REPEAT VISION

To create a model for calculating the objective function \(f(x) = (x - 5)^2 - 20\) on the REPEAT VISION platform, you need to add 4 blocks of the Automation library to a new project, with a name, for example, Parabola with offset.

Parabola Value Calculation Model in REPEAT VISION

First, block №1 Constant is added to the project with the Constant value property equal to 0. This block will be used as parameter \(x\) (see equation (1)) of the objective function \(f(x)\).

Next, block №2 Bias is added to the project with the Bias property equal to -5. This block will be used to calculate the offset \(x - 5\).

Then block №3 Raising to the constant power is added, with the Power property equal to 2. This block will be used to square the previously calculated value, \((x - 5)^2\).

To complete the model preparation, add block №4 Bias with the Bias property set to -20. This block performs the final operation in calculating the objective function \(f(x) = (x - 5)^2 - 20\).

For this stationary problem statement, it will be sufficient to use the following project settings:

Simulation time \([s]\)	Integration step \([ms]\)	Sampling step \([ms]\)
0.1	50	50

In the next section, the optimizer is configured to obtain a solution to the optimization problem.

4.3.  Configuring the optimizer

To configure the Optimization, you need to click on the ‘Optimization’ icon on the bottom panel.

The location of the Optimization icon on the bottom panel of the REPEAT VISION interface

In the tab that opens, you need to apply the settings to solve the local optimization problem.

Main settings

In the Main settings section, you need to apply the following settings.

Optimization task type	Optimization budget	Handling of non-physical values (NaN)
Local optimization	25	Raise exception

Optimization budget is the number of available optimizer calls to the computational model for calculating the objective function. Each time the algorithm passes the next value of the parameter \(x\) to the objective function and receives a new value of the objective function \(f(x)\) in response, the budget decreases by 1. When the budget is exhausted, optimization is forcibly stopped.

Hint

For simple, smooth, continuous objective functions similar to quadratic functions, a small budget (\(10 \leq budget \leq 100\)) is sufficient to solve a local optimization problem.

In the Handling of non-physical values (NaN) setting, you should select Raise exception since in a simple model there will be no problems with calculating the objective function that could lead to errors during modeling. Therefore, there is no need for additional processing of the calculation results with checking for the physicality of the results of calculating the objective function.

Optimization algorithm

In the Optimization algorithm section, you need to apply the following settings.

Optimization method	Absolute tolerance of the varied parameter
Bounded method	1e-12

In the Optimization method setting, you must select the Bounded method to solve the local optimization problem using the Brent method, which guarantees the convergence of the solution to the problem for an objective function that is computable within the specified boundaries.

The setting Absolute tolerance of the varied parameter must be assigned a value of 1e-12 to fix the convergence criterion for the solution of the optimization problem for the parameter \(x\).

Note

It should be noted that the small value of 1e-12, close to the precision of a double in Java, is suitable for the Bounded method and smooth, continuous objective functions.

Parameter settings

In the Objective function calculation block setting, located in the Optimized parameters section, you must select the Output port of block №4 Bias, which performs the final operation of calculating the objective function \(f(x)\).

In the Varied block property setting, located in the Variable properties section, you must select the Constant value property of block №1 Constant. The Constant value of the block will be used by the optimizer as a variable parameter \(x\) to minimize the objective function \(f(x)\) (see equation (1)).

It is also necessary to specify the bounds within which local optimization is performed. In the current example, the objective function boundaries are set to \(x \in [0; 10]\). Therefore, 0 must be entered in the Min value field, and 10 must be entered in the Max value field.

4.4.  Launch optimization

After completing the Optimization setup, you need to run optimization. To run optimization, click the Optimize button.

Click the Optimize button to start optimization.

After clicking the button, notifications about the start of optimization and the successful completion of optimization will appear (#pic_popup_opt).

Notifications of optimization process stages

After successful completion of optimization, it is necessary to analyze the obtained solution.

4.5.  Analysis of optimization results

The optimization results are available in the corresponding section for analysis after successful completion of optimization.

Optimization results

The optimizer determined a local minimum of the objective function \(f(x)\) for the parameter \(x\) equal to 5, which corresponds to the exact analytical solution.The optimizer determined a local minimum of the objective function \(f(x)\) for the parameter \(x\) equal to 5, which corresponds to the exact analytical solution.

Next, you need to click on the Apply all button to transfer the optimal value \(x^{*} = 5\) to the Constant value property of block №1 Constant. After clicking the button, a notification will appear indicating that the optimal properties have been successfully applied.

Application to the model of optimal properties

At the end of the analysis, it is necessary to run the calculation of the model with the optimal value \(x^{*} = 5\) and get the calculation result on the Output port of block №4 Bias, which performs the final operation of calculating the objective function \(f(x)\).

Minimum value of the objective function at x = 5.

The calculation result shows a local minimum of the objective function \(f(x^{*}) = -20\) with the optimal value of the parameter \(x^{*} = 5\), which corresponds to the exact analytical solution.

5.  Conclusions

As a result of completing the introductory tutorial on solving optimization problems, you learned:

1. On the concept of optimization and the mathematical formulation of an optimization problem;

2. On the concept of the objective function and its purpose in solving optimization problems;

3. About categories of optimization problems;

4. Using a simple example, we mastered the Optimization of the REPEAT VISION platform to solve a local optimization problem.