Why the objective function formulation changes the optimization result in multiple shooting method?

Question

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.

Answer 1

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.