Processing math: 10%

Thursday, October 24, 2019

Quadratic Programming in Hilbert space. Part III. General case.



The algorithm described in the previous post can be applied for solving a more general quadratic programming problem [1], [2].

Let H is a Hilbert space with inner product ,H and norm and A is a linear positive-definite self-adjoint operator acting in H. Let linear manifold D = D(A), D \subset H is the domain of definition of this operator and the element z belongs to D.

It is required to minimize functional J:
\begin{eqnarray}    (J, \varphi) =  {\langle A \varphi \, , \varphi \rangle}_H - 2 {\langle z \, , \varphi \rangle}_H \to \min \ , \ \end{eqnarray}
subject to constraints
\begin{eqnarray}     {\langle h_i , \varphi \rangle}_H &=& u_i \, ,     \quad 1 \le i \le L \ , \\     {\langle h_{i+L} , \varphi \rangle}_H  &\le& u_{i+L} \, ,     \quad 1 \le i \le M \, , \\  \nonumber  \varphi  &\in& D \, , \quad  D \subset H \, . \end{eqnarray}
The elements h_i \in D, \, 1 \le i \le M+L are assumed to be linearly independent (thereby the system of constraints is compatible). 

Let H_A be an energetic space generated by the operator A [2], [3]. This space is a completion of linear manifold D with a scalar product
\begin{eqnarray*}   [\varphi, \vartheta]_A  =  {\langle A \varphi \, , \vartheta \rangle}_H \ ,  \quad \varphi, \vartheta \in H_A \, , \end{eqnarray*}
and corresponding norm [\varphi, \varphi]_A.
We introduce elements \bar z and \bar h_i from H_A as solutions of the following equations
\begin{eqnarray*} A \bar z &=& z,  \quad \bar z \in H_A  \, , \\  A \bar h_i &=& h_i \, , \ \ \,  \bar h_i \in H_A \, , \quad 1 \le i \le M+L \, , \end{eqnarray*}
and quadratic functional
\begin{eqnarray}  (\bar J, \varphi) = \| \varphi - z \|_A^2 \, . \end{eqnarray}
It is easy to see that
\begin{eqnarray*}  (J, \varphi) =  (\bar J, \varphi) - \|  z \|_A^2 \, . \end{eqnarray*}
and constraints (2), (3) are transformed to
\begin{eqnarray}     [\bar h_i , \varphi]_A &=& u_i \, ,  \quad 1 \le i \le L \ , \\     [\bar h_{i+L} , \varphi]_A  &\le& u_{i+L} \, ,  \ 1 \le i \le M+L \, , \\  \nonumber  \varphi  &\in& H_A \,  , \quad \bar h_i \in H_A. \end{eqnarray}
Thereby the problem of minimization of functional (1) on linear manihold D subject to constraints (2), (3) is equivalent to the problem of minimization of functional (4) in Hilbert space H_A under constraints (5), (6). This later problem is a problem of finding a projection of element z onto a nonempty convex closed set defined by (5), (6) and it has an unique solution. The solution can be found by using algorithms described in the previous posts.

References

[1] V. Gorbunov, Extremum Problems of Measurements Data Processing, Ilim, 1990 (in Russian).
[2] V.Lebedev, An Introduction to Functional Analysis in Computational Mathematics, Birkhäuser, 1997
[3] V. Agoshkov, P. Dubovski, V. Shutyaev, Methods for Solving Mathematical Physics Problems. Cambridge International Science Publishing Ltd, 2006.