MATHEMATICS

A. Ya. DUBOVITSKII, A. A. MILYUTIN

SECOND VARIATIONS IN EXTREMUM PROBLEMS WITH CONSTRAINTS

(Presented by Academician L. S. Pontryagin on 22 VI 1964)

In \((^1)\) a general method was proposed for analyzing extremum problems in the presence of constraints in the linear approximation. In the present work we supplement it with a theory for the investigation of the same problems in approximations of higher order. A principal feature of the proposed method is that in it each constraint and the functional to be minimized are analyzed independently of one another. All essential connections are taken into account by the Euler equation obtained as a result of the analysis. As an illustration, a sufficient condition for a minimum in a constrained extremum problem is established and the well-known problem of V. A. Markov \((^2)\) on the maximum of the norm of the \(k\)-th derivative of a polynomial is solved.

\(1^\circ\). Statement of the problem. In a Banach space \(U\), find \(\min F(u)\) under the condition \(u \in Q_1, \ldots, u \in Q_n\) and \(u \in \mathcal L\). The sets \(Q_1, \ldots, Q_n\) are called constraints of inequality type, and \(\mathcal L\) a constraint of equality type. With respect to \(F\), \(Q_i\), and \(\mathcal L\), assumptions \(2^\circ\), A, B, C, as well as \(3^\circ\), A′, B′, C′, are assumed to hold.

\(2^\circ\). Analysis of problem \(1^\circ\) in the linear approximation. Let \(u_0 \in U\). A variation \(\bar u\) is admissible for \(Q_i\) if \(u_0+\varepsilon(\bar u+y)\in Q_i\) for all sufficiently small \(\varepsilon>0\) and \(y\). The cone \(\Omega_i\) of such \(\bar u\) is open. A variation \(\bar u\) is admissible for \(\mathcal L\) if

\[ \rho(\mathcal L, u_0+\varepsilon \bar u)=o(\varepsilon). \]

Such \(\bar u\) form a cone \(L\). Finally, \(\Omega\) is the cone of forbidden variations \(\bar u\): \(F(u_0+\varepsilon(\bar u+y))<F(u_0)\) for all sufficiently small \(\varepsilon>0\) and \(y\); \(\Omega\) is always open.

It is assumed that:

A. The cone \(\Omega\) is convex and nonempty.
B. All \(\Omega_i\) are convex and nonempty.
C. \(L\) is a subspace.

It is obvious that, in order that \(u_0\) give a minimum in problem \(1^\circ\), it is necessary that
\[ \Omega \cdot \Omega_1 \cdot \ldots \cdot \Omega_n \cdot L = \theta \]
(\(\theta\) is the empty set). According to \((^1)\), in order that the open convex cones \(\Omega, \Omega_i\) and the subspace \(L\) have empty intersection, it is necessary and sufficient that there exist linear functionals \(\omega, \omega_i\), and \(\lambda\), nonnegative respectively on \(\Omega, \Omega_i\), and \(L\), not all equal to zero, and such that

\[ \omega+\omega_1+\ldots+\omega_n+\lambda=0. \tag{1} \]

Solutions of the Euler equation (1) are called stationary points of the problem. The points of minimum are contained among them.

\(3^\circ\). Analysis of problem \(1^\circ\) by means of the second variation. We denote the order of approximation by \(\eta\), \(\eta=o(\varepsilon)\). Let \(u_0\) be a stationary point, and \(\bar u\) a fixed first variation. We introduce definitions.

The second variation \(\tilde u\) is admissible for \(Q_i\) if \(u_0+\varepsilon \bar u+\eta(\tilde u+y)\in Q_i\) for all sufficiently small \(\varepsilon>0\) and \(y\). The set \(\Omega_i'\) of such \(\tilde u\) is open. Let \(L'\) be the set of second variations \(\tilde u\) for which
\[ \rho(u_0+\varepsilon \bar u+\eta \tilde u,\mathcal L)=o(\eta). \]
Denote by \(\Omega'\) the set of forbidden \(\tilde u\):
\[ F(u^0+\varepsilon \bar u+\eta(\tilde u+y))<F(u_0) \]
for all sufficiently small \(\varepsilon>0\) and \(y\).

We shall consider only problems for which:

A′. The set \(\Omega'\) is convex and nonempty (\(\Omega'\) is always open!).
B′. All \(\Omega_i'\) are convex and nonempty.
C′. \(L'\) is a nonempty hyperplane (a translated subspace).

Variations \(\bar u\) for which, for some \(\eta=o(\varepsilon)\), A′, B′, and C′ are satisfied are called critical. The totality of critical directions can be represented in the form \(Z \cup L\cdot \overline{\Omega}\cdot \Omega_1\cdots \Omega_n\), where \(Z \subset L\).

In problems with convex \(F\) and \(Q_i\), \(Z=\theta\).

As in 2°, in order that \(u_0\) give a minimum in problem 1°, it is necessary that

\[ \Omega'\cdot \Omega_1'\cdots \Omega_n'\cdot L'=\theta . \tag{2} \]

To make this condition meaningful, it must be formulated in terms of the adjoint space.

The solution is analogous to condition (1) of item 2°. Namely, let \(\Omega'\), \(\Omega_1'\), \(\ldots\), \(\Omega_n'\) be open nonempty convex sets, and let \(L'\) be a hyperplane. In order that \(\Omega'\cdot \Omega_1'\cdots \Omega_n'\cdot L'=\theta\), it is necessary and sufficient that there exist linear functions \(\omega,\omega_1,\ldots,\omega_n\) and \(\lambda\), nonnegative respectively on \(\Omega'\), \(\Omega_1'\), \(\ldots\), \(\Omega_n'\), and \(L'\), not all equal to zero, and such that

\[ \omega+\omega_1+\cdots+\omega_n+\lambda=0 . \tag{3} \]

We call (3) the Euler equation for the second problem 1°. Its solutions are the stationary points of problem 1° in the approximation \(\eta\). The derivation of the Euler equations for the following approximations is entirely analogous. In items 4° and 5° \(\eta=\varepsilon^2\).

4°. Minimum conditions for a problem with conditional extremum (³). Find \(\min f(x)\), if \(\varphi_1(x)=\cdots=\varphi_s(x)=0\).

The Euler equation for the first variation is

\[ f_x'(x)+\lambda_1\varphi_{1x}'(x)+\cdots+\lambda_s\varphi_{sx}'(x)=0 . \tag{4} \]

(It is assumed that \(\varphi_{ix}'(x)\) are linearly independent and \(f_x'(x)\) is nonzero.)

Let \(x_0\) be a stationary point. A critical direction \(\bar x\) satisfies the conditions \(\bar x\perp \varphi_{ix}'(x)\). According to (4), \(f_x'(x_0)\perp \bar x\).

Investigation of problem 4° by means of the second variation. The set \(\Omega'\) of forbidden \(\widetilde x\) is characterized by the condition

\[ f_{xx}''(x_0)\bar x\cdot \bar x+2f_x'(x_0)\cdot \widetilde x<0 . \]

\(\Omega'\) is convex, open, and nonempty. The linear functions nonnegative on \(\Omega'\) have the form
\(-a\bigl(f_{xx}''(x_0)\bar x\cdot \bar x+2f_x'(x_0)\cdot \widetilde x\bigr)+b\), where \(a\geq 0,\ b\geq 0\).

The hyperplane \(L'\) of variations \(\widetilde x\) admissible with respect to the constraint \(\varphi_i(x)=0\) is:
\[ \varphi_{ixx}''(x_0)\bar x\cdot \bar x+2\varphi_{ix}'(x_0)\cdot \widetilde x=0 . \]

The linear functions nonnegative on \(L'\) have the form

\[ \sum_i c_i\bigl(\varphi_{ixx}''(x_0)\bar x\cdot \bar x+2\varphi_{ix}'(x_0)\widetilde x\bigr)+d_i,\qquad d_i\geq 0 . \]

According to (3) and (4),

\[ A\bar x\cdot \bar x= \bigl(f_{ixx}''(x_0)-\sum \lambda_i\varphi_{ixx}''(x_0)\bigr)\bar x\cdot \bar x\geq 0, \tag{5} \]

where \(\lambda_i\) are the same as in (4).

5°. The problem of V. A. Markov. In the space \(P\) of polynomials of degree \(n\), defined on the interval \(-1\leq x\leq +1\), find the maximum of the functional
\[ F(p)=\|p^{(k)}\|=\max_{-1\leq x\leq +1}|p^{(k)}(x)|, \]
if \(\|p\|\leq 1\). Here \(k\) is a certain integer, \(0<k\leq n\), and \(p^{(k)}(x)\) is the \(k\)-th derivative of the polynomial \(p(x)\).

As a result of analyzing the Euler equations for the first and second variations, we shall show that the optimal polynomial \(p_0(x)\) of problem \(5^0\) is uniquely determined and is the Chebyshev polynomial \(H_n(x)=\cos n\arccos x\). This proof appears to be new.

Let \(p_0(x)\) be a solution of problem \(5^0\). By \(M\) denote the set of points where \(|p_0(x)|=1\), and by \(c\) the point where \(|p_0^{(k)}(c)|=\|p_0^{(k)}\|\) (\(M\) and \(c\in[-1,1]\)).

Investigation of problem \(5^0\) by means of the first variation. Variation. The cone \(\Omega\) of forbidden \(\bar p\) satisfies the condition
\[ \bar p^{(k)}(c)/p_0^{(k)}(c)>0. \]
\(\Omega\) is a nonempty, convex, open cone. Linear functionals nonnegative on \(\Omega\) have the form
\[ \alpha \bar p^{(k)}(c)/p_0^{(k)}(c), \]
where \(\alpha\ge 0\).

The cone \(\Omega_1\) of variations \(\bar p\) admissible under the restriction \(\|p\|\le 1\) is determined by the inequality
\[ \bar p(x)/p_0(x)<0,\quad x\in M. \]
\(\Omega_1\) is also an open, convex, and nonempty cone. Linear functionals nonnegative on it have the form
\[ -\int \frac{\bar p(x)}{p_0(x)}\,d\mu, \]
where \(\mu\) is a nonnegative measure concentrated on \(M\).

Euler equation for the first variation. According to (1) we have
\[ \frac{\bar p^{(k)}(c)}{p_0^{(k)}(c)} = \int \frac{\bar p(x)}{p_0(x)}\,d\mu, \tag{6} \]
an equality valid for arbitrary \(\bar p\).

It is clear from (6) that \(M\) contains either \(n\) or \(n+1\) points. If \(M\) contains \(n+1\) points, then, as is known,
\[ p_0(x)=\cos n\arccos x. \]
The rest is devoted to proving the contradiction of the assumption that \(M\) contains \(n\) points.

Let
\[ M=\{x_1,\ldots,x_n\}. \tag{7} \]

Investigation of equation (6). Consider the polynomial
\[ Q(x)=(x-x_1)\cdots(x-x_n). \]
By virtue of (6), \(Q^{(k)}(c)=0\). Consequently, \(c\) is an interior point of \([-1,1]\). Hence,
\[ p_0^{(k+1)}(c)=0. \]
It is known that if the roots of polynomials interlace, then the roots of their derivatives also possess the same property. It follows that all
\[ Q_i^{(k)}(c),\quad Q_i=Q/(x-x_i), \]
have one and the same sign.

By virtue of (6),
\[ \frac{Q_i^{(k)}(c)}{p_0^{(k)}(c)} = \frac{Q_i(x_i)}{p_0(x_i)}\,\mu_i. \tag{8} \]

It follows from (8) that \(p_0(x)\) has different signs at neighboring points of \(M\). Consequently, \([-1,1]\) contains \(n-1\) roots of \(p_0(x)\). Without loss of generality one may assume that \(-1\in M\) and that to the left of the point \(-1\) there are no roots of \(p_0(x)\). By \(\beta\) denote the rightmost root of \(p_0'(x)\). If \(\beta\le 1\), then \(p_0(x)\) is obtained by stretching \(H_n(x)\). Therefore, for the optimal polynomial \(p_0(x)\) one has \(\beta>1\). Consequently, \(1\) is also contained in \(M\).

It is easy to show that polynomials \(p_\beta(x)\) of the indicated type exist for all \(\beta\ge 1\), and
\[ p_\infty(x)=-H_{n-1}(x). \]

To complete the proof of the contradiction of (7), we investigate the Euler equation for the second variation of problem \(5^0\).

Euler equation for the second variations. Let us find the critical directions \(\bar p(x)\). The sets
\[ \bar p^{(k)}(c)/p_0^{(k)}(c)\ge 0 \quad\text{and}\quad \max_{x\in M}\frac{\bar p(x)}{p_0(x)}\le 0 \]
are convex; therefore the critical variations lie on the boundary of each of them. Consequently,
\[ \bar p^{(k)}(c)/p_0^{(k)}(c)=0. \]

By virtue of (6), \(\bar p(x)=0\) for all \(x\in M\). Thus, there exists a unique critical variation
\[ \bar p(x)=\gamma Q(x). \]

Variation. The forbidden variations \(\tilde p(x)\) form the set \(\Omega'\)

\[ \frac{\tilde p^{(k)}(c)}{p_0^{(k)}(c)} - \frac{Q^{(k+1)2}(c)}{p_0^{(k)}(c)\,p_0^{(k+2)}(c)} >0; \]

\(\Omega'\) is convex, open, and nonempty.

The variations \(\tilde p\) admissible under the constraint \(\|p\|<1\) form the set \(\Omega_1'\):

\[ -\left( \frac{\tilde p(x_i)}{p_0(x_i)} - \frac{Q'^2(x_i)}{p_0(x_i)\,p_0''(x_i)} \right)>0,\qquad x_i\in(-1,1)\cdot M; \]

\[ -\frac{\tilde p(-1)}{p_0(-1)}>0,\qquad -\frac{\tilde p(1)}{p_0(1)}>0. \]

By virtue of (3), the Euler equation for the second variation is

\[ \frac{\tilde p^{(k)}(c)}{p_0^{(k)}(c)} - \frac{Q^{(k+1)2}(c)}{p_0^{(k)}(c)\,p_0^{(k+2)}(c)} +\delta = \int \frac{\tilde p(x)}{p_0(x)}\,d\nu - \int \frac{Q''^2(x)}{p_0(x)\,p_0''(x)}\,d\nu_{\mathrm{vn}}, \tag{9} \]

where \(\nu\ge 0\) is a measure concentrated on \(M\), and \(\nu_{\mathrm{vn}}\) is a nonnegative measure concentrated on \((-1,1)\cdot M\) and coinciding there with \(\nu\). By the arbitrariness of \(\tilde p\), the measure \(\nu\) coincides with the measure \(\mu\) from equation (6). The new information, as compared with equation (6), consists in the condition

\[ -\frac{Q^{(k+1)2}(c)}{p_0^{(k)}(c)\,p_0^{(k+2)}(c)} - \int \frac{Q''^2(x)}{p_0(x)\,p_0''(x)}\,d\mu_{\mathrm{vn}}\ge 0. \tag{10} \]

We shall show that (10) is impossible. Since \(Q(x)(x-\beta)=p_0'(x)(x^2-1)\), using \(Q^{(k)}(c)=p_0^{(k+1)}(c)=0\) and the identity (6), we reduce (10) to the form

\[ \frac{1}{Q^{(k+1)}(c)} \left[ \left( \frac{Q'(\beta)Q(x)-Q(\beta)Q'(x)}{x-\beta} \right)^{(k-1)} \right]_{x=c} + \frac{k(k+1)p_0^{(k)}(c)Q(\beta)} {(c-\beta)p_0^{(k+2)}(c)(\beta^2-1)} \le 0. \tag{11} \]

The last term in (11) is positive. The required contradiction will be obtained if we show that the first term in (11) is also positive.

Indeed, the roots of the polynomials

\[ \Delta(x)=\frac{Q'(\beta)Q(x)-Q(\beta)Q'(x)}{x-\beta} \]

and \(Q(x)\), as well as the roots of \(\Delta(x)\) and \(Q'(x)\), interlace, and between every root of \(Q'(x)\) and the nearest root of \(Q(x)\) on the left there lies a root of \(\Delta(x)\). Consequently, the polynomials \(\Delta^{(k-1)}(x)\), \(Q^{(k)}(x)\), and \(Q^{(k-1)}(x)\) possess the same property; hence the required contradiction follows, since all three polynomials are positive at \(x=\infty\).

Institute of Chemical Physics
Academy of Sciences of the USSR

Received
22 VI 1964

CITED LITERATURE

1. A. Ya. Dubovitskii, A. A. Milyutin, DAN, 149, No. 4 (1963).
2. S. N. Bernstein, Collected Works, 2, Publishing House of the Academy of Sciences of the USSR, 1954, p. 281.
3. G. M. Fikhtengol’ts, Course of Differential and Integral Calculus, 1, 1958, p. 472.