{'fraction_non_alphanumeric': 0.06771179899390488, 'fraction_numerical': 0.018152298315189906, 'mean_word_length': 3.3410745233968804, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 72, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal synthesis in the simplest time-optimal problem with a linear state constraint

We consider the time-optimal problem for a classical system of"double integrator"under the presence of a linear state constraint. By using the Maximum Principle of Dubovitskii and Milyutin, we determine a complete synthesis of optimal trajectories and qualitatively analyze the corresponding Lagrange multipliers.


Statement of the Problem
T → min, |u| 1, under a linear state constraint Here x is the position of an object (material point) on a straight line, y its velocity, the control u is an acceleration applied to the object, t ∈ [0, T ]. The problem is to move the object from a given initial state (x 0 , y 0 ) to the final state (0, 0) in the minimum time under the linear constraint (3) on the state variables x, y. We assume that u(t) is an arbitrary measurable bounded function, and hence x(t), y(t) are Lipschitz continuous functions.
In the absence of the state constraint, (1)-(2) is a well-known Feldbaum problem that served as one of the first test examples for application of the Pontryagin maximum principle (see [1]). The case when the constraint (3) is present and k = 0, is considered, e.g., in the book [3] as an example of application of the maximum principle (MP) in the form of Dubovitskii-Milyutin. The case of the general constraint (3) has not yet been considered.
Note that (3) is the general form of linear state constraint in this problem which is not vertical. The constraint y kx + b (b > 0) is symmetric to this one. The vertical linear constraints x p and x −p (p > 0) will be considered separately in Sec. 6 below.
If either constraint (3) is absent, or is present with k = 0, the solution can be found without such an advanced theory as MP, by using just basic tools of calculus. Indeed, here we need to find the minimal time interval on which a Lipschitz function y(t) with given endpoints conditions, the bound on its derivative |ẏ| 1, and a lower bound on the function itself y −b has a given integral. In the absence of this lower bound, we conclude by simple considerations that the optimal function is piecewise linear with the derivative ±1 and at most one break. If the obtained function violates the lower bound on some time interval, then one must put y = −b on this interval and expand the latter so that the whole function y(t) has the given integral. A detailed elaboration of this solution can be recommended as an exercise for students.
If the restriction (3) is present and k = 0, the solution can hardly be found in the described way, because here the lower bound for the function y(t) at each point t depends on its integral on the interval [0, t]. We will apply here the maximum principle for problems with state constraints that was obtained by A.Ya. Dubovitskii and A.A. Milyutin in [2].
It is well known that the "deciphering" of MP conditions for searching optimal trajectories is not a routine task even for problems without state constraints. The more so this is true if these constraints are present, when both the conditions and their deciphering are more complicated. If we would knew a qualitative structure of optimal trajectories, the search for them could be essentially more simple, but this structure is not a priori known, and we do not impose any assumptions about that. Therefore, we perform here a detailed procedure of solving a problem with a state constraint by means of the MP. Perhaps it can be useful for solving other problems of this type.
The latter means that Here and thereafterμ(t) is the derivative in the sense of generalized functions. In other words, it is the Radon-Nikodim density of the measure dµ(t) w.r.t. the Lebesgue measure dt, so the adjoint equations should be understood as equalities between measures, i.e., or, in the integral form, for any t ∈ [0, T ] The same relates to condition (7), which should be understood as the equality dµ(t) y 0 (t) − kx 0 (t) + b = 0. This means that dµ(t) can be nonzero only on the state boundary, i.e., dµ(t) = 0 on any time interval where y 0 (t) > kx 0 (t) + b, and so, the costate variables ψ, ϕ are absolutely continuous there.
We do not write the transversality conditions, since the endpoints of trajectory are fixed. The nontriviality condition means that the case ϕ ≡ ψ ≡ 0 is forbidden. In what follows, we drop the superscript 0 for the optimal process.
Before applying the maximum principle, we define the set of starting points from which at least one admissible trajectory originates. This set will be denoted by D and called admissible set. Obviously, it essentially depends on the sign of the coefficient k. It follows from the Filippov theorem that for any initial position from D there exists an optimal trajectory.
3 The case k > 0 : Description of the admissible set Denote by Γ the line y = kx − b (boundary of the admissible state domain), and by S the switching line in the problem without state constraint (we will call it free problem), it is the union of two semi-parabolas: x = − 1 2 y 2 , y 0 and x = 1 2 y 2 , y 0. Introduce the following characteristic points for the case k > 0 ( Fig. 1) 1 : 1) the point A is the intersection of Γ and S, 2) the point E is the intersection of Γ and the abscissa axis, 3) C is the point where the line Γ is tangent to some parabola of the family x = − 1 2 y 2 + const (clearly, this parabola is unique), 4) the point B is the intersection of the tangent parabola from the previous item with the curve S .
One can easily find the coordinates of these points. The point A is defined by the relations x = 1 2 y 2 , y = kx − b, whence The point E = (b/k, 0). The point C is common to the parabola x = − 1 2 y 2 + m and the line y = kx − b, which is tangent to this parabola at C, so dx/dy = −y = 1/k . Hence, The point B is defined by the relations x = − 1 2 y 2 + m x = 1 2 y 2 , whence x B = m/2 , y B = − √ m . However, we do not need these coordinates for qualitative research, only the relative position of the points A and C on the line Γ will be important. Depending on this relative position, there are three possible cases, see Figs. 1, 2 and 3, respectively. First of all, consider properties of admissible trajectories that are valid in all these three cases.
1) The points on the phase boundary that lie below C are never reachable. Indeed, since y < −1/k here, we have u −1 > ky, so (y−kx) • = u−ky > 0, hence we arrive at such a point from the forbidden area, which is impossible.
2) Let C * be the point on the line Γ that is the symmetric to C with respect to E. If we got to the state boundary at a point E 1 C * , then further motion is impossible, because the dynamics (1) moves us into the forbidden area. If we got to Γ at a point E 1 ∈ (E, C * ), then further motion is possible only in the lens formed by the line Γ and the arc of the parabola coming from the point E 1 with the control u = +1, and it is impossible to leave this lens obeying the state constraint. Hence, all the points on the state boundary above E are unreachable. It follows that all the points of the upper half-plane lying to the right of parabola (E ′ , E) and above Γ are also unreachable (because from every such point we would eventually get to the state boundary above the point E ).
3) An important fact is the following Lemma 1 An admissible trajectory cannot pass through the point E.
Thus, we cannot reach E. But then we cannot also reach the entire upper part of the parabola (E ′ , E), because from there we would get either to E, or to the already forbidden area on the right of this parabola.
4) It follows that the set D of initial positions from which there exist admissible trajectories is the half-plane y kx − b except the closed set bounded from the left by the parabola (E ′ , E). These trajectories consist of motions along the parabolas under the controls u = −1 or u = +1, and also motions along the state boundary. Note that D is not closed.

5)
The state boundary can be reached only on the semi-interval [C, E), and hereẋ = y < 0. If at some time interval we are on Γ, then y = kx − b, y = kẋ < 0, so we can move only in "the left-down" direction from the point E, excluding it, to the point C. Since u = ky, in view of the constraint |u| 1 this motion can continue only while |y| 1/k . The limit value y = −1/k corresponds exactly to the point C.
4 The case k > 0: Analysis of MP Let an admissible process x(t), y(t), u(t), t ∈ [0, T ] with a starting point (x 0 , y 0 ) / ∈ Γ satisfy the maximum principle. We now pass to its analysis, which for convenience is divided into a number of separate steps.

Lemma 4
If on some open interval (t 1 , t 2 ) we are on Γ, then ψ = 0 and the measure has a densityμ 0 which is an exponential function. Moreover, ∆µ(t 1 ) = 0, both ψ and ϕ are continuous at t 1 , so they may have jumps only at t 2 .

Lemma 5
The following case is impossible: t 1 < t 2 , r(t 2 ) ∈ Γ, we are outside of Γ for t < t 1 and t > t 2 , both ψ and ϕ are continuous at t 1 and vanish on (t 1 , t 2 ).
Assume that M is nonempty. Denote t 1 = min M, t 2 = max M.
It follows that on any open interval ω ′ ⊂ [t 1 , t 2 ] where we are outside of Γ, we have ψ = 0 (since ω ′ is contained in some maximal interval ω of the above type), and then, due to the control system, ϕ = 0 as well. Thus, if on some interval in [t 1 , t 2 ] we have ψ < 0, then we are on Γ on this interval.
We claim that ψ = ϕ = 0 on (t 1 , t 2 ). Indeed, suppose ψ(t * ) < 0 at some point t * ∈ (t 1 , t 2 ) of its continuity (the case ψ(t * ) > 0 is excluded by Lemma 2). Then ψ < 0 in a neighborhood of this point, so we are on Γ and u = −1. But it is impossible to keep on Γ with this control. Therefore, ψ(t) = 0 at all points of its continuity in (t 1 , t 2 ), and hence, everywhere on (t 1 , t 2 ). Then by Lemma 3 ϕ is an exponential function. Since ϕ = 0 on the above interval ω, we get ϕ = 0 on (t 1 , t 2 ) as well.
It follows from these arguments that an interval ω = (t ′ , t ′′ ) with the above properties cannot exist, and so M = [t 1 , t 2 ]. The lemma is proved. Recall that domain Ω 3 is forbidden, so the set of admissible starting positions D = (Ω 1 ∪ Ω 2 ) \ Ω 3 . 7) Can we have M = {t * } (touching the boundary at a single point) with r(t * ) > C ? By Lemma 2, there is no jump here, soμ ≡ 0, and the motion is the same as in the free problem, i.e. along the parabolas. But this motion has u = −1 in a neighborhood of the point r(t * ), then moving from this point we violate the boundary. So, this case is not possible.
with t 1 < t 2 and r(t 2 ) > C ? By Lemma 4, in this case there is no jump anywhere, ψ = 0 andμ = −ϕ 0 is an exponential function on M. The case ϕ = 0 is excluded by Lemma 5, so ϕ < 0 on M.
For t > t 2 the measure switches off, ϕ = ϕ(t 2 ) < 0,ψ = −ϕ > 0, then ψ > 0, u = +1 until the end, and we cannot get to the origin with this control from r(t 2 ) > C. So, this case is impossible. 9) Suppose that M = {t * } and r(t * ) = C. The first thing that comes to mind in this case is the trajectory C ′ CBO starting at a point C ′ on the parabola C ′ C and having the control u = (−1, −1, +1). Anyway, let us find what the MP implies.
Thus, ψ(t * + 0) < 0 and ψ increases on [t * , T ] (so ϕ < 0 there) changing its sign from minus to plus at a time t B ∈ (t * , T ) corresponding to the point B, with the respective switching of the control from −1 to +1. Sinceμ = 0 both on the left and right of t * , then ∆ψ(t * ) = −∆ϕ(t * ) 0, so ψ increases as well on [0, t * ) up to a value ψ(t * − 0) 0, hence ψ < 0 and u = −1 on this interval. We thus move along the above trajectory C ′ CBO.
Since it is optimal in the free problem, it just occasionally touches the state boundary, which makes no affection on it.
However, let us find a possible value of the jump ∆µ(t * ) := δ for this trajectory. Denote by t C , t B the moments corresponding to the points C, B (here t C = t * ). Choose the normalizationψ = −ϕ = 1 on (t C , T ] for our collection of multipliers. Then ψ = t − t B on (t C , T ] independently of δ, and we should have , so the MP is satisfied. Thus, a possible value of the jump of measure at the point C is not unique, being arbitrary within the above bounds 2 . In particular, if δ = 0, then ψ is totally linear. If δ = 1, then p < 0 on [0, t C ] and linearly increases up to the value ψ(t C − 0) = 0.
Thus, the case when M = {t * } and r(t * ) = C > A is completely done. 10) Finally, let M = [t 1 , t 2 ], t 1 < t 2 and r(t 2 ) = C. Then, by Lemma 4, within M we move along the boundary in the "left-down" direction, the jump at t 1 is absent, ψ is continuous at this point and vanishes on [t 1 , t 2 ), while ϕ = −μ 0 is an exponential function there.
If the jump at t 2 is absent, the measure switches off on [t 2 , T ], then ϕ = const < 0, ψ(t 2 ) = 0 andψ = −ϕ > 0, whence ψ > 0 and u = +1 until the end of motion. Since r(t 2 ) = C > B, we cannot get to the origin under this control.
Thus, the measure must have a jump ∆µ(t 2 ) = δ > 0. Then ∆ϕ(t 2 ) = kδ and ψ(t 2 + 0) = −δ. For definiteness, choose the normalizationψ = −ϕ = 1 for t > t 2 . Then ϕ(t 2 − 0) = −1 − kδ, which gives the above relationsψ > 0, For the given positions of the points C and B (which are determined by the value of k), the value of ∆t is known, so the value of jump δ is uniquely determined. So, we have a trajectory of the type N ′ N CBO with u = (−1, ky, −1, +1) that starts at a point N ′ ∈ int Ω 2 , the first leg of which is the motion with u = −1 to a point N ∈ (C, E). 11) Thus, for the case k > 0 and C > A, we examined all possible cases of location of the set M (the contact set with the state boundary), and for each case we specified the corresponding costate variables and the measure supported on this set.
Since for any starting point in D there is only one trajectory satisfying the MP, it is indeed optimal. This yields the following optimal synthesis. Theorem 1 Let k > 0 and C > A (Fig. 1). In the domain Ω 1 the optimal trajectories are the same as in the free problem.
In the domain int Ω 2 any optimal trajectory is of the type N ′ N CBO with the control u = (−1, ky, −1, +1) and a unique positive jump of measure at the point B, where N is a point on the line interval (C, E).
For starting points lying on the interval (C, E), the optimal trajectories are the "tails" of optimal trajectories starting from int Ω 2 , the first leg of which is the motion with u = −1 to a point on (C, E). Here, the admissible set D = (W 1 ∪ W 2 ) \ W 3 . One can see that Steps 7 and 8 are still valid (see Fig. 2). 12) Consider the case when M = {t * } and r(t * ) = C. Like in Step 9, before and after t * the function ψ is linear (may be, with different coefficients), If ∆µ(t * ) > 0, then ψ < 0 on the right near t * , and further may change its sign to plus, so either u = −1 or u = (−1, +1) on [t * , T ]. However, in both these cases we do not reach the origin. Therefore, ∆µ(t * ) = 0, whence ψ is totally linear and obviously increases, so u = (−1, +1) on [0, T ] with the switching point t * . We obtain the trajectory C ′ CO which is optimal in the free problem. It just occasionally touches the state boundary, which makes no affection both on the trajectory and on the costate variables. 13) Now, let M = [t 1 , t 2 ], t 1 < t 2 and r(t 2 ) = C. Like in Step 10, within M we move along the boundary in the "left-down" direction, ψ < 0 on [0, t 1 ] and increases up to zero, while u = −1. Further on, ψ is continuous at t 1 and vanishes on [t 1 , t 2 ); moreover, ϕ < 0 on [0, t 2 ).
Thus, for any starting point in D, a trajectory satisfying the MP is unique, so it is optimal. Therefore, we obtain Theorem 2 Let k > 0 and C = A = B (Fig. 2). In the domain W 1 the optimal trajectories are the same as in the free problem.
In the domain W 2 an optimal trajectory is of the above type N ′ N CO with u = (−1, ky, +1), where N is a point on the line interval (E, C).
For starting points lying on the interval (C, E), the optimal trajectories are the "tails" of optimal trajectories starting from int W 2 , the first leg of which is the motion with u = −1 to a point on (C, E).

