1
$\begingroup$

I need to compute an optimal control for the following problem: $$\begin{cases}\dot{x}=f(x,u),\quad x(0)=x_0\in\mathbb{R}^n\\g(x(t_i),u(t_i),t_i)\leq 0\\\sum_{i\in I} x_i(T)\rightarrow \min,\end{cases}$$ where $0=t_0<t_1<\dots<t_n=T$ are fixed instants of time and the control $u_i\in\mathbb{R}^m$ is assumed to be constant over each interval $[t_i,t_{i+1})$, $i=0,\dots,n-1$. The objective function to minimize is the sum of some components of the state vector $x$ at time $T$.

To solve this problem I programmed a method of multiple shooting, i.e., I consider $x(t_i)$ and $u_i$ as decision variables and formulate the following constraints: $$\begin{cases}x(t_{i+1})-\phi(x(t_i),u_i,t_{i+1})=0& \mbox{continuity constraints}\\g(x(t_i),u_i,t_i)\leq0&\mbox{path constraints},\end{cases}$$ where $\phi(x(t_i),u_i,t_{i+1})$ is the solution of the system's DEs at time $t_{i+1}$ when starting from $x(t_i)$ with control $u_i$.


Now comes the question. I can formulate the objective function in a number of formally equivalent ways:

  • $F_n=\sum_{i\in I}\phi_i(x_0,[u_1,\dots,u_n],t_n)$
  • $F_{n-1}=\sum_{i\in I}\phi_i(x(t_1),[u_2,\dots,u_n],t_n)$
  • $\dots$
  • $F_1=\sum_{i\in I}\phi_i(x(t_{i-1}),u_n,t_n)$
  • $F_0=\sum_{i\in I}x_i(t_n)$

