betaFeedback

WorksMathematics

The regularization continuation method for optimization problems with nonlinear equality constraints

Abstract

This paper considers the regularization continuation method and the trust-region updating strategy for the nonlinearly equality-constrained optimization problem. Namely, it uses the inverse of the regularization quasi-Newton matrix as the pre-conditioner to improve its computational efficiency in the well-posed phase, and it adopts the inverse of the regularization two-sided projection of the Hessian as the pre-conditioner to improve its robustness in the ill-conditioned phase. Since it only solves a linear system of equations at every iteration and the sequential quadratic programming (SQP) needs to solve a quadratic programming subproblem at every iteration, it is faster than SQP. Numerical results also show that it is more robust and faster than SQP (the built-in subroutine fmincon.m of the MATLAB2020a environment and the subroutine SNOPT executed in GAMS v28.2 (2019) environment). The computational time of the new method is about one third of that of fmincon.m for the large-scale problem. Finally, the global convergence analysis of the new method is also given.

Mathematics Subject Classification (2010) 65K05 · 65L05 · 65L20 · 90C53

Introduction

In this article, we consider the optimization problem with nonlinear equality constraints as follows:

min⁡x∈Rnf(x)subject toc(x)=0,(1)\begin{aligned} \min_{x\in\mathfrak{R}^{n}}\quad&f(x)\\ \text{subject to}\quad&c(x)=0, \tag*{(1)} \end{aligned}

where f:Rn→Rf:\mathfrak{R}^{n}\to\mathfrak{R} and c:Rn→Rmc:\mathfrak{R}^{n}\to\mathfrak{R}^{m} (m≤nm\le n). This problem has many applications in engineering fields such as the visual-inertial navigation of an unmanned aerial vehicle maintaining the horizontal flight [11] [49], constrained sparse regression [8], sparse signal recovery [20, 83], image restoration and de-noising [21, 77] [57], the Dantzig selector [43], support vector machines [22], and sparse principal component analysis (PCA) methods [15, 86, 84]. And there are many practical methods [65] [38, 42] and many efficient solvers (the built-in subroutine fmincon [72] of MATLAB 2020a [60] and the subroutine SNOPT [29, 30] in the GAMS environment [23]) to solve it based on the sequential quadratic programming (SQP) method [31, 70, 85].

For the constrained optimization problem (1), the continuation method [3, 12, 24, 67, 80] [37] is another method other than the traditional optimization method such as SQP [31, 70, 71, 85] or the penalty function method [17]. The advantage of the continuation method over the SQP method is that the continuation method is capable of finding many local optimal points of the non-convex optimization problem by tracking its trajectory, and it is even possible to find the global optimal solution [6, 73, 87] [55]. However, the computational efficiency of the classical continuation methods is lower than that of the traditional optimization method such as SQP. Recently, Luo et al intensively investigate the continuation methods for nonlinear equations [50,53], linear programming problems [51], linear complementarity problems [56], unconstrained optimization problems [52,55], and linearly constrained optimization problems [49,54]. And they obtain the more robust and faster continuation methods than the traditional optimization methods.

Here, we extend their ideas to the optimization problem with nonlinear equality constraints. In order to improve the computational efficiency of the continuation method for the large-scale optimization problem further, we consider the regularization BFGS (a special quasi-Newton method) preconditioned technique for the regularization continuation method and use an adaptive time step control based on the trust-region updating strategy in this article. Moreover, in order to improve its robustness, we replace the inverse of the regularization BFGS matrix with the inverse of the regularization two-sided projection of the Hessian matrix in the ill-posed phase.

The rest of the paper is organized as follows. In Section 2, we give the regularization continuation method with the switching preconditioned technique and the trust-region updating strategy for the problem (1). In Section 3, we analyze the global convergence of this new method. In Section 4, we report some promising numerical results of the new method, in comparison to the state-of-art optimization methods (SQP, the built-in subroutine fmincon [72] of MATLAB 2020a [60] and the subroutine SNOPT [29, 30] in the GAMS environment [23]) for some large-scale problems. Finally, we give some discussions and conclusions in Section 5.

