UDC 51:330.115

MATHEMATICS

V. L. MAKAROV

A CHARACTERIZATION OF SOLUTIONS OF THE PROBLEM OF CONTINUOUS LINEAR AND CONVEX PROGRAMMING

(Presented by Academician L. V. Kantorovich, 22 XII 1966)

Problems of continuous linear and convex programming arise in considering economic models in continuous time. The problem of continuous linear programming (c.l.p.) was first systematically considered by Bellman. In his terminology this is the “bottleneck” problem (see \((^1)\), Chs. VI–VII). The duality theorem formulated by Bellman for the class of problems he considered was proved, under a number of additional assumptions, by Tyndall \((^2)\), who already used the term c.l.p. Here we establish a substantially more general duality theorem, of a somewhat different nature, and also a theorem on the finite number of switchings of an optimal plan.

1. Formulation of the problem of convex continuous programming. Given are an \(n\)-dimensional nonnegative vector \(x_0\) (the initial state), a number \(T > 0\) (the length of the planning period), a family of closed convex cones \(\{Z_t\}\), \(t \in [0,T]\), lying in the nonnegative orthant of \(2n\)-dimensional Euclidean space (technology), and a nonnegative \(n\)-dimensional vector \(c\) (the vector of values). It is required to find an \(n\)-dimensional vector-function \(\bar z\), summable on \([0,T]\), which maximizes the expression \(cx(T)\), where the maximum is taken over all vector-functions \(z\) summable on \([0,T]\) and satisfying the constraints:

\[ 1)\quad x(t)=x_0+\int_0^t z(\tau)\,d\tau \quad \text{for all } t\in[0,T]; \]

\[ 2)\quad z(\tau)=y(\tau)-x(\tau), \quad (x(\tau),y(\tau))\in Z_\tau \quad \text{for all } \tau\in[0,T]. \]

A summable vector-function \(z\) satisfying relations 1) and 2) is called an admissible control on \([0,T]\) for \(x_0\). We shall say that a control \(z\), admissible for \(x(t_1)\), transfers the point \(x(t_1)\) to the point \(x(t_2)\) if

\[ x(t_2)=x(t_1)+\int_{t_1}^{t_2} z(t)\,dt \quad \text{and} \quad z(t)=y(t)-x(t), \]

\[ (x(t),y(t))\in Z_t \quad \text{for all } t\in[t_1,t_2], \quad \text{where} \quad x(t)=x(t_1)+\int_{t_1}^{t} z(\tau)\,d\tau. \]

Theorem 1 (on the characterization of an optimal control). Suppose there is a problem of continuous convex programming, and suppose the technology \(\{Z_t\}\) satisfies the following additional restrictions: a) there exists a constant \(K>0\) such that

\[ \max_{t\in[0,T]}\ \max_{(x,y)\in Z_t}\ \sum_i y_i \bigg/ \sum_i x_i \le K; \]

b) for any \(t\in[0,T]\) and \(i,\ i=1,2,\ldots,n\), there exists an \(n\)-dimensional vector \(y\) such that \((e_i,y)\in Z_t\), where \(e_i\) is the unit vector corresponding to the \(i\)-th coordinate axis.

Then there exists an optimal control. Moreover, in order for a control \(z\), admissible on \([0,T]\) for \(x_0\), to be optimal, it is necessary and sufficient that there exist an \(n\)-dimensional vector function \(\pi\), defined on \([0,T]\), having the following properties: 1) \(\pi(T)=c\); 2) \(x(t)\pi(t)\geq x(T)c\) for any \(t\in[0,T]\), any state \(x(t)\), and any control \(z\) admissible for \(x(t)\), carrying the point \(x(t)\) into the point \(x(T)\); 3) \(\bar x(t)\pi(t)=\bar x(T)c\) for all \(t\in[0,T]\), where \(\bar x\) is the trajectory corresponding to the control \(\bar z\).

This theorem can be rewritten in the form of a duality theorem, if the dual problem is formulated as follows:

Find an \(n\)-dimensional vector function \(\pi\) delivering \(\min\) to the expression \(x_0\pi(0)\) subject to the constraints: 1) \(\pi(T)=c\); 2) \(x(t)\pi(t)\geq x(T)c\) for any \(t\in[0,T]\), any state \(x(t)\), and any control \(z\) admissible for \(x(t)\), carrying the point \(x(t)\) into the point \(x(T)\).

2. The problem of continuous convex programming is transformed into a problem of c.l.p. if every cone \(Z_t,\ t\in[0,T]\), is polyhedral. In this item the case is considered when the technology does not depend on time, i.e., \(Z_t=Z\) for any \(t\in[0,T]\). The polyhedral cone \(Z\) is specified by its generators \((a^s,b^s)\in Z,\ s=1,2,\ldots,S\), which are usually called technological methods. The matrix \(\|a_i^s\|\) is denoted by \(A\), and the matrix \(\|b_i^s\|\) by \(B\). Then the c.l.p. problem will have the following form:

Find a summable on \([0,T]\) \(S\)-dimensional vector function \(u\) (an optimal plan), delivering \(\max\) to the expression \(u(T)Ac\) subject to the constraints:

\[ \text{1) }\quad x(t)=x_0+\int_0^t u(\tau)(B-A)\,d\tau;\qquad \text{2) }\quad u(t)A=x(t)\quad \text{for all } t\in[0,T]; \]

\[ \text{3) }\quad u(t)\geq 0\quad \text{for all } t\in[0,T]. \]

Thus, here the plan \(u(t)\) corresponds to the control \(z(t)=u(t)(B-A)\).

A plan \(u\) has a finite number of switches on \([0,T]\) if there are moments of time \(t_1,\ldots,t_r,\ 0=t_0<t_1<\cdots<t_r<t_{r+1}=T\), such that \(u\) on the interval \([t_k,t_{k+1}],\ k=0,\ldots,r\), is determined from the solution of the system of equations \(\dot u_{(k)}=u_{(k)}(B_kA_k^{-1}-I)\). Here \(A_k,\ B_k\) are \((n\times n)\)-matrices composed of rows of the matrices \(A\) and \(B\). Another case is also possible, which is not formulated precisely here, when \(A_k,\ B_k\) are square matrices of dimension less than \(n\), obtained by choosing the corresponding rows of the matrices \(A\) and \(B\) and replacing several components in a row by one component. The vector function \(u_{(k)}\) has a number of components corresponding to the dimension of the matrices \(A_k,\ B_k\), \(\dot u_{(k)}=du_{(k)}/dt\); the plan \(u\) on the interval \([t_k,t_{k+1}]\) is obtained from \(u_{(k)}\) in the following way: \(u^s=u_{(k)}^s\), if \((a^s,b^s)\) enters into the matrices \(A_k,\ B_k\), and \(u^s=0\) otherwise. \(I\) is the identity matrix.

Theorem 2. For any optimal plan \(\bar u\) of the c.l.p. problem with constant cone \(Z\), there is an admissible plan \(u\), having a finite number of switches, such that \(\bar u(T)A=u(T)A\).

It follows easily from Theorem 2 that the dual problem to the c.l.p. problem can be written as follows:

Find a summable on \([0,T]\) \(n\)-dimensional vector function \(\pi\), delivering \(\min\) to the expression \(\pi(0)x_0\) subject to the constraints: 1) \(\pi(T)=c\); 2)

\[ A\pi(t)\geq Ac+\int_t^T (B-A)\pi(\tau)\,d\tau \quad \text{for all } t\in[0,T]. \]

Remark. Theorems 1 and 2 extend to more general cases, in particular to models with “load.” However, the corresponding results are formulated more complicatedly than those described.

Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR

Received
21 XII 1966

CITED LITERATURE

1. R. Bellman, Dynamic Programming, Moscow, 1960.
2. W. F. Tyndall, J. Soc. Ind. and Appl. Math., 13, No. 3, 644 (1965).