That is to say, I can start from the initial condition and integrate the system throughout the whole time interval or start from some intermediate state $x(t_i)$ and integrate from that time on or just take the latest values of $x$ at $t_n=T$ (which I wouldn't compute otherwise) and define the objective function in terms of these values only.

It turns out that as I modify the problem formulation by reformulating the objective function from $F_n$ to $F_{n-1}$ and so on till $F_0$, the optimization result continuously improves, i.e., it converges to a better solution, which I find somehow counterintuitive (note that technically, it's still the same objective function, just formulated in a different manner).

Is there any theoretical explanation to this phenomenon?

A bit of technical information: the optimization script was implemented with Matlab's Fmincon, the optimization method used: SQP. The system of DEs on subintervals was solved with ODExx

My thoughts:

  • these objective functions are equivalent provided the continuity condition hold. So, their values may differ during the initial stage, but they should converge as the optimization algorithm (SQP) first ensures that the constraints are satisfied (i.e., enters the admissible set) and then moves towards the (locally) optimal solution along the admissible set.

  • it seems that this phenomenon is somehow related to the sensitivity of the objective function(?), constraints(?). It can be seen that the path constraints $g(x(t_i),u(t_i),t_i)\leq 0$ get "tighter", i.e., closer to equalities as we move towards $F_0$.

  • another intuitive explanation is that by choosing $F_0$ we shift some part of the job to the continuity constraints while when choosing $F_n$ we redo the same work within the objective function.


Should someone wish to play with the code, I can send it along or embed in the question, whatever is more convenient.

$\endgroup$
7
  • $\begingroup$ Sanity check: Are you absolutely certain that your objective functions are equivalent? Have you checked by plugging in the same values of the optimization variables to each? Does the better solution to $F_0$ still have a lower $F_n$ value than the solution originally found for $F_n$? $\endgroup$
    – user856
    May 18, 2018 at 6:45
  • $\begingroup$ @Rahul, to the second question: Yes. I visualize the results by integrating the system from $x_0$ with the obtained controls $u_0,\dots,u_{n-1}$. That is, I alsways compute $F_n$ when checking the results. First question: these are equivalent, but not equal. That is, thay take different values during the optimization process because they are defined in terms of different variables. I'll modify my question in a couple of minutes to add some of my thoughts. $\endgroup$
    – Dmitry
    May 18, 2018 at 7:35
  • $\begingroup$ $x(t_1)$ depends on $u_1$, you can not simply eliminate that first segment, as you then lose the condition at $t_0$. And the same for the other formulas. Or in other words, in trying out the different objective functions, did you also always check that the inequality constraints are all satisfied? $\endgroup$ May 18, 2018 at 10:10
  • $\begingroup$ @LutzL, indeed, it depends. But this is taken care by the continuity constraint. It ensures that $x(t_1)-\phi(x_0,u_0)=0$. $\endgroup$
    – Dmitry
    May 18, 2018 at 10:14
  • $\begingroup$ @LutzL, It seems that by choosing $F_0$ I shift some part of the job to the continuity constraints while when choosing $F_n$ I redo the same work within the objective function. But I cannot formalize this intuition... $\endgroup$
    – Dmitry
    May 18, 2018 at 10:17

1 Answer 1

1
+100
$\begingroup$

Let me hazard a guess, without knowing the details of your code. (I don't know how you feed the problem into the optimisation routine and how fmincon actually works. You confirmed that you are using ceq(x) for the path constraints $g\le 0$ and c(x) for the continuity constraints in the fmincon routine.)

Observation 1. Once the optimisations have converged, $x(t_{n-1})$ used in $F_0$ must be different from $x(t_{n-1})$ used in $F_1$. This must be the case, otherwise $x(t_{n})$ in $F_0$ would be the same as $x(t_{n})$ in $F_1$ (because you're integrating the same differential equation with the same initial value at $x(t_{n-1})$ and same input) and then you'd be getting the same values for the objective functions $F_0$ and $F_1$, which you are not. Similarly, $x(t_{n-j})$ used in $F_{j-1}$ must be different from $x(t_{n-j})$ used in $F_{j}$.

Observation 2. The more you relax the constraints (the more violation you allow), the better (the lower) objective function you can achieve. E.g. the inequality constraint $g\le 0$ is often some upper bound on energy that you can use to steer the system (or it can include energy among other things, such as spatial constraints of motion). If you are allowed more energy (more forceful control), then you can typically achieve better objective function.

You don't say how much change you see between $F_n, F_{n-1},\dots, F_1, F_0$. I assume it's small compared to the value of the objective function. But how small?

If $F_0=\sum_{i\in I}x_i(t_n)$ and $F_1=\sum_{i\in I}\phi_i(x(t_{n-1}),u_n,t_n)$ (note: I corrected a typo relative to your definition of $F_1$) are basically equal, but $F_2, \dots, F_{n-1}, F_n$ are monotone increasing, then here is what can be wrong.

When you integrate the differential equation from the initial state $t_i$ in some $F_{n-i}$, then you get a continuous trajectory. When you do the calculation for some $F_{n-j}$ with $j>i$, which gives you a better optimum, then you have a continuous trajectory from $t_j$ to $t_n$, but the trajectory from $t_i$ to $t_j$ is only as continuous as the tolerance of the continuity constraint enforces it. The more wiggle room there is there, the more potential there is for the optimisation to exploit (think of Observation 2). Moreover, it could be the case that the two trajectories before $t_i$ are more or less identical.

In the light of this and Observation 1, you could check the values of $x(t_j)$ and its left limit in $F_i$ for all $i,j$ pairs.

$\endgroup$
4
  • $\begingroup$ thank you for your answer. As a first iteraton, let me comment on your remarks and observations. 1) Right, ceq(x) and c(x). 2) Obs. 1: I start from the same initial conditions, so initially these values are the same. As the optimization goes on, it converges to different values. 3) Obs. 2: I do not actually relax the constraints. I do not change ceq(x) and c(x), only the objective function. 4) For 10 intervals the values of F are: 2901, 2841, 2846, 2832, ... ,2543, 2528. So, there is a substantial improvement. I'll add more tomorrow $\endgroup$
    – Dmitry
    May 24, 2018 at 16:16
  • $\begingroup$ I made small updates to clarify 1) and 2). As to 3), I know you are not relaxing the conditions. I meant it as a thought experiment (if... then...) with the generic you. The conjecture in my answer is that numeric errors in the continuity constraint might have the same effect as a relaxation. I don't know how great an effect they have, maybe not great enough. 4) is useful info. $\endgroup$ May 24, 2018 at 16:36
  • $\begingroup$ The more obvious set of experiments you could do is to decrease the tolerances ConstraintTolerance (this is the prime suspect in my answer), OptimalityTolerance and StepTolerance, to increase MaxIterations (perhaps in different combinations) and see whether $F_n, \dots, F_0$ get closer to each other. Link 1: de.mathworks.com/help/optim/ug/fmincon.html#busog7r-options Link 2: de.mathworks.com/help/optim/ug/… $\endgroup$ May 25, 2018 at 7:47
  • $\begingroup$ Your interpretation seems plausible. I'll make the suggested changes and report on the results. As for now, I award you the bounty in appreciation of your valuable help. $\endgroup$
    – Dmitry
    May 25, 2018 at 8:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .