ACADO Toolkit

Static Optimization Problem with Two Objectives

This tutorial explains how to set up multi-objective optimization problems in ACADO and discusses several algorithmic settings. As an introductory example a static optimization problems with two objectives is considered.

Part 1: Mathematical formulation
Part 2: An ACADO tutorial code
Part 3: ACADO results

Mathematical formulation

For the static bi-objective problem only two scalar variables are involved: y₁ and y₂ . The aim is to simultaneously minimize these two variables. However, both are bounded and have to satisfy a nonlinear constraint.

[back to top]

An ACADO tutorial code

The following piece of code illustrates how to set up the bi-objective optimization problem mentioned above. The Pareto set is first generated with 41 points based on NBI, and filtered afterwards using the Pareto filter algorithm. Both original and the filtered Pareto set are plotted and exported. This code is available in the examples/multi_objective directory as scalar2_nbi.cpp. The WS and NNC version are called scalar2_ws.cpp and scalar2_nnc.cpp, respectively.


  #include <acado_optimal_control.hpp>
  #include <include/acado_gnuplot/gnuplot_window.hpp>
 
  int main( ){

    USING_NAMESPACE_ACADO


    // INTRODUCE THE VARIABLES:
    // -------------------------
    Parameter y1,y2;


    // DEFINE AN OPTIMIZATION PROBLEM:
    // -------------------------------
    NLP nlp;
    nlp.minimize( 0, y1 );
    nlp.minimize( 1, y2 );

    nlp.subjectTo( 0.0 <= y1 <= 5.0 );
    nlp.subjectTo( 0.0 <= y2 <= 5.2 );
    nlp.subjectTo( 0.0 <= y2 - 5.0*exp(-y1)
                             - 2.0*exp(-0.5*(y1-3.0)*(y1-3.0)) );


    // DEFINE A MULTI-OBJECTIVE ALGORITHM AND SOLVE THE NLP:
    // -----------------------------------------------------
    MultiObjectiveAlgorithm algorithm(nlp);

    algorithm.set(PARETO_FRONT_GENERATION,PFG_NORMAL_BOUNDARY_INTERSECTION);
    algorithm.set(PARETO_FRONT_DISCRETIZATION,41);
    algorithm.set(KKT_TOLERANCE,1e-12);

    // Minimize individual objective function  
    algorithm.initializeParameters("scalar2_initial2.txt");
    algorithm.solveSingleObjective(1);

    // Minimize individual objective function
    algorithm.initializeParameters("scalar2_initial1.txt");
    algorithm.solveSingleObjective(0);

    // Generate Pareto set 
    algorithm.solve();


    // GET THE RESULT FOR THE PARETO FRONT AND PLOT IT:
    // ------------------------------------------------
    VariablesGrid paretoFront;
    algorithm.getParetoFront( paretoFront );

    GnuplotWindow window1;
      window1.addSubplot( paretoFront,"Pareto Front y1 vs y2",
                                      "y1","y2", PM_POINTS );
    window1.plot( );

    FILE *file = fopen("scalar2_nbi_pareto.txt","w");
    paretoFront.print();
    file << paretoFront;
    fclose(file);


    // FILTER THE PARETO FRONT AND PLOT IT:
    // ------------------------------------
    algorithm.getParetoFrontWithFilter( paretoFront );

    GnuplotWindow window2;
      window2.addSubplot( paretoFront,"Pareto Front (with filter) y1 vs y2",
                                      "y1","y2", PM_POINTS );
    window2.plot( );

    FILE *file2 = fopen("scalar2_nbi_pareto_filtered.txt","w");
    paretoFront.print();
    file2 << paretoFront;
    fclose(file2);


    // PRINT INFORMATION ABOUT THE ALGORITHM:
    // --------------------------------------
    algorithm.printInfo();

    return 0;
  }

Typical settings for multi-objective optimization:

The choice of scalarization method

Currently, three approaches are available: Normal Boundary Intersection, Weighted Sum and Normalized Normal Constraint. The desired method can be selected in the option "ParetoFrontGeneration".


  algorithm.set(PARETO_FRONT_GENERATION,PFG_NORMAL_BOUNDARY_INTERSECTION);
  //algorithm.set(PARETO_FRONT_GENERATION,PFG_WEIGHTED_SUM);
  //algorithm.set(PARETO_FRONT_GENERATION,PFG_NORMALIZED_NORMAL_CONSTRAINT);

As both NBI and NNC require the individual minima, these points are first calculated, before the Pareto set is computed. In the current case, initial guesses are provided for both minimizations. However, for WS precomputing the individual minima is not required.


  // Minimize individual objective function  
  algorithm.initializeParameters("scalar2_initial2.txt");
  algorithm.solveSingleObjective(1);

  // Minimize individual objective function
  algorithm.initializeParameters("scalar2_initial1.txt");
  algorithm.solveSingleObjective(0);

  // Generate Pareto set 
  algorithm.solve();

The number of Pareto points n_p

The number of Pareto points n_p relates to the number of points between two individual minima. Hence, the number of single objective optimizations is n_p for a bi-objective case and 1/2* n_p *( n_p +1) for a tri-objective case. Or for a general multi-objective case with m objectives this number is 1/(2 m !)* n_p *( n_p +1)*...*( n_p +m-2).
```
  algorithm.set( PARETO_FRONT_DISCRETIZATION, 41 );
```

Hot-start re-initialization of the different single objective problems

To speed-up the solution of the different single objective problems, the hot-start strategy is used by default. Here, the solution of a previous single objective optimization is used to initialize the next one. This options can be switched of as follows.
```
  algorithm.set( PARETO_FRONT_HOTSTART, BT_FALSE );
```

Pareto filter