The case k > 0 and C < A
Define the following closed sets (see Fig. 3): The admissible set D = (Q 1 ∪ Q 2 ) \ Q 3 . This case differs from the case C A in that here the motion along the boundary Γ below the point A is of no sense, because one can switch to u = +1 at this point and get to the origin in a smaller time.
Therefore, by Lemma 2 the measure has no jumps here altogether. By analogy to Step 7, one can see that the case when M = {t * } with r(t 2 ) > A is impossible, and by analogy to Step 8, the case when M = [t 1 , t 2 ] with t 1 < t 2 and r(t 2 ) > A, is also impossible.
If M = {t * } with r(t * ) = A, the measure is absent by Lemma 2, so we have the trajectory A ′ AO of the free problem. 14) Consider the only possible case with a nonzero measure, which is when M = [t 1 , t 2 ] with t 1 < t 2 and r(t 2 ) = A. Then, by Lemma 4 ψ = 0 on M, while by Lemma 5 ϕ < 0 on M and hence on the whole interval [0, T ]. Sincė ψ = −ϕ > 0 both on the left of t 1 and the right of t 2 , we have ψ < 0, u = −1 and ψ > 0, u = +1 on these intervals, respectively. Therefore, we obtain a trajectory N ′ N AO with u = (−1, ky, +1), where N is a point on the line interval (E, A).
Since for any starting point in D, a trajectory satisfying the MP is unique, it is optimal. Thus, here the optimal synthesis is as follows.
Theorem 3 Let k > 0 and C < A (Fig. 3). In the domain Q 1 the optimal trajectories are the same as in the free problem.
In the domain Q 2 any optimal trajectory is of the above type N ′ N AO with u = (−1, ky, +1), where N is a point on the line onterval (A, E).
For starting points lying on (A, E), the optimal trajectories are the "tails" of optimal trajectories starting from int Q 2 , the first leg of which is the motion with u = −1 to a point on (A, E).

Remark 1.
Note an important property of the Bellman function V (x 0 , y 0 ) for the studied problem, that appears in both three subcases for k > 0. Recall that it is the minimal time of motion when starting from a point (x 0 , y 0 ). Obviously, V (x 0 , y 0 ) is finite for any point in D. However, if the point (x 0 , y 0 ) tends to boundary parabola (E ′ , E], then V (x 0 , y 0 ) → +∞. This is caused by the fact that if (x 0 , y 0 ) is close to that parabola, then at some moment t * the corresponding optimal trajectory gets to a point r(t * ) of the interval (C, E) and then goes along this interval up to the point C or A. Since the latter motion obeysẏ = ky, the time of motion along the interval [r(t * ), C] or [r(t * ), A] tends to infinity as r(t * ) tends to E.

The case k < 0
Denote k = −q, where q > 0. The boundary Γ of the admissible state domain is now defined by y = −qx−b, while the switching line S is the same as before. There are three qualitative different cases here, depending on the number of points where the line Γ and the curve S intersect: one, two, or three.

The case k < 0 with three intersection points
Introduce characteristic points for this case. Let C be the point where the line Γ is tangent to some parabola of the family x = 1 2 y 2 + const (clearly, this parabola is unique), F be the intersection point of Γ and S lying above the point C, and H be the intersection point of Γ and curve S lying below the point C (see. Fig. 4).
Let us find the coordinates of these points. The point F is defined by the relations x = 1 2 y 2 , y = −(qx + b), whence The point C is common to a parabola x = 1 2 y 2 +m and the line y = −(qx+b), which is tangent to this parabola at C, so dx/dy = y = −1/q . Hence, The point H will not play any role in our analysis, as well as First of all, consider some properties of admissible trajectories of the control system (1) valid in our case, and determine the set of admissible starting positions.
1) The points on the phase boundary lying below C are not reachable on the trajectories of our system. Indeed, here always y < −1/q, so (y + qx) • = u + qy < u − 1 0, i.e. the admissible velocities are directed inside the forbidden area, whence further movement from such points is impossible.
It is easily seen that any points of int Ω 5 are also inadmissible, because any motion from them gets us to the phase boundary below C, so the set D of admissible starting positions is the one bounded from below by the line Γ and parabola [C, C ′′ ). In other words, D = Ω 1 ∪ Ω 2 ∪ Ω 3 ∪ Ω 4 , and it is a closed set.
2) Observe that for the initial points lying in the regions Ω 1 and Ω 2 the optimal trajectories of the free problem, without the state constraint, satisfy this constraint, so they are optimal in the problem with this constraint as well. Thus, it remains to consider only the regions Ω 3 and Ω 4 .

