alexa An Algorithm for Solving Indefinite Quadratic Programming Problems

ISSN: 2168-9679

Journal of Applied & Computational Mathematics

An Algorithm for Solving Indefinite Quadratic Programming Problems

Siddieg AMAEl*
Department of Mathematics, Prince Sattam Bin Abdulaziz University, Alkharj Public Library, Sa'ad Ibn Mu'adh, Al Kharj, Saudi Arabia
*Corresponding Author: Siddieg AMAEl, Department of Mathematics, Prince Sattam Bin Abdulaziz University, Alkharj Public Library, Sa'ad Ibn Mu'adh, Al Kharj, Saudi Arabia, Tel: +966 11 588 8888, Email: [email protected]

Received Date: Dec 12, 2017 / Accepted Date: Jan 11, 2018 / Published Date: Jan 24, 2018

Abstract

In this paper, we give in section (1) compact description of the algorithm for solving general quadratic programming problems (that is, obtaining a local minimum of a quadratic function subject to inequality constraints) is presented. In section (2), we give practical application of the algorithm, we also discuss the computation work and performing by the algorithm and try to achieve efficiency and stability as possible as we can. In section (3), we show how to update the QR-factors of , when the tableau is complementary ,we give updating to the LDLT-Factors of . In section (4) we are not going to describe a fully detailed method of obtaining an initial feasible point, since linear programming literature is full of such techniques.

Introduction

In this section we give the detailed outlines of the algorithm of indefinite quadratic programming problems. It references to the numbers of some equations and conditions appeared in the following equations [1-8]:

Equation (1)

and

Equation (2)

the algorithm assumes the availability of an initial basic feasible point [9-15]. The steps are:

1. Given Equation and η, set K=1.

2. Solve (1) for q.

3. If Equation terminate with Equation otherwise solve EquationEquation for P1.

4. If If Equation is satisfied remove q from η; update the basic variables using [16-20] Equation to :Equation set K=K+1 and go to (b) otherwise remove q from η [21-28]; update the basic variables using Equation

5. Set r=1 and k k=k, set KK+r and add Pr to η .

6. Solve Equation

7. If Equation is satisfied, update the basic variables using Equation to Equation.

Set K=K+1 and go to (b).

Otherwise update the basic variables using Equation toEquation set r=r+1 and go to (e)

Practical Application of the Algorithm

The algorithm presented above represents a general outline of a method for solving indefinite quadratic programming problems rather than an exact definition of a computer implementation. In this section we discuss the computational work performed by the algorithm, and try to achieve efficiency and stability as possible as we can. In doing so we follow, with slight modifications, the work of Gill and Murray which has been applied to active set methods since mid-seventies until now [7-10]. The slight modifications are made to cope with the new forms of the matrices used in the method when G is indefinite. In the case when G is positive (semi definite) the active set methods are considered to be equivalent, [20], pointed out. There he gave a detailed description of that equivalence. He also re-mentioned this equivalence [6]. The major computational work of the algorithm is in the solution of

Equation (3)

and

Equation (4)

Equation (5)

Equation

We do not solve them directly; instead, we make use of the special structure of the matrices involved. We use the matrices H, T and U defined in eqn. (5). Thus, accordingly the solution in eqn. (3) is given by:

Equation (6)

Equation (7)

Equation (8)

Equation (9)

Equation (10)

Equation (11)

H, U, T define the inverse of the upper left partition of the basis matrix when the tableau is complementary. This calls for making them available at every complementary tableau. In other words they are to be updated from a complementary tableau to another [12].

Referring to Equation H, T and U are given by:Equation

Equation (12)

Equation

Where S(K) and Z(K) satisfy

Equation (13)

and Equation (14)

The choice of S(K) and Z(K) to satisfy in eqns. (13) and (14), respectively is generally open. Here we take the choice given in S=Q1R-T, Z=Q2 which is, according to K(ZTGZ)≤K(G), is advantageous as far as stability is concerned. For the sake of making this section selfcontained we show how S(K) and Z(K) are obtained in away suitable to this section. Let:

Equation (15)

represent the QR factorization of Equation, where Equation is n×Lx. Thus Q(K) is n×n and R(K) is an LLK upper triangular matrix partition Q(K) into Equation, where Equation is Lx×n. and Equation is Equation. Thus, in eqn. (15) we have:

