Improved Conditions for the Existence and Uniqueness of Solutions to the General Equality Constrained Quadratic Programming Problem

Affiliation(s)

Department of Mathematics, University of Science and Technology of China, Hefei, China.

Department of Mathematics, Faculty of Pure and Applied Sciences, Fourah Bay College,University of Sierra Leone, Freetown, Sierra Leone.

Department of Mathematics, Faculty of Education, Kassala University, Kassala, Sudan.

Department of Mathematics, University of Science and Technology of China, Hefei, China.

Department of Mathematics, Faculty of Pure and Applied Sciences, Fourah Bay College,University of Sierra Leone, Freetown, Sierra Leone.

Department of Mathematics, Faculty of Education, Kassala University, Kassala, Sudan.

ABSTRACT

This paper presents an approach that directly utilizes the Hessian matrix to investigate the existence and uniqueness of global solutions for the ECQP problem. The novel features of this proposed algorithm are its uniqueness and faster rate of convergence to the solution. The merit of this algorithm is base on cost, accuracy and number of operations.

This paper presents an approach that directly utilizes the Hessian matrix to investigate the existence and uniqueness of global solutions for the ECQP problem. The novel features of this proposed algorithm are its uniqueness and faster rate of convergence to the solution. The merit of this algorithm is base on cost, accuracy and number of operations.

Cite this paper

A. Kamara, M. Koroma and M. M.-Ali, "Improved Conditions for the Existence and Uniqueness of Solutions to the General Equality Constrained Quadratic Programming Problem,"*Open Journal of Optimization*, Vol. 1 No. 2, 2012, pp. 15-19. doi: 10.4236/ojop.2012.12003.

A. Kamara, M. Koroma and M. M.-Ali, "Improved Conditions for the Existence and Uniqueness of Solutions to the General Equality Constrained Quadratic Programming Problem,"

References

[1] J. Nocedal and S. J. Wright, “Numerical Optimization,” 2nd Edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006, pp. 448-492. doi:10.1007/978-0-387-40065-5_16

[2] N. I. M. Gould, M. E. Hribar and J. Nocedal, “On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization,” SIAM Journal on Scientific Computing, Vol. 23, No. 4, 2001, pp. 1376-1395. doi:10.1137/S1064827598345667

[3] N. I. M. Gould, “On Practical Conditions for the Existence and Uniqueness of Solutions to the General Equality Quadratic Programming Problem,” Mathematical Programming, Vol. 32, No. 1, 1985, pp. 90-99. doi:10.1007/BF01585660

[4] R. H. Byrd, N. I. M. Gould, J. Nocedal and R. A. Waltz, “An Algorithm for Nonlinear Optimization Using Linear Programming and Equality Constrained Subproblems,” Mathematical Programming, Vol. 100, No. 1, 2004, pp. 27-48.

[5] N. I. M. Gould and D. P. Robinson, “A Second Derivative SQP Method: Global Convergence,” SIAM Journal on Optimization, Vol. 20, No. 4, 2010, pp. 2023-2048. doi:10.1137/080744542

[6] N. I. M. Gould and D. P. Robinson, “A Second Derivative SQP Method: Local Convergence and Practical Issues,” SIAM Journal on Optimization, Vol. 20, 2010, pp. 2049-2079. doi:10.1137/080744554

[7] J. L. Morales, J. Nocedal and Y. Wu, “A Sequential Quadratic Programming Algorithm with an Additional Equality Constrained Phase,” IMA Journal of Numerical Analysis, Vol. 32, No. 2, 2012, pp. 553-579. doi:10.1093/imanum/drq037

[8] R. Fletcher and S. Leyffer, “Nonlinear Programming without a Penalty Function,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 239-269. doi:10.1007/s101070100244

[9] A. Drud, “CONOPT: A GRG Code for Large Sparse Dynamic Nonlinear Optimization Problems,” Mathematical Programming, Vol. 31, No. 2, 1985, pp. 153-191. doi:10.1007/BF02591747

[10] P. E. Gill, W. Murray and M. A. Saunders, “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization,” SIAM Journal on Optimization, Vol. 12, No. 4, 2002, pp. 979-1006. doi:10.1137/S1052623499350013

[11] K. Schittkowski, “The Nonlinear Programming Method of Wilson, Han and Powell with an Augmented Lagrangian Type Line Search Function,” Numerische Mathematik, Vol. 38, No. 1, 1981, pp. 83-114. doi:10.1007/BF01395810

[12] S. Boyd and L. Vandenberghe, “Convex Optimization,” Cambridge University Press, Cambridge, 2004, pp. 241245.

[13] E. Anderson, Z. Bai and J. Dongarra, “Generalized QR Factorization and Its Application,” Linear Algebra and Its Applications, Vol. 162-164, 1992, pp. 243-271. doi:10.1016/0024-3795(92)90379-O

[14] P. E. Gill and W. Murray, “Numerically Stable Methods for Quadratic Programming,” Mathematical Programming, Vol. 14, No. 1, 1978, pp. 349-372. doi:10.1007/BF01588976

[15] M. OCW, “Positive Definite Matrices and Minima,” 2012. http://ocw.mit.edu/courses/mathematics/18-06sc-linear-algebra-fall-2011/positive-definite-matrices-and -applications/positive-definite-matrices-and-minima/MIT18_06SCF11_Ses3.3prob.pdf

[16] Wikipidia, “Positive-Definite Matrix,” 2012. http://en.wikipedia.org/wiki/Positive-definite_matrix

[17] R. A. Horn and C. R. Johnson, “Matrix Analysis,” Cambridge University Press, Cambridge, 1985.

[1] J. Nocedal and S. J. Wright, “Numerical Optimization,” 2nd Edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006, pp. 448-492. doi:10.1007/978-0-387-40065-5_16

[2] N. I. M. Gould, M. E. Hribar and J. Nocedal, “On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization,” SIAM Journal on Scientific Computing, Vol. 23, No. 4, 2001, pp. 1376-1395. doi:10.1137/S1064827598345667

[3] N. I. M. Gould, “On Practical Conditions for the Existence and Uniqueness of Solutions to the General Equality Quadratic Programming Problem,” Mathematical Programming, Vol. 32, No. 1, 1985, pp. 90-99. doi:10.1007/BF01585660

[4] R. H. Byrd, N. I. M. Gould, J. Nocedal and R. A. Waltz, “An Algorithm for Nonlinear Optimization Using Linear Programming and Equality Constrained Subproblems,” Mathematical Programming, Vol. 100, No. 1, 2004, pp. 27-48.

[5] N. I. M. Gould and D. P. Robinson, “A Second Derivative SQP Method: Global Convergence,” SIAM Journal on Optimization, Vol. 20, No. 4, 2010, pp. 2023-2048. doi:10.1137/080744542

[6] N. I. M. Gould and D. P. Robinson, “A Second Derivative SQP Method: Local Convergence and Practical Issues,” SIAM Journal on Optimization, Vol. 20, 2010, pp. 2049-2079. doi:10.1137/080744554

[7] J. L. Morales, J. Nocedal and Y. Wu, “A Sequential Quadratic Programming Algorithm with an Additional Equality Constrained Phase,” IMA Journal of Numerical Analysis, Vol. 32, No. 2, 2012, pp. 553-579. doi:10.1093/imanum/drq037

[8] R. Fletcher and S. Leyffer, “Nonlinear Programming without a Penalty Function,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 239-269. doi:10.1007/s101070100244

[9] A. Drud, “CONOPT: A GRG Code for Large Sparse Dynamic Nonlinear Optimization Problems,” Mathematical Programming, Vol. 31, No. 2, 1985, pp. 153-191. doi:10.1007/BF02591747

[10] P. E. Gill, W. Murray and M. A. Saunders, “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization,” SIAM Journal on Optimization, Vol. 12, No. 4, 2002, pp. 979-1006. doi:10.1137/S1052623499350013

[11] K. Schittkowski, “The Nonlinear Programming Method of Wilson, Han and Powell with an Augmented Lagrangian Type Line Search Function,” Numerische Mathematik, Vol. 38, No. 1, 1981, pp. 83-114. doi:10.1007/BF01395810

[12] S. Boyd and L. Vandenberghe, “Convex Optimization,” Cambridge University Press, Cambridge, 2004, pp. 241245.

[13] E. Anderson, Z. Bai and J. Dongarra, “Generalized QR Factorization and Its Application,” Linear Algebra and Its Applications, Vol. 162-164, 1992, pp. 243-271. doi:10.1016/0024-3795(92)90379-O

[14] P. E. Gill and W. Murray, “Numerically Stable Methods for Quadratic Programming,” Mathematical Programming, Vol. 14, No. 1, 1978, pp. 349-372. doi:10.1007/BF01588976

[15] M. OCW, “Positive Definite Matrices and Minima,” 2012. http://ocw.mit.edu/courses/mathematics/18-06sc-linear-algebra-fall-2011/positive-definite-matrices-and -applications/positive-definite-matrices-and-minima/MIT18_06SCF11_Ses3.3prob.pdf

[16] Wikipidia, “Positive-Definite Matrix,” 2012. http://en.wikipedia.org/wiki/Positive-definite_matrix

[17] R. A. Horn and C. R. Johnson, “Matrix Analysis,” Cambridge University Press, Cambridge, 1985.