The regularization continuation method

In this section, we give the regularization continuation method with the switching preconditioned technique and the adaptive time-stepping scheme based on the trust-region updating strategy [13] for the optimization problem with nonlinear equality constraints. Firstly, we consider the regularized projection gradient flow based on the KKT conditions of equality-constrained optimization problems. Then, we construct the regularization continuation method with the trust-region updating strategy to follow this special ordinary differential equations (ODEs). The new method uses the Broyden-Fletcher-Goldfarb-Shanno (BFGS) updating formula [5, 18, 25, 76] as the preconditioned technique to improve its computational efficiency in the well-posed phase, and it adopts the inverse of the regularized two-sided projection Hessian as the pre-conditioner to improve its robustness in the ill-posed phase. Furthermore, we use the generalized continuation Newton method [53] to find an initial feasible point.

The regularized projection Newton flow

For the nonlinearly constrained optimization problem (1), it is well known that its optimal solution x∗x^* needs to satisfy the Karush-Kuhn-Tucker conditions (p. 328, [65]) as follows:

∇xL(x,λ)=∇f(x)+A(x)Tλ=0,(2)\nabla_x L(x,\lambda)=\nabla f(x)+A(x)^T\lambda=0, \tag*{(2)}
c(x)=0,(3)c(x)=0, \tag*{(3)}

where A(x)T=[∇c1(x),…,∇cm(x)]A(x)^T=[\nabla c_1(x),\ldots,\nabla c_m(x)] and the Lagrangian function L(x,λ)L(x,\lambda) is defined by

L(x,λ)=f(x)+λTc(x).(4)L(x,\lambda)=f(x)+\lambda^T c(x). \tag*{(4)}

Similarly to the method of the negative gradient flow for the unconstrained optimization problem [33], from the first-order necessary conditions (2)-(3), we can construct a dynamical system of differential-algebraic equations for problem (1) [14, 74] [46, 47, 48, 49, 54] as follows:

dxdt=−∇Lx(x,λ)=−(∇f(x)+A(x)Tλ),(5)\frac{dx}{dt}=-\nabla L_x(x,\lambda)=-(\nabla f(x)+A(x)^T\lambda), \tag*{(5)}
c(x)=0.(6)c(x)=0. \tag*{(6)}

By differentiating the algebraic constraint (6) with respect to tt and substituting it into the differential equation (5), we obtain

dc(x)dt=A(x)dxdt=−A(x)(∇f(x)+A(x)Tλ)=−A(x)∇f(x)−A(x)A(x)Tλ=0.(7)\frac{dc(x)}{dt}=A(x)\frac{dx}{dt}=-A(x)\left(\nabla f(x)+A(x)^{T}\lambda\right) = -A(x)\nabla f(x)-A(x)A(x)^{T}\lambda=0. \tag*{(7)}

If we assume that matrix A(x)A(x) has full row rank further, from equation (7), we obtain

λ=−(A(x)A(x)T)−1A(x)∇f(x).(8)\lambda=-\left(A(x)A(x)^{T}\right)^{-1}A(x)\nabla f(x). \tag*{(8)}

By substituting λ\lambda of equation (8) into equation (5), we obtain the projected gradient flow [80] for the constrained optimization problem (1) as follows:

dxdt=−(I−A(x)T(A(x)A(x)T)−1A(x))∇f(x)=−P(x)g(x),(9)\frac{dx}{dt}=-\left(I-A(x)^{T}\left(A(x)A(x)^{T}\right)^{-1}A(x)\right)\nabla f(x)=-P(x)g(x), \tag*{(9)}

where g(x)=∇f(x)g(x)=\nabla f(x) and the projection matrix P(x)P(x) is defined by

P(x)=I−A(x)T(A(x)A(x)T)−1A(x).(10)P(x)=I-A(x)^{T}\left(A(x)A(x)^{T}\right)^{-1}A(x). \tag*{(10)}

