Subscribe Now Subscribe Today
Research Article
 

An Approximation Method for Solving Nonconvex Quadratic Programming Problems



Ali Ahmadian and Reza Afsharinafar
 
ABSTRACT

In this study, we propose an approximate solution for nonconvex Quadratic Programming Problem (QPP) in general form using the eigenvalues of the Hessian matrix. Here we don't consider any special conditions (such as positive definiteness or positive semi definiteness) for the Hessian matrix of the objective function. Using the eigenvalues of the hessian matrix and solving two optimization problems, we propose an interval containing the optimal solution of QPP. This method can be useful for complicated and large scale optimization problems and also for integer quadratic programming problems.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Ali Ahmadian and Reza Afsharinafar, 2011. An Approximation Method for Solving Nonconvex Quadratic Programming Problems. Journal of Applied Sciences, 11: 3807-3810.

DOI: 10.3923/jas.2011.3807.3810

URL: https://scialert.net/abstract/?doi=jas.2011.3807.3810
 
Received: August 04, 2011; Accepted: November 23, 2011; Published: January 02, 2012

INTRODUCTION

Quadratic programming problem (QPP) is a special class of Nonlinear Programming Problems (NLPPs) where the objective function is quadratic and the constraints are linear. QPP has widespread applications in engineering (Petersen and Bodson, 2006) (e.g., electrical engineering), economics (Schwarz, 2006) and practical problems in sciences. Also often approximate nonlinear programming problems via a series of quadratic programming (Zhu and Zhang, 2004). On the other hand, a broad class of difficult combinatorial problems can be formulated as nonconvex quadratic minimization problem, for example: integer programming, quadratic 0-1 programming, quadratic assignment problems, bilinear programming, linear complementary problems and max/min problems (Pardalos and Rosen, 1987). Several methods (e.g., Wolfe and Bale), are available in the literature for solving QPPs.

Also we can apply Kurush-Kuhn-Tucker (KKT) optimality conditions (Bazaraa et al., 1993) for solving a QPP. The algorithms for quadratic programming have been developed in the past few decades, such as active set method, interior point method, dual method, etc. (Zhu and Zhang, 2004) Nonconvex quadratic programming problem has great importance both from the mathematical and application viewpoints. During the last decade, several authors have shown that the general quadratic programming problem is an NP-hard problem in global optimization (Murty and Kabadi, 1987). In this study we try to propose bounds for a general QPP using an optimization problem with interval valued objective function.

PROPOSED METHOD

Consider the following general QPP:

(1)

subject to:

where, ε and I are finite sets of indices, c is a n vector and H is an NxN symmetric matrix, {ai}, i∈I∪ε are vectors with n elements. Let H be a positive definite matrix then the objective function will be a convex function and we can apply nonlinear programming methods (which are convergent to the unique solution). In this case (1) is said to be a convex QP. When the hessian matrix of the objective function is not positive semi definite, however, finding a global minimum for the underlying QPP becomes a difficult task. In fact, nonconvex QPs, in which H is an indefinite matrix, can be more challenging, since they can have several stationary points and local minima. Here we use a theorem and find an interval which involves the optimal value of the objective function which can be useful. Our approximation is useful for complicated and large scale problems.

Basics of our new method are to estimate the quotient:

for x ≠ 0 from both sides. Consider the following theorem:

Theorem 1: If A is a symmetric matrix of order n with eigenvalues λ1≤λ2≤...λn, then:

(2)

proof (Fiedler et al., 2006).

Now we apply this theorem to find the bounds of optimal solution of problem (1). Suppose that, λ1≤λ2≤...λn, are the eigenvalues of the matrix H, then for every nonzero vector x we have for every nonzero vector x. It is simple to see that In another word we found a range for the objective function of problem (1), and so we have:

(3)

using Eq. 3 we have:

(4)

For every nonzero vector x. It is simple to see that:

(5)

In another word we found a range for the objective function of problem (1) and so we have:

(6)

where, I is the identity matrix of order n. So it is enough to solve the following QPPs:

(7)

subject to:

And:

(8)

Subject to:

which it is very simple, because I is a positive semi definite matrix and symmetric, so we can apply any nonlinear programming techniques.

Remark 1: Note that to compute the smallest and greatest eigenvalues we can apply existing algorithms in numerical linear algebra (e.g., Power method).

NUMERICAL RESULTS

Here, to show the applicability of this approximation, we solve two examples which the second one is a nonconvex QPP. To solve numerical examples with proposed method, we used MATLAB7 optimization toolbox.

Here, to show the applicability of this approximation, we solve two examples which the second one is a nonconvex QPP. To solve numerical examples with proposed method, we used MATLAB7 optimization toolbox.

Example 1: consider the following QPP:

(9)

subject to:

According to Eq. 1, here:

Optimal solution is x* = (1.6923, -1.3077, 1.3077)T with objective value Z = 7.7692. Here we solved corresponding problems 7 and 8 for this example. The optimal value for Lower problem is x*L = (2.5650, -0.4350, 0.4350) with ZL = -4.1001 and for Upper problem x*U = (2.1568, -0.8432, 0.8432)T with ZU = 34.4009. For this example x*U is nearer to x*. Table 1 shows the numerical results.

In next example, we apply the same method to solve a QPP with indefinite Hessian matrix.

Example 2: consider the following indefinite QPP:

(10)

Subject to:

Where:

This example solved by an iterative method in Eq. 5, with optimal solution:

and the optimal value Here we solved this example: Z*L = -24.0313 and the optimal solution:


Table 1: Numerical results for example 1

Table 2: Numerical results for example 2

Table 3: Numerical results for example 3

This example solved by an iterative method in Eq. 5, with optimal solution:

and the optimal value Z = -15.0313. Here we solved this example: Z*L = -24.0313 and the optimal solution:

and also Z*U = 0.1 with x*U = (0.2, 0.4)T In this example, x*L is more near to x*. Table 2 shows the numerical results.

Example 3: Now consider the following QPP from Wang et al. (2005)

So we have

This problem is solved in Wang et al. (2005). The optimal solution can be seen in Table 3.

CONCLUSION

In this study, we proposed a novel approximation method for solving any QPP in general form. Nonconvex quadratic programming problems have widespread applications from both theoretical and practical viewpoints. But the general quadratic programming problem is an NP-hard problem in global optimization, so our approximation method can be very useful. In this method, to compute the eigenvalues of the Hessian matrix, we can use numerical linear algebra methods. Work is in progress to apply this method for solving problems arising in engineering applications and also for Integer QPP.

REFERENCES
Bazaraa, M.S., H.D. Sherali and C.M. Shetty, 1993. Nonlinear Programming Theory and Algorithms. 2nd Edn., Wiley, New York.

Fiedler, M., J. Nedoma, J. Ramik, J. Rohn and K. Zimmermann, 2006. Linear Optimization Problems with Inexact Data. Springer Science Business Media Inc., New York.

Murty, K.G. and S.N. Kabadi, 1987. Some NP-complete problems in quadratic and nonlinear programming. Math Progr., 39: 117-129.
CrossRef  |  

Pardalos, P.M. and J.B. Rosen, 1987. Constrained Global Optimization: Algorithms and Applications Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, ISBN: 9783540180951, Pages: 143.

Petersen, J.A.M. and M. Bodson, 2006. Constrained quadratic programming techniques for control allocation. IEEE Trans. Control Syst. Technol., 14: 91-98.
CrossRef  |  

Schwarz, H.G., 2006. Economic material-product chain models: Current status, further development and an illustrative example. Ecol. Econ., 58: 373-392.
CrossRef  |  

Wang, D.Q., S. Chukova and C.D. Lai, 2005. Reducing quadratic programming problem to regression problem: Stepwise algorithm. Eur. J. Operat. Res., 164: 79-88.
Direct Link  |  

Zhu, Z. and K. Zhang, 2004. A new SQP method of feasible directions for nonlinear programming. Applied Math. Comput., 148: 121-134.
CrossRef  |  

©  2019 Science Alert. All Rights Reserved