Equation (16)

and Equation (17)

so in eqns. (16) and (17) we define S(K) and Z(K) by:

Equation (18)

and Equation (19)

Where Equation the identity matrix is whose columns are reversed. Thus we conclude by saying that the computation is focused on using the QR factorization of Equation, (when the kth iteration is complementary). So updating these factors is required at each iteration when the tableau is complementary [25].

Updating the QR-Factors of

In this section we show how to update the QR-factors of Equation, when the tableau is complementary, also we give updating to the LDLTFactors of Equation.

Following the stream of our discussions, two cases are to be considered separately. The case when the (k+1)th iteration results in a complementary tableau, and the case when complementarity is restored at the (k+r+1)th iteration after r successive non-complementary tableaux. In the first case the factors of Equation are updated to give those of Equation, and this is the case when a column, Equation say, is deleted from Equation. In the second case the factors of Equation are used to give those of Equation, and this is the case when one column, Equation say, is deleted from Equation and then r other columns are added to Equation. We follow the same steps carried [9], with the appropriate modification in the second case. In the first case, let Equation be the n×(Lk-1) matrix obtained by deleting the qth column, Equation, from Equation. Suppose the QR-factorization of Equation is given by: Equation, partition Equation into:Equation

Where Equation is n×(q-1) and Equation is n×(LK-q). Let R(K) have the form

Equation

where R11 is (q-1)×(q-1) upper triangular, R12 is (q-1)×(Lk-q), R22 is (Lk- q)×(Lk-q) upper triangular, Equation is a (q-L) vector, β is an (LK-q) vector and γ is a scalar. Since Equation will have the form:

Equation

Now, let Equation be the product of the plane rotations which gives:

Equation

where R' is (Lk-q)×(Lk-q) upper triangular. In this case Equation is an (Lk- q+1)×(Lk-q+1) orthogonal matrix. Thus if Equation

Which is orthogonal, then Equation

So we obtain Equation andEquation (20)

Thus, only the rows from the qth to the Lkth of Q(K) are altered in obtaining Q(K+1), so if Q(K+1) is partitioned into

Equation (21)

then Equation, in particular, takes the form:

Equation (22)

Note also that the first q-1 rows of Equation are not changed. This fact might be helpful as far as efficiency is concerned if we want to think of another alternative of choosing q in eqn. (1), such an alternative is:

Equation (23)

So that increase the number of rows of Equation and R(K) which are unaltered in iteration (K+1), which in turns reduces the effort, especially when Lk is relatively large. We now consider the second case when complementarity is restored at the (k+r+1)th iteration. Let Equation. Let Equation be obtained from Equation by removing Equation.

Thus

Equation (24)

Pre-multiplying both sides in eqn. (24) by Q(k+1) (defined in eqn. (21)) we get

Equation (25)

where Equation is defined in eqn. (20)

Equation (26)

Define the QR-factorization of Equation. Here Equation is (h-Lk+1)×(n-Lk+1) and orthogonal, and Equation is r×r upper triangular. If Equation

Then Equation (27)

Thus we obtain the QR-factorization of A(k+r+1) with

Equation (28)

Equation (29)

Updating the LDLT-Factors of Equation

The factors Equation of Equation are updated at each iteration when the tableau is complementary. Near the end of this section we show that Equation is always positive definite (on the assumption that Equation is positive semi-definite). Updating these factors is very stable when Equation is positive definite as we shall see. This fact is counted as one of the good numerical features of the method. We consider the case when the (k+1)th iteration results in a complementary tableau. Unfortunately, in the other case when complementarity is restored at the (k+r+1)th iteration, we are unable till now to explore a way of using the factors of Equation in obtaining those of Equation. However n-Lk-r, the dimension of Equation, decreases with r, in which case the effort of re-factorizing Equation might not be so much, especially when n-Lk is itself small. This calls for choosing the starting L1 so that n-L1 is small. In the case when the number of constraints is greater than n, L1 is chosen to be equal to n; that is the initial guess Equation is a vertex. With this choice Equation, and in the second iteration we might expect a constraint to be deleted from the active set (which is the case when the second iteration is complementary). Otherwise the third iteration will definitely restore complementarity at another vertex leaving Equation. In the former case the dimension of Equation is 1. In general the dimension of Equation keeps on increasing when constraints are deleted, and updating the factors is straight forward as will be shown. On the other hand the dimension of Equation keeps on decreasing when constraints are added to the active set, and in this case we are faced with re-factorizing the factors. We return to the case when the (k+1)th iteration is complementary. Here we are almost copying the work of in eqn. (9). In this case, as in eqn. (25) showsEquation, and using in eqn. (19) we have :