It is not difficult to verify (P(x))2=P(x)(P(x))^{2}=P(x). That is to say, the projection matrix P(x)P(x) is symmetric and its eigenvalues are 0 or 1. From Theorem 2.3.1 in p. 73 of [27], we know that its matrix 2-norm is

∥P(x)∥=1.(11)\lVert P(x)\rVert=1. \tag*{(11)}

We denote P(x)†P(x)^{\dagger} as the Moore-Penrose generalized inverse of the projection matrix P(x)P(x) (see p. 11, [79] or [64, 68]). Since the projection matrix P(x)P(x) is symmetric and (P(x))2=P(x)(P(x))^{2}=P(x), it is not difficult to verify

P(x)†=P(x).(12)P(x)^{\dagger}=P(x). \tag*{(12)}

Actually, from equation (12), we have P(x)(P(x))†P(x)=P(x)P(x)(P(x))^{\dagger}P(x)=P(x), P(x)†P(x)P(x)†=P(x)†P(x)^{\dagger}P(x)P(x)^{\dagger}=P(x)^{\dagger}, (P(x)†P(x))T=P(x)†P(x)(P(x)^{\dagger}P(x))^{T}=P(x)^{\dagger}P(x) and (P(x)P(x)†)T=P(x)P(x)†(P(x)P(x)^{\dagger})^{T}=P(x)P(x)^{\dagger}.

Remark 1 If x(t)x(t) is the solution of the ODE (9), it is not difficult to verify that x(t)x(t) satisfies A(x)(dx/dt)=0A(x)(dx/dt)=0. That is to say, if the initial point x0x_{0} satisfies c(x0)=0c(x_{0})=0, the solution x(t)x(t) of the projected gradient flow (9) also satisfies c(x)=0c(x)=0, ∀t≥0\forall t\geq0. This property is very useful such that we can construct an ODE method to follow the trajectory of the ODE (9) and obtain its steady-state solution x∗x^{*}.

If we assume that x(t)x(t) is the solution of the ODE (9), by using the property (P(x))2=P(x)(P(x))^{2}=P(x), we obtain

df(x)dt=(∇f(x))Tdxdt=−(∇f(x))TP(x)∇f(x)=−g(x)T(P(x))2g(x)=−∥P(x)g(x)∥2≤0.\frac{df(x)}{dt}=(\nabla f(x))^{T}\frac{dx}{dt}=-(\nabla f(x))^{T}P(x)\nabla f(x) =-g(x)^{T}(P(x))^{2}g(x)=-\lVert P(x)g(x)\rVert^{2}\leq0.

That is to say, f(x)f(x) is monotonically decreasing along the solution curve x(t)x(t) of the dynamical system (9). Furthermore, the solution x(t)x(t) converges to x∗x^{*} when f(x)f(x) is lower bounded and tt tends to infinity [33, 73, 80], where x∗x^{*} satisfies the first-order Karush-Kuhn-Tucker conditions (2)–(3). Thus, we can follow the trajectory x(t)x(t) of the ODE (9) to obtain its steady-state solution x∗x^{*}, which is also one stationary point of the original optimization problem (1).

However, since the right-hand-side function P(x)g(x)P(x)g(x) of the ODE (9) is rank-deficient, we will confront the numerical difficulties when we use the explicit ODE method to follow the projected gradient flow (9) [4, 7, 9]. In order to mitigate the stiffness of the ODE (9), we use the generalized inverse (P(x)∇2f(x)P(x))†(P(x)\nabla^{2}f(x)P(x))^{\dagger} of the two-sided projection matrix P(x)∇2f(x)P(x)P(x)\nabla^{2}f(x)P(x) as the pre-conditioner for the ODE (9), which is used similarly to the system of nonlinear equations [50], the unconstrained optimization problem [33] [52, 55], the linear programming problem [51], the linear complementarity problem [56], the underdetermined system of nonlinear equations [49,54] and the linearly constrained optimization problem [54].

