×

The solution of Euclidean norm trust region SQP subproblems via second-order cone programs: an overview and elementary introduction. (English) Zbl 1398.90206

Summary: It is well known that convex sequential quadratic programming (SQP) subproblems with an Euclidean norm trust region constraint can be reduced to second-order cone programs for which the theory of Euclidean Jordan algebras leads to efficient interior-point algorithms. Here, a brief and self-contained outline of the principles of such an implementation is given and the application to SQP subproblems as well as to cubic regularization problems is discussed. All identities relevant for the implementation are derived from scratch and are compared to interior-point methods for linear programs (LPs). Sparsity of the data of the SQP subproblem can be maintained essentially in the same way as for interior-point methods for LPs. The presentation is intended as an introduction for students and for colleagues who may have heard about Jordan algebras but did not yet find the time to get involved with them. A simple Matlab implementation is made available and the discussion of implementational aspects addresses a scaling property that is critical for SQP subproblems.

MSC:

90C55 Methods of successive quadratic programming type
90C51 Interior-point methods

Software:

Matlab; SDPT3; ECOS; GQTPAR; SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ai, W. B.; Zhang, S. Z., Strong duality for the CDT subproblem: A necessary and sufficient condition, SIAM J. Optim., 19, 1735-1756 (2009) · Zbl 1187.90290 · doi:10.1137/07070601X
[2] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Prog., 95, 3-51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[3] Alizadeh, F.; Haeberly, J.-P.; Overton, M. L., Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Opt., 8, 746-768 (1998) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[4] Ben-Tal, A.; Nemirovskii, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (2001) · Zbl 0986.90032
[5] Bienstock, D., A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26, 1, 488-498 (2016) · Zbl 1382.90083 · doi:10.1137/15M1009871
[6] Boyd, S.; Vandenberghe, L., Convex Optimization (PDF) (2004), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1058.90049
[7] Calafiore, G. C.; El Ghaoui, L., Optimization Models (2014), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1342.90001
[8] Coralia, C.; Gould, N. I.M.; Toint, P. L., Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program., 127, 245-295 (2011) · Zbl 1229.90192 · doi:10.1007/s10107-009-0286-5
[9] Celis, M., Dennis, J., and Tapia, R., A trust region strategy for nonlinear equality constrained optimization, in Numerical Optimization, P. Boggs, R. Byrd, and R. Schnabel, eds., SIAM, Philadelphia, 1985, 71-82. · Zbl 0566.65048
[10] Chen, X. D.; Yuan, Y.-X., On local solutions of the Celis-Dennis-Tapia subproblem, SIAM J. Optim., 10, 359-383 (1999) · Zbl 0957.65060 · doi:10.1137/S1052623498335018
[11] Conn, A. R.; Gould, N. I.M.; Toint, Ph. L., Trust-Region Methods (2000), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0809.65066
[12] Domahidi, A., Chu, E., and Boyd, S., ECOS: An SOCP solver for embedded systems, in Proceedings European Control Conference, Zurich, Switzerland, July 2013, pp. 3071-3076.
[13] Faraut, J.; Koranyi, A., Analysis on Symmetric Cones (1994), The Clarendon Press, Oxford University Press, Oxford Science Publications: The Clarendon Press, Oxford University Press, Oxford Science Publications, New York · Zbl 0841.43002
[14] Faybusovich, L., Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86, 1, 149-175 (1997) · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2
[15] Faybusovich, L., Euclidean Jordan algebras and interior-point algorithms, Positivity, 1, 4, 331-357 (1997) · Zbl 0973.90095 · doi:10.1023/A:1009701824047
[16] Fletcher, R., A model algorithm for composite non-differentiable optimization problems, Math. Program. Stud., 17, 67-76 (1982) · Zbl 0478.90063 · doi:10.1007/BFb0120959
[17] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Prog., 91, 239-269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[18] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman and Co.: W. H. Freeman and Co., San Francisco, CA · Zbl 0411.68039
[19] Goldsmith, M., Sequential quadratic programming methods based on indefinite hessian approximations, PhD thesis, Stanford University, 1999.
[20] Gould, N.I.M., An introduction to algorithms for continuous optimization, Report, Oxford University Computing Laboratory and Rutherford Appleton Laboratory, 2006, Available at .
[21] Griewank, A., The modification of Newton’s method for unconstrained optimization by bounding cubic terms, Technical report NA/12, Department of Applied Mathematical and Theoretical Physics, University of Cambridge, UK, 1981. doi: .
[22] Griewank, A.; Fischer, J.; Bosse, T., Cubic overestimation and secant updating for unconstrained optimization of C-2,C-1 functions, Optim. Methods Softw., 29, 5, 1075-1089 (2014) · Zbl 1306.90150 · doi:10.1080/10556788.2013.863308
[23] Gu, G.; Zangiabadi, M.; Roos, C., Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, Eur. J. Oper. Res., 214, 3, 473-484 (2011) · Zbl 1245.90144 · doi:10.1016/j.ejor.2011.02.022
[24] Jarre, F., MWD, smooth minimization without using derivatives, a Matlab collection, 2015, Available at .
[25] Jarre, F., A priori bounds on the condition numbers in interior-point methods, 2015, Available at .
[26] Lobo, M. S.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[27] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 4, 575-601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[28] Monteiro, R. D.C.; Tsuchiya, T., Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Math. Prog., 88, 61-83 (2000) · Zbl 0967.65077 · doi:10.1007/PL00011378
[29] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 553-572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[30] Muramatsu, M.; Vanderbei, R. J., Primal-dual affine-scaling algorithms fail for semidefinite programming, Math. Oper. Res., 24, 1, 149-175 (1999) · Zbl 0977.90033 · doi:10.1287/moor.24.1.149
[31] Nesterov, Y. E.; Nemirovskii, A. S., Interior-Point Polynomial Algorithms in Convex Programming (1993), SIAM: SIAM, Philadelphia, PA · Zbl 0824.90112
[32] Nesterov, Y. E.; Polyak, B. T., Cubic regularization of Newton method and its global performance, Math. Program., 108, 177-205 (2006) · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8
[33] Nesterov, Y. E.; Todd, M. J., Self-scaled barriers and interior-point methods for convex programming, Math. OR, 22, 1-42 (1997) · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[34] Nesterov, Y. E.; Todd, M. J., Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim, 8, 2, 324-364 (1998) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[35] Omojokun, E.O., Trust region algorithms for optimization with nonlinear equality and inequality constraints, Doctoral Dissertation, University of Colorado at Boulder Boulder, CO, 1989.
[36] Peng, J.-M.; Yuan, Y.-X., Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 579-594 (1997) · Zbl 0891.90150 · doi:10.1137/S1052623494261520
[37] Poljak, S.; Rendl, F., Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Optim., 5, 3, 467-487 (1995) · Zbl 0838.90130 · doi:10.1137/0805024
[38] Powell, M. J.D.; Yuan, Y., A trust region algorithm for equality constrained optimization, Math. Program., 49, 189-211 (1990) · Zbl 0816.90121 · doi:10.1007/BF01588787
[39] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12, 625-653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[40] Sturm, J. F.; Zhang, S. Z., On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 246-267 (2003) · Zbl 1082.90086 · doi:10.1287/moor.28.2.246.14485
[41] Tsuchiya, T., A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optim. Methods Softw., 11 and 12, 141-182 (1999) · Zbl 0957.90129 · doi:10.1080/10556789908805750
[42] Tutuncu, R. H.; Toh, K. C.; Todd, M. J., On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optim., 8, 3, 769-796 (1998) · Zbl 0913.90217 · doi:10.1137/S105262349630060X
[43] Tutuncu, R. H.; Toh, K. C.; Todd, M. J., Solving semidefinite-quadratic-linear programs using SDPT3, Math. Programm. Ser. B, 95, 189-217 (2003) · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5
[44] Vardi, A., A trust region algorithm for equality constrained minimization: Convergence properties and implementation, SIAM J. Num. Anal., 22, 575-591 (1985) · Zbl 0581.65045 · doi:10.1137/0722035
[45] Wright, S. J., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM, Philadelphia, PA · Zbl 0863.65031
[46] Yuan, Y., On a subproblem of trust region algorithms for constrained optimization, Math. Program, 47, 53-63 (1990) · Zbl 0711.90062 · doi:10.1007/BF01580852
[47] Yuan, Y., A dual algorithm for minimizing a quadratic function with two quadratic constraints, J. Comput. Math., 9, 348-359 (1991) · Zbl 0758.65050
[48] Yuan, Y.-X., On the convergence of a new trust region algorithm, Numer. Math., 70, 515-539 (1995) · Zbl 0828.65062 · doi:10.1007/s002110050133
[49] Yuan, Y.-X., Recent advances in trust region algorithms, Math. Program., 151, 249-281 (2015) · Zbl 1317.65141 · doi:10.1007/s10107-015-0893-2
[50] Zhang, Y., Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization, Math. Program., 55, 109-124 (1992) · Zbl 0773.90056 · doi:10.1007/BF01581194
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.