Equation (30)

the matrix Equation is given by:

Equation (31)

It can be shown that when a symmetric matrix is augmented by a single row and a column, the lower-triangular factor is augmented by a single row. Define:

Equation (32)

If we substitute in eqn. (31) and in eqn.(32) into the identity:

Equation, we obtain Equation and dn-LK+1 as the solution of the equations

Equation (33)

and Equation (34)

The numerical stability of this scheme is based on the fact that, if Equation is positive definite, the element Equation must be positive. In this event in eqn. (34) ensures that arbitrary growth in magnitude cannot occur in the elements of Equation

Before ending this section we show that when the kth iteration and the (k+1)th iteration are complementary then Equation must be positive definite.

Let the tableau be complementary at the kth iteration. Let Equation be the matrix whose columns correspond to the active constraints, and Equation. The increase of vq changes f according to

Equation (35)

Equation (36)

and Equation changes according to

Equation (37)

For the next tableau (i.e., the (k+1)th)) to be complementary uqq must be negative, and the new value Equation of vq must not violate feasibility.

Thus, using in eqn. (35), we have Equation which reflects the fact that f possesses a positive curvature along the direction Equation. Now letEquation be obtained from Equation by removing Equation and let Z(k+1) be defined so that Equation.

Pre-multiply both sides of in eqn. (37) by Equation to get:

Equation (38)

showing that Equation lies in the space spanned by the columns of Z(k+1), so

Equation (39)

for some (n-Lk+1) vector Equation. Since along Equation atEquation and Equation, then f is minimum along Equation atEquation, where

Equation (40)

We therefore conclude, in the active set methods sense, that the direction Equation solves the equality problem:

minimize Equation

Subject to Equation (41)

Using (39), Equation, thus Equation solves the problem

minimize Equation,

from which we conclude that Equation is positive definite.

Finding an Initial Feasible Point

In this section we are not going to describe a fully detailed method of obtaining an initial feasible point, since linear programming literature is full of such techniques. The method of finding a feasible point has been resolved in linear programming by a technique known as phase 1 simplex [27]. The basis of the technique is to define an artificial objective function, namely: Equation, where Equation is the set of indices of constraints which are violated at the point Equation, and to minimize this function with respect to Equation , subject to the constraints Equation. The function Equation is linear and is known as the sum of infeasibilities. If a feasible point exists the solution Equation of the artificial problem is such that Equation . In the case when m exceeds n, a non-feasible vertex is available as an initial feasible point to phase 1 and the simplex method is applied to minimize Equation. This process will ultimately lead to a feasible vertex [28]. Direct application of this method to finding a feasible point in the case when m is less than n is not feasible since, although a feasible point may exist a feasible vertex will not. Under these circumstances artificial vertices can be defined by adding simple bounds to the variables, but this could lead to either a poor initial point, since some of these artificial constraints must be active, or exclusion of the feasible region. A way out of this dilemma is described [6-9] a number of methods including the above one have been described. Gill and Murray is advantageous in that it makes available the QR-factorization of the initial matrix of active constraints which is then directly used in our algorithm.

References

Citation: Siddieg AMAEl (2018) An Algorithm for Solving Indefinite Quadratic Programming Problems. J Appl Computat Math 7: 380. DOI: 10.4172/2168-9679.1000380

Copyright: ©2018 Siddieg AMAEl. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Select your language of interest to view the total content in your interested language

Post Your Comment Citation
Share This Article
Article Usage
  • Total views: 823
  • [From(publication date): 0-2018 - Sep 19, 2018]
  • Breakdown by view type
  • HTML page views: 746
  • PDF downloads: 77

Post your comment

captcha   Reload  Can't read the image? click here to refresh