By using the generalized inverse (P(x)∇2f(x)P(x))†(P(x)\nabla^{2}f(x)P(x))^{\dagger} of P(x)∇2f(x)P(x)P(x)\nabla^{2}f(x)P(x) as the pre-conditioner for the ODE (9), we obtain the projected Newton flow

dx(t)dt=−(P(x)∇2f(x)P(x))†P(x)g(x).(13)\frac{dx(t)}{dt}=-(P(x)\nabla^{2}f(x)P(x))^{\dagger}P(x)g(x). \tag*{(13)}

Since P(x)∇2f(x)P(x)P(x)\nabla^{2}f(x)P(x) is singular, we reformulate equation (13) as

(P(x)∇2f(x)P(x))dx(t)dt=−P(x)g(x).(14)(P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-P(x)g(x). \tag*{(14)}

Although the projected Newton flow (14) mitigates the stiffness of the ODE such that we can adopt the explicit ODE method to integrate it on the infinite interval, there are two disadvantages. One is that the two-side projection matrix P(x)∇2f(x)P(x)P(x)\nabla^{2}f(x)P(x) may be not positive semi-definite. Consequently, it can not ensure the objective function f(x)f(x) is monotonically decreasing along the solution x(t)x(t) of the ODE (14). The other is that the solution x(t)x(t) of the ODE (14) can not ensure to satisfy the feasibility, i.e., dc(x)/dt=A(x)dx(t)/dt=0dc(x)/dt=A(x)dx(t)/dt=0. In order to overcome these two shortcomings, we use the regularization technique [32, 81, 82] for the projected Newton flow (14) as follows:

(σ(x)I+P(x)∇2f(x)P(x))dx(t)dt=−P(x)g(x),(15)(\sigma(x)I+P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-P(x)g(x), \tag*{(15)}

where the regularization parameter σ(x)\sigma(x) satisfies σ(x)+μmin⁡(P(x)∇2f(x)P(x))≥σmin⁡>0\sigma(x)+\mu_{\min}(P(x)\nabla^{2}f(x)P(x))\geq\sigma_{\min}>0. Here, μmin⁡(B)\mu_{\min}(B) represents the smallest eigenvalue of matrix BB.

Remark 2 If we assume that x(t)x(t) is the solution of the ODE (15), from the property A(x)P(x)=0A(x)P(x)=0, we have

A(x)(σ(x)I+P(x)∇2f(x)P(x))dx(t)dt=−A(x)P(x)g(x)=0.A(x)(\sigma(x)I+P(x)\nabla^{2}f(x)P(x))\frac{dx(t)}{dt}=-A(x)P(x)g(x)=0.

Consequently, we obtain σ(x)A(x)dx(t)dt=0\sigma(x)A(x)\frac{dx(t)}{dt}=0, i.e. A(x)dx(t)dt=0A(x)\frac{dx(t)}{dt}=0. By integrating it, we obtain c(x)=c(x0)=0c(x)=c(x_0)=0. That is to say, the solution x(t)x(t) of the ODE (15) preserves the feasibility c(x)=0c(x)=0 when c(x0)=0c(x_0)=0. □\square

References

  1. [1]N. Andrei, An unconstrained optimization test functions collection, Adv Model Optim 10 (2008), 147-161.
  2. [3]E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, SIAM, Philadelphia, PA, 2003.DOI
  3. [4]U. M. Ascher and L. R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, Philadelphia, PA, 1998.DOI
  4. [5]C. G. Broyden, The convergence of a class of double-rank minimization algorithms, J Inst Math Appl 6 (1970), 76-90.
  5. [6]A. A. Brown and M. C. Bartholomew-Biggs, ODE versus SQP methods for constrained optimization, J Optim Theory Appl 62 (1989), 371-386.
  6. [7]K. E. Brenan, S. L. Campbell and L. R. Petzold, Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations, SIAM, Philadelphia, PA, 1996.DOI
  7. [8]J. M. Bioucas-Dias and M. A. T. Figueiredo, Alternating direction algorithms for constrained sparse regression: Application to hyperspectral unmixing, 2010 2nd Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing, 2010, 1-4, http://doi.org/10.1109/WHISPERS.2010.5594963.
  8. [9]J. C. Butcher, Z. Jackiewicz, Construction of high order diagonally implicit multistage integration methods for ordinary differential equations, Appl Numer Math 27 (1998), 1-12.DOI
  9. [11]F. Caballero, L. Merino, J. Ferruz and A. Ollero, Vision-based odometry and SLAM for medium and high altitude flying UAVs, J Intell Robot Syst 54 (2009), 137-161.
  10. [12]T. S. Coffey, C. T. Kelley and D. E. Keyes, Pseudotransient continuation and differential-algebraic equations, SIAM J Sci Comput 25 (2003), 553-569.
  11. [13]A. R. Conn, N. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, Philadelphia, USA, 2000.DOI
  12. [14]M. T. Chu and M. Lin, Dynamical system characterization of the central path and its variants-a revisit, SIAM J Appl Dyn Syst 10 (2011), 887-905.DOI
  13. [15]A. d’Aspremont, L. El Ghaoui, M. Jordan, G. R. Lanckriet, A direct formulation for sparse PCA using semidefinite programming, SIAM Rev 49 (2007), 434-448.
  14. [16]E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math Program 91 (2002), 201-213.DOI
  15. [17]A. V. Fiacco and G. P. McCormick, Nonlinear programming: Sequential Unconstrained Minimization Techniques, SIAM, 1990.
  16. [18]R. Fletcher, A new approach to variable metric algorithms, Comput J 13 (1970), 317-322.DOI
  17. [19]R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput J 6 (1963), 163-168.DOI
  18. [20]J. M. Fadili, J. L. Starck, Monotone operator splitting for optimization problems in sparse recovery, IEEE ICIP, Nov 2009, Cairo, Egypt., 1461-1464, http://doi.org/10.1109/ICIP.2009.5414555.
  19. [21]M. A. T. Figueiredo and J. M. Bioucas-Dias, Restoration of Poissonian images using alternating direction optimization, IEEE Trans Image Process 19 (2010), 3133-3145.
  20. [22]P. A. Forero, A. Cano and G. B. Giannakis, Consensus-based distributed support vector machines, J Mach Learn Res 11 (2010), 1663-1707.
  21. [23]GAMS v28.2, GAMS Corporation, https://www.gams.com/, 2019.
  22. [24]B. S. Goh, Approximate greatest descent methods for optimization with equality constraints, J Optim Theory Appl 148 (2011), 505-527.DOI
  23. [25]D. Goldfarb, A family of variable metric updates derived by variational means, Math Comput 24 (1970), 23-26.DOI
  24. [26]N. I. M. Gould, D. Orban and P. L. Toint, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput Optim Appl 60 (2015), 545-557.DOI
  25. [27]G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, Maryland, 2013.
  26. [29]P. E. Gill, W. Murray and M. A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Rev 47, (2005), 99-131.
  27. [30]P. E. Gill, W. Murray and M. A. Saunders, User’s guide for SQOPT Version 7: Software for large-scale linear and quadratic programming, 2006.
  28. [31]S. P. Han, A globally convergent method for nonlinear programming, J Optim Theory Appl 22 (1977), 297-307.DOI
  29. [32]P. C. Hansen, Regularization Tools: A MATLAB package for analysis and solution of discrete ill-posed problems, Numer Algorithms 6 (1994), 1-35.DOI
  30. [33]U. Helmke and J. B. Moore, Optimization and Dynamical Systems, 2nd ed., Springer-Verlag, London, 1996.
  31. [34]D. J. Higham, Trust region algorithms and timestep selection, SIAM J Numer Anal 37 (1999), 194-210.DOI
  32. [60]MATLAB v9.8.0 (R2020a), The MathWorks Inc., http://www.mathworks.com, 2020.
  33. [61]J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Trans Math Softw 7 (1981), 17-41.
  34. [62]D. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, SIAM J Appl Math 11 (1963), 431-441.DOI
  35. [64]E. H. Moore, On the reciprocal of the general algebraic matrix, Bull New Ser Am Math Soc 26 (1920), 394-395.
  36. [65]J. Nocedal and S. J. Wright, Numerical Optimization, Springer-Verlag, Berlin, 1999.
  37. [67]P.-Q. Pan, New ODE methods for equality constrained optimization (2): algorithms, J Comput Math 10 (1992), 129-146.DOI
  38. [68]R. A. Penrose, Generalized inverses for matrices, Math Proc Camb Philos Soc 51 (1955), 406-413.
  39. [69]M. J. D. Powell, Convergence properties of a class of minimization algorithms, in: O.L. Mangasarian, R. R. Meyer and S. M. Robinson, eds., Nonlinear Programming 2, Academic Press, New York, pp. 1-27, 1975.DOI
  40. [70]M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in: G. A. Watson, eds., Numerical Analysis, Springer-Verlag, Berlin, pp. 144-157, 1978.DOI
  41. [71]M. J. D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations in: O.L. Mangasarian, R. R. Meyer and S. M. Robinson, eds., Nonlinear Programming 3, Academic Press, New York, pp. 27-63, 1978.DOI
  42. [72]K. Schittkowski, NLPOPL: A fortran subroutine solving constrained nonlinear programming problems, Ann Oper Res 5 (1986), 485-500, available at https://doi.org/10.1007/BF02739235.
  43. [73]J. Schropp, A dynamical systems approach to constrained minimization, Numer Funct Anal Optim 21 (2000), 537-551.DOI
  44. [74]J. Schropp, One and multistep discretizations of index 2 differential algebraic systems and their use in optimization, J Comput Appl Math 150 (2003), 375-396.DOI
  45. [75]L. F. Shampine, I. Gladwell and S. Thompson, Solving ODEs with MATLAB, Cambridge University Press, Cambridge, 2003.DOI
  46. [76]D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Math Comput 24 (1970), 647-656.DOI
  47. [77]G. Steidl and T. Teuber, Removing multiplicative noise by Douglas-Rachford splitting methods, J Math Imaging Vis 36 (2010), 168-184.DOI
  48. [78]S. Surjanovic and D. Bingham, Virtual library of simulation experiments: Test functions and datasets, retrieved from http://www.sfu.ca/~ssurjano, January 2020.
  49. [79]W. Y. Sun and Y. X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.
  50. [80]K. Tanabe, A geometric method in nonlinear programming, J Optim Theory Appl 30 (1980), 181-210.DOI
  51. [81]A. N. Tikhonov, The stability of inverse problems, Dokl Akad Nauk USSR 39 (1943), 176-179.
  52. [82]A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed Problems, John Wiley & Sons, New York- Toronto-London, 1977.DOI
  53. [83]R. Vanderbei, K. Lin, H. Liu and L. Wang, Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods, Math Prog Comp 8 (2016), 253-269, http://doi.org/10. 1007/s12532-016-0105-y.
  54. [84]Z.-W. Wen and W.-T. Yin, A feasible method for optimization with orthogonality constraints, Math Program 142 (2013), 397-434.DOI
  55. [85]R. B. Wilson, A Simplicial Method for Convex Programming, Ph.D. thesis, Harvard University, 1963.
  56. [86]D. M. Witten, R. Tibshirani and T. Hastie, A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis, Biostatistics 10 (2009), 515-534.DOI
  57. [87]H. Yamashita, A differential equation approach to nonlinear programming, Math Program 18 (1980), 155-168.DOI
  58. [88]Y. Yuan, Recent advances in trust region algorithms, Math Program 151 (2015), 249-281.DOI

Paper details

vlnc:W_732hvgaj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents