Initialization of Nonlinear Optimization Algorithms

When nonlinear optimization algorithms are used to solve mathematical programs often initializations are required. In some special cases, e.g. if an optimization problem is convex, no such initialization is needed as there are guarantees that the algorithm converges. However, even for such convex problems, initial guesses that are close to the optimal solution might considerably speed up the iteration progress. In ACADO Toolkit the implementation methods, how initializations can be provided, can basically be devided into three main variants.

Using the ACADO auto-initialization

The most convenient way of initializing an algorithm is by relying on the auto-initialization. This auto-initialization routine does often work for not too difficult problems, which are either convex or not too nonlinear. In the previous example Time Optimal Control of a Rocket Flight we have already used the auto-initialization without understanding the details. The key strategy of ACADO is to use the constraints of the problem to generate an initial guess. For example the code lines

        ocp.subjectTo( -1.1 <= u <=  1.1   );  
        ocp.subjectTo(  5.0 <= T <= 15.0   );

define bounds on a control input u and the horizon lengthT. If nothing else is specified, ACADO will detetect these bounds and initialize with u(t) = 0 for all t ∈ [0,T] as this is the arithmetic mean between the upper and the lower bound. Similarly, the parameter T, representing in our example the duration of the rocket flight, will be initialized with T = 10. If only one bound is specified, the corresponding variable will be initialized at this bound. If no constraint has been detected the auto-initialization routine will start with 0 as an initial guess. Similarly, the differential states are initialized by the first simulation with the specified initial values.

Let us sketch the algotithmic strategy of the auto-initialization routine as follows:

Summarizing the strategy, all bounds on the variables are used to improve the initial guess. Thus, it is recommended to provide reasonable bounds for the case that auto-initialization should be used.

Advantages of the auto-initialization: .

Disadvantages of the auto-initialization: .

Loading the initialization from a text file

As an alternative to the auto-initialization it is possible to specify initial values in a simple text file. In ACADO Toolkit convenient reading routines are implemented. In order to demonstrate an example we assume that we have defined an optimal control problem "ocp" as it as been discussed in the previous tutorial A Guiding Example: Time Optimal Control of a Rocket Flight. Now, we try to solve this optimal control problem via the following lines of code:

        OptimizationAlgorithm algorithm(ocp);
        
        algorithm.initializeDifferentialStates( "x.txt" );  
        algorithm.initializeControls          ( "u.txt" );
        algorithm.initializeParameters        ( "p.txt" );
        
        algorithm.solve();

Here, the initialization for the differential states, controls, and parameters are assumed to be stored in separate files, which contain the corresponding time-series. For example these files could read as follows:

The file "x.txt":

time        s          v         m

0.00e+00  0.00e+00  0.00e+00  1.00e+00   
1.00e-01  2.99e-01  7.90e-01  9.90e-01 
2.00e-01  1.13e+00  1.42e+00  9.81e-01 
3.00e-01  2.33e+00  1.69e+00  9.75e-01 
4.00e-01  3.60e+00  1.70e+00  9.73e-01 
5.00e-01  4.86e+00  1.70e+00  9.70e-01 
6.00e-01  6.13e+00  1.70e+00  9.68e-01 
7.00e-01  7.39e+00  1.70e+00  9.65e-01 
8.00e-01  8.66e+00  1.70e+00  9.63e-01 
9.00e-01  9.67e+00  8.98e-01  9.58e-01 
1.00e+00  1.00e+01  0.00e+00  9.49e-01

The file "u.txt":

time       u

0.00e+00  1.10e+00   
1.00e-01  1.10e+00
2.00e-01  1.10e+00
2.99e-01  5.78e-01
4.00e-01  5.78e-01
5.00e-01  5.78e-01
6.00e-01  5.78e-01
7.00e-01  5.78e-01
8.00e-01 -2.12e-01
9.00e-01 -1.10e+00
1.00e+00 -1.10e+00

The file "p.txt":

time         T

0.00e+00  7.44e+00   

Actually, this tutorial already describes the most difficult case: first, the time T is optimized in our example, such that the time series for the states and controls have to be rescaled to [0,1]. And second, the number of controls in the file "u.txt" is 11 - but in our example "Time Optimal Control of a Rocket Flight" we have used the default settings, i.e. 20 control intervals. Note that the ACADO toolkit does not require the files to be consistent, i.e. in the above case the missing control and state inititalizations are automatically generated by linear interpolation. Fortunately, having understood this difficult example, we have already understood everything that needs to known about initialization via text files.

