Unconstrained Reformulation of Sequential Quadratic Programming for Solving Optimization Problems With Linear Equality Constraints
DOI:
https://doi.org/10.2298/YJOR251015011CKeywords:
Sequential quadratic programming, constrained optimization, unconstrained reformulation, convex optimization, local minimum pointAbstract
In this paper, we propose an alternative approach to Sequential Quadratic Programming (SQP) for solving optimization problems with linear equality constraints. The concept of a regularized gap function is employed to reformulate the constrained problem into an unconstrained one. The proposed algorithm incorporates a positive definite Hessian modification along with a backtracking line search to promote global convergence. Its effectiveness is demonstrated through several numerical experiments and geometric illustrations. Furthermore, applications of the proposed method are explored in optimal allocation, analytic center computation, and network flow problems.
References
J. Nocedal and S.J. Wright, Numerical Optimization, 2nd ed. New York: Springer, 2006.
R.B. Wilson,“A simplicial algorithm for concave programming, ”PhD Dissertation, Harvard University, 1963.
J.S. Alsumait, J.K. Sykulski, and A.K. Al-Othman, “A hybrid ga-ps-sqp method to solve power system valve-point economic dispatch problems, ”Applied Energy, vol. 87, no. 5, pp. 1773–1781, 2010.
S. K. Chakraborty and G. Panda, “Two-phase-sqp method with higher-order convergence property,” Journal of the Operations Research Society of China, vol. 4, no. 3, pp. 385–396, 2016.
F. E. Curtis, T. Mitchell, and M. L. Overton, “A bfgs-sqp method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles,” Optimization Methods and Software, vol. 32, no. 1, pp. 148–181, 2017.
P. E. Gill, V. Kungurtsev, and D. P. Robinson, “A stabilized sqp method: Global convergence,” IMA Journal of Numerical Analysis, vol. 37, no. 1, pp. 407–443, 2017.
A. F. Izmailov and M. V. Solodov, “Stabilized sqp revisited,” Mathematical Programming, vol. 133, no. 1-2, pp. 93–120, 2012.
P. T. Boggs and J. W. Tolle, “Sequential quadratic programming,” Acta Numerica, vol. 4, pp. 1–51, 1995.
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, pp. 1376–1395, 2001.
N. I. M. Gould and D. P. Robinson, “A second derivative sqp method: Global convergence,” SIAM Journal on Optimization, vol. 20, no. 4, pp. 2023–2048, 2010.
M. Fukushima, “Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,” Mathematical Programming, vol. 53, no. 1-3, pp. 99–110, 1992.
G. Auchmuty, “Variational principles for variational inequalities,” Numerical Functional Analysis and Optimization, vol. 10, no. 9-10, pp. 863–874, 1989.
A. Auslender, “Optimisation,” M´ethodes num´eriques, 1976.
T. Larsson and M. Patriksson, “A class of gap functions for variational inequalities,” Mathematical Programming, vol. 64, no. 1-3, pp. 53–79, 1994.
M. Pappalardo, G. Mastroeni, and M. Passacantando, “Merit functions: a bridge between optimization and equilibria,” 4OR, vol. 12, no. 1, pp. 1–33, 2014.
W. Li and J. Peng, “Exact penalty functions for constrained minimization problems via regularized gap function for variational inequalities,” Journal of Global Optimization, vol. 37, no. 1, pp. 85–94, 2007.
R. Sadhu and C. Nahak, “An exact convex reformulation of the quadratic programming,” Journal of Advanced Mathematical Studies, vol. 12, no. 2, pp. 230–239, 2019.
R. Sadhu, C. Nahak, and S. P. Dash, “Unconstrained reformulation of sequential quadratic programming and its application in convex optimization,” Proceedings of Indo-French Seminar, 2020.
P. T. Harker and J. S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,” Mathematical Programming, vol. 48, no. 1-3, pp. 161–220, 1990.
A. Beck, Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. SIAM,2014.
J. R. Bunch, L. Kaufman, and B. N. Parlett, “Decomposition of a symmetric matrix,” Numerische Mathematik, vol. 27, no. 1, pp. 95–109, 1976.
I. S. Duff and J. K. Reid, “The multifrontal solution of indefinite sparse symmetric linear,” ACMTransactions on Mathematical Software, vol. 9, no. 3, pp. 302–325, 1983.
R. Fourer and S. Mehrotra, “Solving symmetric indefinite systems in an interior-point method for linear programming,” Mathematical Programming, vol. 62, no. 1-3, pp. 15–39, 1993.
F. E. Curtis, T. Mitchell, and M. L. Overton, “A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization,” SIAM Journal on Optimization, vol. 22, no. 2, pp. 474–500, 2012.
M. Rashidi and M. Soleimani-Damaneh, “An exact penalty method with nonmonotone line search and rapid infeasibility detection for constrained multiobjective optimization: Application in supervised machine learning,” Computers & Operations Research, vol. 188, p. 107351, 2026.
——, “MultiSQP-GS: A sequential quadratic programming algorithm via gradient sampling for nonsmooth constrained multiobjective optimization,” Computational Optimization and Applications, vol. 89, no. 3, pp. 729–767, 2024.
S. Surjanovic and D. Bingham, “Virtual library of simulation experiments: Test functions and datasets,” 2020, retrieved December 29, 2020 from http://www.sfu.ca/ ssurjano.
Y. X. Yuan, “Subspace techniques for nonlinear optimization,” Some Topics in Industrial and Applied Mathematics, vol. 2007, pp. 206–218, 2007.
J. H. Lee, Y.M. Jung, Y.Z. Yuan, and S. Yun, “A subspace sqp method for equality constrained optimization,” Computational Optimization and Applications, vol. 74, no. 1, pp. 177–194, 2019.
E. D. Dolan and J. J. Mor´e, “Benchmarking optimization software with performance profiles,” Mathematical Programming, vol. 91, no. 2, pp. 201–213, 2002.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Yugoslav Journal of Operations Research
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