3) According to
Step 1, the state boundary can be reached only at the points above or equal the point C, whereẋ = y < 0. If on some time interval we are on the boundary Γ, i.e. y(t) = −qx(t) − b, thenẏ(t) = −qẋ(t) > 0, so we move in "the left-up" direction, as long as the condition y < 0 holds. Clearly, it is enough to move only to the point F, because from it we can optimally get to the origin with the control u = +1. Since u = −q y, in view of the constraint |u| 1 this motion can happen only while y −1/q . The limit value y = −1/q corresponds to the point C. Thus, the motion along the state boundary is possible only within the segment [C, F ].

Analysis of MP for the case k < 0 with three intersection points
Let (x(t), y(t), u(t)), t ∈ [0, T ], be an optimal process starting at a point (x(0), y(0)) ∈ Ω 3 ∪ Ω 4 not lying on Γ (see Fig. 4). Then it satisfies the maximum principle (6)-(9). We now pass to its analysis. Partially, it will be similar to that in the case k > 0.
Thus, a jump of measure is possible only at the point C.
Lemma 3 is still valid in this case, while Lemmas 4 and 5 transform into the following ones.

Lemma 8
If on some open interval (t 1 , t 2 ) we are on Γ, then ψ = 0 and the measure has a densityμ 0 which is an exponential function. Moreover, ∆µ(t 2 ) = 0, both ψ and ϕ are continuous at t 2 , so they may have jumps only at t 1 .
Lemma 9 If the initial point does not lie on the parabola (C, C ′′ ), the following case is impossible: t 1 < t 2 , r(t 1 ) ∈ Γ, we are outside of Γ for t < t 1 and t > t 2 , both ψ and ϕ are continuous at t 2 and vanish on (t 1 , t 2 ).
Proof. In this case ϕ(t 2 ) = ψ(t 2 ) = 0 withφ = 0 andψ = −ϕ on [t 2 , T ], so we obtain ϕ = ψ = 0 there, hence also on [t 1 , T ). Let us now see what is on the left of t 1 . If ∆µ(t 1 ) = 0, then ψ = ϕ = 0 there, hence on the whole [0, T ], which is the trivial collection of multipliers. Therefore, ∆µ(t 1 ) > 0, whence ∆ϕ(t 1 ) < 0, ∆ψ(t 2 ) < 0, andψ = −ϕ < 0 for t > t 2 , so ψ > 0 and u = +1 for all t < t 1 . By Lemma 7, r(t 1 ) = C so the initial point lies on the parabola (C, C ′′ ) on the right of C, which is excluded from consideration. 6) Consider the set M of contact points with the state boundary. If it is empty, we have the motion along the parabolas of the above two families, which is possible only for the regions Ω 1 and Ω 2 . We then assume that M is nonempty. Denote t 1 = min M, t 2 = max M. The following lemma is similar to Lemma 6, but refers to another situation, depicted in Fig. 4.
Lemma 10 If the initial point does not lie on the parabola (C, C ′′ ) on the right of C, the set M is connected, i.e. it is a closed interval or a point: The proof in fact repeats that of Lemma 6 with corresponding alterations: the points t 1 and t 2 change their roles, so do the intervals [0, t 1 ] and [t 2 , T ]. We live the details to the interested reader.
Like before, consider all possible cases of location of the set M.
8) Can we have M = {t * } (touching the boundary at a single point) with r(t * ) < F ? If ∆µ(t * ) = 0, thenμ ≡ 0, so the motion is the same as in the free problem, i.e. along the parabolas. But since r(t * ) < F, this motion has u = −1 in a neighborhood of r(t * ), and we penetrate the boundary. Therefore, ∆µ(t * ) > 0, which is possible only if r(t * ) = C.
In this case, the function ψ is linear on the right of t * (and also on the left, with another slope), and since by Lemma 7 ψ(t * + 0) 0, we get either ψ > 0 on the right of t * and then u = +1, or ψ changes its sign there from plus to minus and then u = (+1, −1). It is easily seen that in both of these cases we cannot get to the origin from the point C, so they are impossible.
Thus, the set M can consist of a single point only if this point is F, and by Lemma 7 the measure has no jump here. Then we have a trajectory of the free problem just occasionally touching the state boundary. 9) Can we have M = [t 1 , t 2 ] with t 1 < t 2 and r(t 1 ) > C ? In this case there are no jumps of the measure anywhere, and by Lemma 8 ψ = 0 on M, so ϕ = −μ 0 is an exponential function. If ϕ = 0 on M, then ϕ = ψ = 0 everywhere, which is forbidden. On the right of t 2 we have ϕ = const < 0, thenψ = −ϕ > 0, hence ψ > 0, u = 1 without switching, and then we can get to the origin only if r(t 2 ) = F. Thus, the boundary arc of the trajectory always ends at F.
For t > t 2 the measure switches off and we haveψ = −ϕ > 0, so ψ > 0, and we move with u = +1 along the arc F O until the end.
If ∆µ(t 1 ) > 0, then ∆ψ(t 1 ) < 0 and ψ(t 1 − 0) > 0. In this case, either ψ > 0 everywhere on (0, t 1 ], or ψ changes its sign from minus to plus. The first case corresponds to the trajectories starting from the parabola (C, C ′′ ) that we excluded for now, while the second case to the trajectories of the type N ′ N CF O starting from a point N ′ in the region Ω 4 and moving with the control u = −1 along the parabola (N ′ , N ] until the point N ∈ (C, C ′′ ), then moving with the control u = +1 along the parabola [C, C ′′ ) to the point C, then moving on M = [t 1 , t 2 ] along the state boundary Γ to the point F, and finally with the control u = +1 along the curve S to the origin. In this second case, the value of ∆µ(t 1 ) can be uniquely determined, for any normalization of the pair (ϕ, ψ), by the motion time ∆t from the point N to the the point C under the control u = +1. Choosing the normalizationψ = −ϕ = 1 on [0, t 1 ], we have ψ(t N ) = 0, so ψ(t C − 0) = ∆t, whence ∆µ(t C ) = −∆ψ(t C ) = ∆t.
Thus, for any starting position in D not lying on the parabola (C, C ′′ ), there is a unique trajectory satisfying the MP, so it is optimal. 11) Finally, consider the case of "boundary" trajectories, that start from the points N of parabola (C, C ′′ ) on the right of the point C. Any such trajectory can be considered as a tail of a trajectory N ′ N CF O of the above type. Since the latter trajectory is optimal, its tail N CF O is also optimal.
Remark 2. Note the following interesting fact concerning the above trajectory N CF O. Consider any pair (ψ, ϕ) of costate multipliers with ∆µ(t 1 ) = 1, satisfying the last inequalities. If ϕ 1 < q, then ϕ < 0 on (t 1 , t 2 ] and still on (t 2 , T ], which yields ψ > 0 on (t 2 , T ], so u = +1 is determined uniquely from the maximum principle. However, if ϕ 1 = q, then ψ = 1 + q(t 1 − t) on [0, t 1 ], and further ϕ = ψ = 0 on (t 1 , T ]. In this case u ∈ [−1, 1] can be arbitrary on (t 1 , T ], with the only requirement that it steers the point C to the origin. Thus, the multipliers with ϕ 1 = q do not select a unique trajectory satisfying the MP. In particular, these trajectories may not pass along the boundary interval (C, F ]. Probably, this peculiar fact is related to that these trajectories start from the boundary of admissible set D. Obviously, among these trajectories only N CF O is optimal, because it is a tail of a unique optimal trajectory starting from a point N ′ ∈ Ω 4 . This degeneracy phenomenon deserves more thorough study in a general setting of problem with state constraints. Thus, the case k < 0 with three intersection points is completely considered, and we proved the following Theorem 4 The optimal synthesis is as follows (see Fig. 4). In the sets Ω 1 and Ω 2 it is the same as in the free problem, i.e. the optimal trajectory goes either with the control u = (−1, +1) or with the control u = (+1, −1). This case is the limit of the previous case with three intersection points, when the boundary segment [C, E] narrows to the single point C. Here the set W 1 is the limit of the set Ω 1 (in some natural sense which we do not formalize here), the set W 2 is the limit of the set Ω 2 ∩ Ω 3 , the set W 3 is the limit of the set Ω 4 , and the set W 4 is the limit of the set Ω 5 .