Let us summarize the six important key concepts regarding the initialization via text files:

Finally, we discuss the general advantages and disadvantages of the initialization method via text files:

Advantages of the initialization via text files:

Disadvantages of the initialization via text files:

Using ACADO data structures for the initialization

The third way of initializing a nonlinear optimization algorithm is based on the data structures which are available in ACADO Toolkit. The class which is needed for this purpose is called "VariablesGrid". This data class is suitable to store time series of vector valued functions. Let us explain this concept by considering the following piece of code:

        OptimizationAlgorithm algorithm(ocp);
        
        Grid timeGrid( 0.0, 1.0, 11 );
        
        VariablesGrid   x_init( 3, timeGrid );
        VariablesGrid   u_init( 1, timeGrid );
        VariablesGrid   p_init( 1, timeGrid );
        
        x_init(0,0 ) = 0.00e+00; x_init(1,0 ) = 0.00e+00; x_init(2,0 ) = 1.00e+00;   
        x_init(0,1 ) = 2.99e-01; x_init(1,1 ) = 7.90e-01; x_init(2,1 ) = 9.90e-01; 
        x_init(0,2 ) = 1.13e+00; x_init(1,2 ) = 1.42e+00; x_init(2,2 ) = 9.81e-01; 
        x_init(0,3 ) = 2.33e+00; x_init(1,3 ) = 1.69e+00; x_init(2,3 ) = 9.75e-01; 
        x_init(0,4 ) = 3.60e+00; x_init(1,4 ) = 1.70e+00; x_init(2,4 ) = 9.73e-01; 
        x_init(0,5 ) = 4.86e+00; x_init(1,5 ) = 1.70e+00; x_init(2,5 ) = 9.70e-01; 
        x_init(0,6 ) = 6.13e+00; x_init(1,6 ) = 1.70e+00; x_init(2,6 ) = 9.68e-01; 
        x_init(0,7 ) = 7.39e+00; x_init(1,7 ) = 1.70e+00; x_init(2,7 ) = 9.65e-01; 
        x_init(0,8 ) = 8.66e+00; x_init(1,8 ) = 1.70e+00; x_init(2,8 ) = 9.63e-01; 
        x_init(0,9 ) = 9.67e+00; x_init(1,9 ) = 8.98e-01; x_init(2,9 ) = 9.58e-01; 
        x_init(0,10) = 1.00e+01; x_init(1,10) = 0.00e+00; x_init(2,10) = 9.49e-01;
        
        u_init(0,0 ) =  1.10e+00;   
        u_init(0,1 ) =  1.10e+00;
        u_init(0,2 ) =  1.10e+00;
        u_init(0,3 ) =  5.78e-01;
        u_init(0,4 ) =  5.78e-01;
        u_init(0,5 ) =  5.78e-01;
        u_init(0,6 ) =  5.78e-01;
        u_init(0,7 ) =  5.78e-01;
        u_init(0,8 ) = -2.12e-01;
        u_init(0,9 ) = -1.10e+00;
        u_init(0,10) = -1.10e+00;
        
        p_init(0,0 ) =  7.44e+00;
        
        algorithm.initializeDifferentialStates( x_init );
        algorithm.initializeControls          ( u_init );
        algorithm.initializeParameters        ( p_init );
        
        algorithm.solve();

Note that the above example is equivalent to the previous example with the text files. The only difference is that the initialization is not read-in but directly hard-coded in the C++ file. The class Grid is constructed with three arguments: the line "Grid timeGrid( 0.0, 1.0, 11 ); " constructs a grid with 11 time points that are equally distributed over the interval [0.0,1.0]. Moreover, the constructor of the VariablesGrid gets the dimensions of the function and the sampling time grid (in our example the differential states have the dimension 3, while the controls and parameters have both the dimension 1). The rest is the same as for the initialization with text files.

Advantages of the initialization via ACADO data structures:

Disadvantages of the initialization via ACADO data structures:

Next example: Algorithmic Options and Numerical Accuracy



acado
Author(s): Milan Vukov, Rien Quirynen
autogenerated on Sat Jun 8 2019 19:40:23