As both NBI and NNC can produce non-Pareto optimal points, a Pareto filter can be employed to remove these points. The rationale behind this Pareto filter is a pairwise comparison of the Pareto candidates.
```
  VariablesGrid paretoFront;
  algorithm.getParetoFront( paretoFront );
  algorithm.getParetoFrontWithFilter( paretoFront );
```

[back to top]

ACADO results

The corresponding Pareto plot as returned by NBI looks as follows in GNUplot.

After filtering, part of the candidate solutions are removed and the following Pareto set is obtained.

The resulting Pareto sets (without and with filtering) are stored in separate files. For this example these files (scalar2_nbi_pareto.txt and scalar2_nbi_pareto_filtered.txt) read as follows.

The unfiltered Pareto set:


  5.0000000000000107e+00 3.0436030146863163e-01 
  4.8510324284838262e+00 3.9969162543346926e-01 
  4.7133911121598349e+00 5.0571008143342888e-01 
  4.5850420277928858e+00 6.2049642303553354e-01 
  4.4641451993538102e+00 7.4231450122746845e-01 
  4.3490799951888750e+00 8.6963513410666815e-01 
  4.2384174965955932e+00 1.0011100346548896e+00 
  4.1308712466129229e+00 1.1355253386984179e+00 
  4.0252392043490266e+00 1.2717468346638157e+00 
  3.9203388647649642e+00 1.4086587444524188e+00 
  3.8149302413018202e+00 1.5450910520393359e+00 
  3.7076137306823567e+00 1.6797231316072156e+00 
  3.5966766651281867e+00 1.8109389585857820e+00 
  3.4798329632877403e+00 1.9365814516773985e+00 
  3.3537245489554657e+00 2.0534820257509918e+00 
  3.2128264698077271e+00 2.1564274930433989e+00 
  3.0465661764272487e+00 2.2354418968369805e+00 
  2.8293166560869163e+00 2.2663443173102213e+00 
  2.4647256611665060e+00 2.1582195159553814e+00
  1.8584089213758319e+00 1.8220091816613602e+00 
  1.5433274412816584e+00 1.7606001493726566e+00 
  1.3462850348245228e+00 1.8105694273777062e+00 
  1.1961741359932123e+00 1.9048219402290063e+00 
  1.0719280625931420e+00 2.0234797662008797e+00 
  9.6442408351665709e-01 2.1579349558683840e+00 
  8.6883450348561131e-01 2.3036322333713701e+00 
  7.8227023942536111e-01 2.4578455421487582e+00 
  7.0285147784670110e-01 2.6188011436947809e+00 
  6.2927821642303783e-01 2.7852723928143126e+00 
  5.6060853512112774e-01 2.9563705205726105e+00 
  4.9613430942411740e-01 3.1314273608299832e+00 
  4.3530697468540458e-01 3.3099253035989671e+00 
  3.7769088215086077e-01 3.4914532831144625e+00 
  3.2293275209686878e-01 3.6756779546841978e+00 
  2.7074096467747111e-01 3.8623241541215165e+00 
  2.2087110100100071e-01 4.0511612547168152e+00 
  1.7311558816070316e-01 4.2419933965831529e+00 
  1.2729611646424321e-01 4.4346523317698354e+00 
  8.3257976125861277e-02 4.6289920805263201e+00 
  4.0865752270796141e-02 4.8248848692309174e+00 
  7.6327832942979512e-17 5.0222179930764810e+00

The Pareto set after filtering:


  5.0000000000000107e+00 3.0436030146863163e-01 
  4.8510324284838262e+00 3.9969162543346926e-01 
  4.7133911121598349e+00 5.0571008143342888e-01 
  4.5850420277928858e+00 6.2049642303553354e-01 
  4.4641451993538102e+00 7.4231450122746845e-01 
  4.3490799951888750e+00 8.6963513410666815e-01 
  4.2384174965955932e+00 1.0011100346548896e+00 
  4.1308712466129229e+00 1.1355253386984179e+00 
  4.0252392043490266e+00 1.2717468346638157e+00 
  3.9203388647649642e+00 1.4086587444524188e+00 
  3.8149302413018202e+00 1.5450910520393359e+00 
  3.7076137306823567e+00 1.6797231316072156e+00 
  1.5433274412816584e+00 1.7606001493726566e+00 
  1.3462850348245228e+00 1.8105694273777062e+00 
  1.1961741359932123e+00 1.9048219402290063e+00 
  1.0719280625931420e+00 2.0234797662008797e+00 
  9.6442408351665709e-01 2.1579349558683840e+00 
  8.6883450348561131e-01 2.3036322333713701e+00 
  7.8227023942536111e-01 2.4578455421487582e+00 
  7.0285147784670110e-01 2.6188011436947809e+00 
  6.2927821642303783e-01 2.7852723928143126e+00 
  5.6060853512112774e-01 2.9563705205726105e+00 
  4.9613430942411740e-01 3.1314273608299832e+00 
  4.3530697468540458e-01 3.3099253035989671e+00 
  3.7769088215086077e-01 3.4914532831144625e+00 
  3.2293275209686878e-01 3.6756779546841978e+00 
  2.7074096467747111e-01 3.8623241541215165e+00 
  2.2087110100100071e-01 4.0511612547168152e+00 
  1.7311558816070316e-01 4.2419933965831529e+00 
  1.2729611646424321e-01 4.4346523317698354e+00 
  8.3257976125861277e-02 4.6289920805263201e+00 
  4.0865752270796141e-02 4.8248848692309174e+00 
  7.6327832942979512e-17 5.0222179930764810e+00

As can be seen, the non-Pareto optimal points depicted in red are removed by the Pareto filter.

[back to top]

Static Optimization Problem with Two Objectives

Topics

Interesting Links

Current Release