Fig. 5
The points on the state boundary that lie below C are unreachable on trajectories of our system. Any points from int W 4 are also unreachable, because any motion from them leads to points of the state boundary that lie below C. Thus, the set of admissible starting points in this case is D = For the starting points in D, the optimal trajectories of the free problem satisfy everywhere the state constraint, so they remain optimal in the problem with this constraint as well. Thus, the optimal synthesis in this case is "the cutting" of the free synthesis along the line composed of the state boundary Γ and the parabola [C, C ′′ ).
Since ∆ψ(t C ) = −∆µ(t C ), we obtain a unique pair with ϕ(0) = q/(1 + q t C ). Then any admissible trajectory with u = 1 until t C and arbitrary after t C satisfies the MP with these costate multipliers.

The case k < 0 with one intersection point
Here, important is the point C where Γ is tangent to some parabola of the family x = 1 2 y 2 + const (see Fig. 6). Clearly, this parabola is unique. Define the following closed sets: Q 1 bounded by the line Γ, the curve S, and the parabola [C, C ′ ), Q 2 lying to the right and above the line Γ and curve S, and Q 3 lying between the line Γ and parabola [C, C ′ ).
In this case, like before, the points lying on the state boundary below C, as well as points from int Q 3 , are not reachable for the trajectories of our system. Thus, the set of admissible starting points is D = Q 1 ∪ Q 2 .
For the starting points in D the optimal trajectories of the free problem satisfy everywhere the state constraint, so they remain optimal in the problem with this constraint as well.
Thus, the synthesis in this case is "the cutting" of the free synthesis along the line composed by the state boundary Γ and the arc of parabola [C, C ′′ ).
Note that in both three subcases for k < 0, the admissible set D is closed and the Bellman function is continuous.
Note that, if ∆µ < 1, the pair (ψ, ϕ) selects the above trajectory C ′′ CV O only. Otherwise, if ∆µ = 1, then ψ > 0 for t < t C and ψ = ϕ = 0 for all t > t C . The pair (ψ, ϕ) then selects not the given trajectory only, but any admissible one with u = 1 until t C and arbitrary u after t C .

The Limit Cases
Consider also the cases when the state boundary Γ is horizontal or vertical. If k = 0, the state constraint is Here, the admissible set D is the whole half-plane y −b, and the analysis of maximum principle is much simpler than that in the case k = 0. By arguments similar to the above ones, it can be easily shown that the contact set M is still either a singleton or a segment.
The optimal synthesis is the "cutting" of the free synthesis by the state boundary Γ (see Fig. 7): if a trajectory gets to this line from the domain lying on the right of the switching line S, the control switches from u = −1 to u = 0 and we move along the line Γ up to the point A = Γ ∩ S, where the control switches to u = +1 and we come to the origin.
How this synthesis relates to the synthesis for k > 0, shown in Fig. 3 ? If k → 0+, the point A tends to ( 1 2 b 2 , −b), the point C = C(k) moves in the left direction (so that x C → −∞) and disappears in the limit. The point E moves to the right along the x− axis, and also disappears in the limit. Therefore, the admissible set D = D(k) transforms in the limit into the half-plane y −b, and the optimal synthesis for k > 0 transforms into that for k = 0. We do not give here formal definitions of these limit passages, since their meaning is clear and do not cause any misunderstandings.
Let us consider what happens if k → 0 − . The synthesis for small k < 0 is shown in Fig. 4. If k → 0−, the point F tends to ( 1 2 b 2 , −b), the tangency point C = C(k), similar to above, moves in the right direction (so that x C → +∞) and disappears in the limit. Along with this, the inadmissible domain int Ω 5 (k) moves in the right direction and also disappears in the limit. One can easily see that here the optimal synthesis for k < 0 transforms into that for k = 0.

The Vertical State Boundary x p
Consider first the case when the state boundary is vertical and lies on the right of the origin. This case is a limit one for k → +∞ : rewriting (3) as y k x − b k and fixing the parameter p = b/k > 0, we obtain, in the limit, the state constraint x p .
Here, the Pontryagin function and the extended Pontryagin function take the form, respectively: so that the costate equations now arė Let us show that here the contact set M with the state boundary can consist only of the point C = (p, 0), i.e. the tangency point of the state boundary and the parabola x = p − 1 2 y 2 generated by the control u = −1 (see Fig. 8).
Indeed, let at a moment t ′ we are on Γ with y(t ′ ) = 0. If y(t ′ ) > 0, then by the system (1) we haveẋ = y > 0 in a neighborhood of t ′ , whence x > p in its right semi-neighborhood, i.e. we penetrate the state boundary. This also implies that all the points lying above the parabola CC ′ and on the left of the line Γ are not admissible.
If otherwise y(t ′ ) < 0 for some t ′ > 0, then by the system (1) we havė x = y < 0 in a neighborhood of t ′ , whence x > p in its left semi-neighborhood, so we came to this point from the forbidden zone.
Thus, we can get to the boundary Γ for some t ′ > 0 only at the point C, and the only way to get to this point is the motion along the tangential parabola C ′ CB with control u = −1. In this case, the optimal trajectory of the free problem, without state constraint, is still admissible in problem with this constraint, and so, it is still optimal there.
It follows from these considerations that the admissible set D := D(+∞) in this case is bounded from the right by the vertical ray x = p, y 0 and the arc of parabola CC ′ , i.e. D(+∞) = Ω 1 in Fig. 8. (This figure is the limit of Fig. 1 with the set Ω 2 reduced to the arc C ′ C belonging to Ω 1 .) On this set, the optimal synthesis coincides with that for the free problem.
However, of interest is the question about possible jump of the measure ∆µ(t C ) = δ for a trajectory C ′ CBO, starting from a point C ′ = (x 0 , y 0 ) on the arc C ′ C and having the control u = (−1, −1, +1). Obviously, y 0 = t C .
Remark 5. The costate pair (ψ, ϕ) where δ = 1/t C , ϕ = −1/t C on [0, t C ] and ϕ = 0 on [t C , T ] with the corresponding ψ = (t − 1)/t C on [0, t C ] and ψ = 0 on [t C , T ] selects not the only trajectory C ′ CBO. One can easily see that any admissible trajectory passing along the parabola C ′ C on [0, t C ] with u = −1 and being arbitrary for t > t C satisfies the maximum principle. However, among these trajectories only the above C ′ CBO is optimal, because it is the only optimal one in the free problem starting from the point C ′ .
How the obtained synthesis relates to that in the case k >> 0, the latter being shown in Fig. 1 ? If k → +∞ with p = b/k = const , the point C con-verges in the limit to the point E = (p, 0). Therefore, the set Ω 2 (k) restricted by the parabolas CC ′ , EE ′ , and the line Γ = Γ (k), transforms into the arc of parabola CC ′ , and the admissible set D = D(k) transforms into the set D(+∞). Thus, the optimal synthesis for k > 0 transforms into the optimal synthesis for k = +∞.

The Vertical State Boundary x −p
Consider now the case when k → −∞ preserving the value b/k = −p = const < 0. By analogy with the above, passing to the limit, we get the state constraint x −p (p > 0). This limit case is symmetrical to the case x p with respect to the origin; the corresponding optimal trajectories are shown in Fig. 9. Here the admissible set D = D(−∞) is bounded from the left by the vertical ray x = −p, y 0 and the arc of parabola CC ′′ , i.e. D(−∞) = Q 1 ∪ Q 2 in Fig. 9. (The set Q 3 is inadmissible.) Let us consider how this synthesis relates to that for k << 0, shown in Fig. 6. As k → −∞, the touching point C = C(k) converges to (−p, 0), the interlocation of the sets Q 1 , Q 2 , Q 3 remains the same in the limit, and the admissible set D(k) transforms continuously into the above set D(−∞) in Fig. 9. Therefore, the optimal synthesis for k << 0 transforms into that for k = −∞.
Note that though the pictures of syntheses for k = −∞ and k = +∞ are symmetric, the prelimit syntheses converge to them in a slightly different ways: in the case k → −∞, the structure of admissible starting positions, shown in Fig. 6, stays invariable, whereas for k → +∞, the region Ω 2 (k) in Fig. 1, restricted by the parabolas CC ′ , EE ′ , and the line Γ = Γ (k), disappears in the limit, resulting just in the arc CC ′ of tangential parabola in Fig. 8.

Conclusion
We constructed a complete picture of synthesis for the given problem and analyzed its evolution under the change of parameter k of the slope of state boundary within the limits −∞ < k < ∞. It would be interesting to find the synthesis for the following 3D-problem with all possible values of a, b, c: x = y,ẏ = z,ż = u, ax + by + cz −d (d > 0), |u| 1, (x 0 , y 0 , z 0 ) → (0, 0, 0), T → min .