Performance analysis of gradient neural network exploited for online time-varying quadratic minimization and equality-constrained quadratic programming

Abstract

In this paper, the performance of a gradient neural network (GNN), which was designed intrinsically for solving static problems, is investigated, analyzed and simulated in the situation of time-varying coefficients. It is theoretically proved that the gradient neural network for online solution of time-varying quadratic minimization (QM) and quadratic programming (QP) problems could only approximately approach the time-varying theoretical solution, instead of converging exactly. That is, the steady-state error between the GNN solution and the theoretical solution can not decrease to zero. In order to understand the situation better, the upper bound of such an error is estimated firstly, and then the global exponential convergence rate is investigated for such a GNN when approaching an error bound. Computer-simulation results, including those based on a six-link robot manipulator, further substantiate the performance analysis of the GNN exploited to solve online time-varying QM and QP problems.

Introduction

As an important branch of mathematical optimization, quadratic programming (QP) constrained with linear equalities [with quadratic minimization (QM) as a special case] has been theoretically analyzed [1], [2], [3], [4] and widely applied in various scientific areas; e.g., optimal controller design [5], [6], power-scheduling [7], robot-arm motion planning [8], [9], [10], [11], and digital signal processing [12]. Due to its fundamental roles, many algorithms have been proposed to solve QP problems [3], [13], [14]. In general, numerical algorithms performed on digital computers are considered to be a well-accepted approach to QM and linear-equality constrained QP problems. However, for large-scale online or real-time applications, such numerical algorithms may not be efficient enough, since the minimal arithmetic operations are normally proportional to the cube of Hessian matrix's dimension n [12].

To solve optimization problems more efficiently, many parallel-processing computational methods have been proposed, analyzed, and implemented based on specific architectures, e.g., the neural-dynamic and analog solvers investigated in [15], [16], [17], [18], [19], [20]. Due to the in-depth research in recurrent neural networks (RNN), such a neural-dynamic approach is now regarded as a powerful alternative to real-time computation and optimization, owing to its parallel-processing distributed nature and convenience of hardware implementation [21], [22], [23], [24], [25], [26], [27], [28], [29]. It is worth noting that Chua and Lin [21] developed a canonical nonlinear programming circuit (NPC) for simulating general nonlinear programs; and that Kennedy and Chua [22] explored the stability properties of such a canonical nonlinear programming circuit model with the objective function and constraints being smooth. Forti et al. [27] introduced a generalized circuit for nonsmooth programming problems, which derives from a natural extension of NPC. Bian and Xue [28] proposed a subgradient-based neural network to solve a nonsmooth nonconvex optimization problem with the objective function being nonsmooth and nonconvex.

A number of neural-dynamic models have been proposed, which are usually based on the gradient-descent methods, or termed gradient neural networks (GNNs). For solving static problems, such GNNs can be proved to exponentially converge to theoretical optimal solutions [9], [18], [24], [30]. To lay a basis for further discussion, the design of a GNN model can generally be described as follows.

• First, to solve a given problem via GNN, a scalar-valued norm-based nonnegative energy function $\varepsilon (t)\ge 0\in \mathbb{R}$ is defined. Theoretically speaking, a minimum point of the energy function $\varepsilon (t)$ is achieved with $\varepsilon (t)=0$, corresponding to the situation that the neural-solution [e.g., $\mathit{x}(t)$] is the theoretical solution (e.g., ${\mathit{x}}^{⁎}$) of the given static problem.

• Second, a computational scheme can be designed to evolve along a descent direction of the energy function $\varepsilon (t)$, until the minimum point is reached. It is worth mentioning here that a typical descent direction is the negative gradient of $\varepsilon (t)$, i.e., $-(\partial \varepsilon /\partial \mathit{x})$.

• Third, the conventional gradient neural network design formula can be chosen and implemented as follows:

  $$\dot{\mathit{x}}(t)≔\frac{d\mathit{x}(t)}{\mathit{dt}}=-\gamma \frac{\partial \varepsilon }{\partial \mathit{x}}\text{,}$$

  where design parameter $\gamma >0$ corresponds to the reciprocal of a capacitance parameter in the analog-circuit implementation of GNN (1), which should be set as large as the hardware would permit or selected appropriately for simulative and/or experimental purposes [31], [32].

However, it is worth pointing out that such a GNN is designed intrinsically for static problems solving with constant coefficient matrices and vectors. When applied to time-varying matrix–vector problems, the GNN may generate a considerably large solution-error, as shown in [33] by Zhang et al. Facing this less-favorable phenomenon, the authors have been interested in the problems inside and have begun to investigate the performance of GNN-type solvers applied to time-varying quadratic optimization. The main contributions of this paper lie in the following facts.

• In this paper, the less-favorable phenomenon of GNN is pointed out formally and systematically; i.e., conventional GNN as a system can not solve exactly the time-varying quadratic optimization problems. In other words, there always exists a nonzero steady-state solution error between the GNN-solution and the time-varying theoretical solution.

• This paper investigates and analyzes the performance of GNN applied to time-varying QM and QP problems. Theoretical analysis is provided rigorously for estimating the steady-state solution-error bound and exponential convergence rate for GNN approaching an error bound.

• The gain $\gamma$ is quite widely exploited in many researchers' works. However, almost all existing works may only show examples to substantiate the function of this parameter in the situation of static problems solving; and the gradient neural networks are then applied to the situation of time-varying problems solving, but without theoretical proof. In this paper, the theoretical analysis and proof are presented for gradient neural network solving time-varying quadratic optimization problems, including the theoretically proved important role of design parameter $\gamma$ in the situation of time-varying quadratic optimization.

• Illustrative examples of online time-varying QM and QP problems solving substantiate well the theoretical results, e.g., those about the steady-state solution-error bound, the important roles of design parameter $\gamma$ and solution-variation rate $\zeta$.

• The application and simulation results based on a six-link robot manipulator further substantiate the performance analysis of the GNN solving time-varying QP problems.

To the best of the authors' knowledge, to date, few studies have been published on such a time-varying performance analysis in the literature at the present stage. Note that Myung and Kim [25] proposed a time-varying two-phase (TVTP) algorithm which can give exact feasible solutions with a finite penalty parameter when the problem is a constrained time-varying optimization. Their work is inspiring and interesting. Evidently, there are some substantial differences between Myung and Kim's pioneering work and this paper lying as below.

• Myung and Kim's work considers the time-varying optimization problem when time t goes to infinity or large enough. In contrast, this paper is to find the time-varying optimal solution at any time instant.

• The constraints in Myung and Kim's work are static. In contrast, the coefficients of quadratic programming investigated in this paper are time-varying, i.e., with a time-varying matrix/vector constraint.

• Myung and Kim's work exploits a penalty-based method for handling time-varying optimization problems. In contrast, this paper exploits time-varying linear-equation solving and Lagrange multiplier method for handling the time-varying quadratic optimization problems at any time instant $t\in [0,\infty )$.

The remainder of this paper is organized as follows. Section 2 describes the situation of using GNN for solving online time-varying QM problem. Online time-varying QP problem solving is further developed and investigated in Section 3. In Section 4, the authors analyze the performance of GNN applied to time-varying QM and QP problems solving; specifically speaking, the solution-error bound and the exponential convergence rate towards a bound are analyzed. Several illustrative examples are shown in Section 5. Section 6 further presents the application and simulation results based on a six-link planar robot manipulator. Finally, the paper is concluded with some remarks in Section 7.