Iterative Solution Methods for a Class of State and Control Constrained Optimal Control Problems ()
1. Sample Examples of the State and Control Constrained Optimal Control Problems
We give two sample examples of the elliptic optimal control problems. The corresponding existence theory, methods of the approximation and more examples can be found, e.g., in [1,2] (see also the bibliography therein).
Consider the homogeneous Dirichlet boundary value problem for Poisson equation which plays a role of the state problem in first sample example:
(1)
Above 
is a bounded domain with piecewise smooth boundary
, 
is the characteristic function of a subdomain
, 
is a fixed function, while 
is a variable control function. For all 
there exists a unique weak solution 
of the boundary value problem (1) from Sobolev space
. We impose the point-wise constraints for both state function 
and control function
:
(2)
with 
and 
Suppose that (1) and (2) are not contradictory in the sense that
(3)
Let the objective functional be defined by the equality
with a given function
. The optimal control problem
(4)
has a unique solution 
if assumption (3) is fulfilled.
In the second sample example we take as the state problem mixed boundary value problem for Poisson equation
(5)
and the objective functional of the form
Here 
is the unit vector of outward normal, 
and 
Let the constraints for 
and 
be
Suppose again that the set
is not empty. Then the optimal control problem
(6)
has a unique solution
.
2. Finite Element Approximation of the Optimal Control Problems
We briefly describe the approximation of the problems (4) and (6) by a finite element method (cf. [3]). Suppose that the domains
, 
and 
are polygons and construct a conforming triangulation of 
into triangle and/or rectangle finite elements
. Let the triangulation be consistent with the subdomains 
and 
and the partition of the boundary into the parts
, 
and 
in the following sense: every subdomain consists of the integer number of the elements 
and every part of the boundary consists of the integer number of the sides of
. Construct the finite element spaces which consist of the continuous functions, piecewise linear on the triangles (
-elements) and piecewise bilinear on the rectangles (
-elements), and satisfy Dirichlet boundary conditions. The integrals over domains and curves we approximate by the composed quadrature formulaes using the simplest 3-points quadrature formulaes for the triangle elements 
and 4-points formulaes for the rectangle elements
. Note, that such kind of the approximation of a 2nd order elliptic equation in the case of rectangular 
and rectangular elements 
coincides with a finite difference approximation of this equation.
We apply the described above approximation procedure for the sample optimal control problems and obtain the mesh optimal control problems which are the finite dimensional problems for the vectors of nodal values1 of the corresponding mesh functions. Namely, the approximations of the state problems (1) and (5) are the discrete state equations of the form
where 
is a positive definite stiffness matrix, 
is a diagonal mass matrix, and
is a rectangular matrix. The discrete objective function approximating 
or 
is a quadratical function
with a symmetric and positive definite matrix 
, symmetric and positive semidefinite matrix
, and given vector
. Finally, the sets of constraints for the vectors 
and 
are
Further we denote by 
and 
the indicator functions of the sets 
and
, respectively. Resulting mesh optimal control problem which approximates (4) or (6) can be written in the following form:
(7)
Below we list the main properties of the matrices and functions in problem (7) which are used for its theoretical investigation and proving the convergence of the corresponding iterative methods:
(8)
Minimization problem (7) with the matrices and the functions which satisfy assumptions (8) arise when approximating by finite difference method or by simplest finite element methods with quadrature formulaes the wide class of the optimal control problems which contain a linear boundary value problem as a state equation, control in the right-hand side of the equation or in the boundary conditions, and point-wise constraints for both state and control functions.
Introduce Lagrange function for problem (7):
Its saddle point 
satisfies the saddle point problem
(9)
where 
and 
are the subdifferentials of the corresponding functions.
Theorem 1 Let the assumptions (8) be valid and
Then problem (7) has a unique solution
. If more strict assumption
is fulfilled then saddle point problem (9) has a nonempty set of solutions
.
3. Transformations of the Primal Saddle Point Problem and Preconditioned Uzawa Method
Matrix 
which multiplies by the vector
in system (9) is only positive semidefinite. This prevents the usage of the dual iterative methods (such as Uzawa method) for solving (9). We transform this saddle point problem to an equivalent one with a positive definite matrix by using the last equation in system (9). Consider two equivalent to (9) saddle point problems:
(10)
(11)
Lemma 1 Matrices 
and
are positive definite for
where constants 
don’t depend on the dimension of the finite element space (or, on the mesh step).
Now, we can apply the preconditioned Uzawa methods for solving problem (10) and problem (11):
(12)
(13)
The choice of the preconditioners is based on the properties of the matrices in problems (10) and (11) (see the corresponding theory in [4]).
Lemma 2 The iterative methods (12) and (13) converge if
, where 
don’t depend on mesh step.
The implementation of every step of (12) includes solution of two systems of linear equations with matrices 
and 
and solution of two inclusions with multivalued operators 
and
. The matrices in the discrete model problems are diagonal while the functions are separable:
Due to these properties 
and 
are diagonal operators, and the solution of the inclusions with these operators reduce to an easy problem of the orthogonal projection on the corresponding sets 
and
.
The implementation of every step of (13) includes solution of the system of linear equations with matrix 
and solution of the inclusion with operator
, which corresponds to a mesh variational inequality of second order. This is more time consuming problem than solution of a linear system, but the numerical tests demonstrates the preference of method (13) in some particular cases. The methods of solving the variational inequalities can be found in the books [5-7].
4. Block SOR-Method for the Problem with Penalization of the State Equation
Let D be a symmetric and positive matrix while 
be a regularization parameter. Consider the following regularization of problem (7):
(14)
Theorem 2 Let the assumptions (8) be valid. Then problem (14) has a unique solution 
If 
is a solution of saddle point problem (9), then the following estimate holds:
(15)
with a constant 
independent on 
and on mesh size.
Problem (14) is equivalent to the following system of the inclusions:
(16)
with a positive definite and symmetric matrix. Different iterative methods can be used for solving problem (14) or equivalent problem (16) (see, e.g., [5,6] and the bibliography therein). We solve system (16) by block SORmethod:
(17)
where 
is a relaxation parameter and
Theorem 3 ([8]) Method (17) converges for any
.
The implementation of (17) depends on the choice of the matrix
. Below we consider two variants of the choice.
a) Let
. In this case the implementation of every iterative step of (17) consists of the solving the following system
(18)
with known
. For the model problems under consideration the operator 
of the first inclusion has diagonal form, so, its solution reduces the projection on the set
. Further, the matrix in the second inclusion is spectrally equivalent to matrix
:
Here 
is a constant in the stability estimate for a solution of the state equation and it is independent on mesh step. The stationary one-step iterative method with preconditioner 
converges with the rate of convergence proportional to 
(and doesn’t depend on mesh step), and its implementation reduces to the projection on the set
.
In the particular case when 
is the unit matrix (which corresponds to the distributed in the domain control) the second inclusion in (18) can be transformed to a system of nonlinear equations and an inclusion with diagonal operator. Namely, let
. Then the auxiliary vector 
is a solution of the system of nonlinear algebraic equations
with the symmetric and positive definite matrix
and monotone, diagonal and Lipshitz-continuous operator
.
b) In the case of a symmetric matrix 
and the unit matrix 
the promising choice is
. Then on every iterative step of (17) we solve the system
First inclusion of this system corresponds to a mesh approximation of a second order variational inequality, while the equation for vector 
contains the symmetric and positive matrix 
and monotone, diagonal and Lipshitz-continuous operator
.
5. Numerical Example
We solved the optimal control problem with the following state problem and constraints:
and the objective functional
where 
and
.
Finite difference approximation of this optimal control problem on the uniform grid leads to a minimization problem of the form (7) and the following saddle point problem (particular case of (9)):
Here symmetric and positive definite matrix 
corresponds to the mesh Laplacian with Dirichlet boundary conditions, 
is a diagonal and positive semidefinite matrix (its positive entries correspond to the grid points in the subdomain
).
To apply Uzawa method we used the equivalent transformation similar to (11) with parameter 
(satisfying the assumptions of theorem 1):
This system was solved by Uzawa method with preconditioner 
which is now spectrally equivalent to
.
We also solved the mesh optimal control problem by applying SOR-method to the problem with penalized state equation and the choice
. Corresponding system for
, 
and auxiliary vector 
reads as:
We used block SOR-method with relaxation parameter 
(found numerically to be close to optimal one). We also used the iterative regularization as follows: calculate the residual vector 
on the current iteration 
and set 
when 
becomes less than 1.
Here the norm 
is the mesh analogue of the Lesbegue space norm
. The smallest value 
was reached started from
.
In the tables below (Tables 1 and 2) 
is the number of an iteration, 
is the value of the objective function on the current iteration, 
and
, the calculation results for the 
are presented. We constructed the exact solution 
of the discrete optimal control problem, so, we knew the exact minimum of the cost function
.
We can conclude that block SOR method had a big advantage in comparison with preconditioned Uzawa method in the accuracy of the calculated state y and control
.
A number of calculations were made for the different state and control constrained optimal control problems on the different meshes. All of them demonstrated the pref-
Table 1. Uzawa method.
Table 2. Block SOR method.
erence of the iterative methods based on the penalty of the state equation in the comparison with the preconditioned Uzawa methods, while that were faster convergent than the gradient methods applied for the problems with the penalization of the state constraints (see [9,10]).
NOTES