Improved Conditions for the Existence and Uniqueness of Solutions to the General Equality Constrained Quadratic Programming Problem ()
1. Introduction
Usually the general quadratic programming
problem has a structure of the form
![](https://www.scirp.org/html/1-2730007\c83d11b6-02a9-4450-be91-55d27d2c16a9.jpg)
![](https://www.scirp.org/html/1-2730007\7e228462-a8ca-4079-bc0f-5ea225b7c3d9.jpg)
![](https://www.scirp.org/html/1-2730007\04324d38-3be9-455d-a870-09e9ad873760.jpg)
where
is a symmetric
matrix,
and
are finite sets of indices. In quadratic programming problems, the matrix
is called the Hessian matrix. The vectors
and
are column vectors in
. To make computational life easier, we consider only the equality constraints and formulate the equality constrained quadratic programming
problem as follows
![](https://www.scirp.org/html/1-2730007\30b7799c-bf45-475a-a649-d77d623d9b2a.jpg)
![](https://www.scirp.org/html/1-2730007\ee2b547b-7346-4a06-bc92-c94c9d5cf375.jpg)
where
is a
jacobian matrix of constraints (with
) [1]. Throughout this paper, we will assume that
can be of any form, since it is not a participant in the determination of the ECQP’s global minimum. Quadratic programming problems occur naturally, and sometimes stem as subproblems in general constrained optimization methods, such as sequential quadratic programming, augmented Lagrangian methods, and interior point methods. This type of programming problems occurs in almost every discipline and as a result became a topic of interest to a lot of researchers [1-3].
In sequential quadratic programming
algorithms, an
phase that employs second derivative information (Hessian matrix) is usually added to enhance rapid convergence to the solution [4-7]
algorithms [8] that utilize the exact Hessian matrix are often preferred to those that use convex quasi-Newton approximations [9-11] since they need lesser time to converge to the solution.
In 1985, Gould investigates the conditions under which the
problem can be said to have a finite solution. Gould’s analysis of the
problem is based on the concepts of the reduced Hessian matrix
and signs of the eigenvalues of the Karush-Kuhn Tucker
matrix [3]. The well known
matrix has the form
![](https://www.scirp.org/html/1-2730007\40f7fd53-7cc6-4a54-8eab-53d377f2b7f8.jpg)
[1]. For small-scale
problems it is possible to solve the
matrix (and hence, the
problem ) analytically [1,3,12]. The matrix
is one whose columns are a basis for the null space of
(matrix of contraints), and is obtained from the
factorization of
. We investigated the method and found that the reduced Hessian matrix is not always accurate due to rounding off errors arising in the calculation of
[13-15].
Our goal in this paper is to present a new method that utilizes a necessary and sufficient condition for the existence and uniqueness of the solutions of the
problem. In this paper, we show that for the
problem to have a global solution, its Hessian matrix must possess a Cholesky factor. As we shall see in Section 2, this paper focuses only on the condition(s) under which the
problem is said to have a global solution [16].
This paper is organized as follows. In Section 2, we discuss our method. Gould’s method is reviewed in Section 3. The analysis follow in Section 4 and some concluding remarks are made in Section 5.
2. Method
In this section, we introduce our new method of analyzing the solution of the
problem. It is based on the fact that the Cholesky decomposition is unique for positive definite matrices.
Cholesky Decomposition
Let
be a matrix that can undergo Cholesky decomposition with a Cholesky factor
(Lower triangular matrix) then we can write
(2.1)
where
is the transpose of
. We let
(2.2)
Substituting Equation (2.2) into Equation (2.1) gives
(2.3)
From Equation (2.3), we see that the conditions for
to be positive definite are satisfied. Therefore,our conditions for positive definiteness are; the matrix must be a square matrix and possesses a Cholesky factor.
We let
to be a
column vector say
(2.4)
and we write
(2.5)
From Equation (2.3), it is clear that the first and second terms are always positive, which implies their sum is also always positive and greater than the third term if
. When
the matrix
always equals zero. Therefore, the matrix
is always positive if and only if the column vector
has entries
and
(such that
) and the matrix
has a Cholesky factor.
In the above demonstration
, which means that a
matrix
and a
column vector
produces Equation (2.5). Analogously, any
matrix
and any
column vector
(where
) shall produce an equation similar in properties to Equation (2.5). If and only if
.
Corollary 2.1: Let
be any non-singular matrix and the Hessian matrix being Cholesky factorizable. Then the
matrix
(2.6)
is nonsingular and has a unique solution.
Corollary 2.2: Let
be the Karush-Kuhn-Tucker matrix
(2.7)
and assume
is any matrix. Then the
problem has a global minimum if and only if the Hessian matrix has a Cholesky factor.
3. Review of Gould’s Method
In this section, we review Gould’s method. The method consists of three approaches: Null-space methods, Lagrangian methods and Schur complement methods [12].
Null-space methods: For
to be a solution of the
problem, a vector
(i.e. Lagrange multipliers) must exist such that the system of equations below is satisfied
(3.1)
We let
(3.2)
with
being some estimate of the solution and
the desired step. By expressing
as in Equation (3.2), Equation (3.1) can be written in a form that is more useful for computational purposes as given below
(3.3)
where
(3.4)
(3.5)
(3.6)
This method finds
and
first, by partitioning the vector
into two components as follows
(3.7)
where
and
have orthonormal columns and can be obtain from the
factorization of
. An interesting property of this approach is that
[1,3], which makes the calculation of
and
possible by solving the four equations below
(3.8)
(3.9)
(3.10)
(3.11)
This method has a wider application than the Rangespace methods because; it doesn’t require
being nonsingular. According to this paper, the condition, that
must undergo Cholesky decomposition is the only requirement for the
problem to have a global minimum. A knowledge of the null space basis matrix
is not important at all.
Lagrangian methods: This method calculates the values of
and
directly from Equation (3.3), i.e. the Karush-Kuhn-Tucker equations for the
problem.
In this paper, the
problem can only have a global minimum if
possesses a Cholesky factor
.
Schur complement methods: Here we assume that
has a Cholesky factor and derive two equations from Equation (3.3) for the solutions of
and
. These equations are as follows
(3.12)
(3.13)
It is easy to see that both
and
are positive definite. In this paper, we show that
and
have Cholesky factors and hence
is always positive definite, which indicate the existence of a global solution for the
problem Section 2.
4. Analysis
In this section we will solve a numerical example from [1] using our algorithm and compared our results with those of Gould’s method. Let us consider the
problem below and deduce whether it has a global minimum or not by using Gould’s method and our algorithm.
![](https://www.scirp.org/html/1-2730007\4cb5b3a4-d85d-4570-ad3f-2298a58319c3.jpg)
(4.1)
We will write the above
problem in the standard form described in the introduction by defining
![](https://www.scirp.org/html/1-2730007\3cc06cc4-0807-4551-aa02-946d22f8c624.jpg)
![](https://www.scirp.org/html/1-2730007\c0723871-0254-4e0e-9fd5-23da3c1f05a4.jpg)
For Gould’s algorithm we need to find
from the
factorization of matrix
i.e.
.
![](https://www.scirp.org/html/1-2730007\d67c2905-0116-467f-95d6-74f66b5c64b7.jpg)
![](https://www.scirp.org/html/1-2730007\bb2ccdf2-018b-4982-9dff-4997bd8c1c5f.jpg)
We can obtain
from the column space of matrix
and the matrix
must satisfies the constrain
. Hence we have
![](https://www.scirp.org/html/1-2730007\80a29413-3963-479f-890a-3dbde0ad81e3.jpg)
Therefore,
and according to Gould’s algorithm the
problem has a global minimum.
For our algorithm we only need to show that the matrix
has a Cholesky factor. Let
be the Cholesky factor of
.
![](https://www.scirp.org/html/1-2730007\1be8b6f7-6376-4f06-a07f-10ee84278e89.jpg)
According to our algorithm,this implies the matrix
is positive definite and therefore the
problem has a minimum solution. To show this fact we select any matrix that is a subset of the set of matrices described in subsection (2.1) and suppose we have that matrix to be
then
.
Let us consider another matrix
![](https://www.scirp.org/html/1-2730007\aa79de92-5e14-463d-9d2d-da846baa1ad2.jpg)
We will have result
![](https://www.scirp.org/html/1-2730007\eb98da30-25b2-4ce1-beb0-1f87e36aee62.jpg)
Finally, we consider a matrix with all negative entries as follows
![](https://www.scirp.org/html/1-2730007\e94c4be7-089e-4f3e-862a-13ac38fdef6c.jpg)
This gives the result
![](https://www.scirp.org/html/1-2730007\7fb424a0-ca26-4849-9d72-e04b940c8d63.jpg)
From the above example, we observed the following result:
1) Multiplying a matrix
that has a Cholesky factor with any other matrix except the zero matrix, doesn’t alter the positive definite property of matrix
and hence the existence of global minimum.
2) Decimals are encountered in Gould’s approach which may lead to rounding off errors and hence inaccuracy. Decimals have no effects on our method as long as the Hessian matrix has a Cholesky factor.
3) The number of matrix operations that are involved in Gould’s approach are far more than those that are involved in our algorithm which implies that our method is faster than that of Gould.
Gould’s approach uses the notion of the reduced Hessian matrix and the signs of the eigenvalues of the Karush-Kuhn-Tucker matrix to analyze the conditions under which the
problem shall have a global solution [3]. It is clear that
is sometimes incorrect due to rounding off errors in the calculation of
. In this paper, we present a method that directly utilizes the Hessian matrix to analyze global minimum conditions for the
problem.
Finally, this proposed method has fewer iterations than Gould’s algorithm, inexpensive and naturally faster (Cholesky factorization) than Gould’s approach (with more iterations).
5. Conclusions
In 1985, Gould investigates the practical conditions for the existence and uniqueness of solutions of the
problem based on
and inertia of the
matrix. In this piece of work, we present a new method that directly works with
to analyze global solutions of the
problem.
The advantages of our method lie in its accuracy, cost and number of operations. It is true that this noble algorithm is unique and computationally faster (i.e. Cholesky decomposition) than Gould’s method. Our method also revealed that if the Hessian matrix has a Cholesky factor then, the Hadamard inequality [17] for positive definiteness is satisfied as well.
We finally conclude that the existence and uniqueness of solutions of the
problem is independent of its constraints but depend wholly and solely on the Hessian matrix
.
6. Acknowledgements
We would like to thank Khalid O. Elaalim for his useful contributions during the early stages of this work. We are also grateful to anonymous referees for their valuable comments on this paper. Finally, we would like to extend special thanks to the Chinese Scholarship Council which funded this research.
NOTES