×

zbMATH — the first resource for mathematics

A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints. (English) Zbl 1382.90082
Summary: We suggest a branch and bound algorithm for solving continuous optimization problems where a (generally nonconvex) objective function is to be minimized under nonconvex inequality constraints which satisfy some specific solvability assumptions. The assumptions hold for some special cases of nonconvex quadratic optimization problems. We show how the algorithm can be applied to the problem of minimizing a nonconvex quadratic function under ball, out-of-ball and linear constraints. The main tool we utilize is the ability to solve in polynomial computation time the minimization of a general quadratic under one Euclidean sphere constraint, namely the so-called trust region subproblem, including the computation of all local minimizers of that problem. Application of the algorithm on sparse source localization problems is presented.

MSC:
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
SCIP; GQTPAR; CVX; QuadProgBB
PDF BibTeX Cite
Full Text: DOI
References:
[1] Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: a new approach to integrate cp and mip. ZIB-Report 08-01 (2008) · Zbl 1142.68504
[2] Beck, A; Eldar, YC, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17, 844-860, (2006) · Zbl 1128.90044
[3] Beck, A; Stoica, P; Li, J, Exact and approximate solutions of source localiztaion problems, IEEE Trans. Signal Process., 56, 1770-1778, (2008) · Zbl 1390.94091
[4] Beck, A; Teboulle, M, A fast iterative shrinkage-thresholding algorithm for linear invers problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[5] Beck, A; Teboulle, M; Chikishev, Z, Exact and approximate solutions of source localiztaion problems, IEEE Trans. Signal Process., 56, 1770-1778, (2008) · Zbl 1390.94091
[6] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[7] Bienstock, D., Michalka, A.: Polynomial solvability of variants of the trust-region subproblem. In: SODA, pp. 380-390 (2014) · Zbl 1334.90130
[8] Bruckstein, AM; Donoho, DL; Elad, M, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 34-81, (2009) · Zbl 1178.68619
[9] Burer, S., Anstreicher, K.: Second-order cone constraints for extended trust-region subproblems. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52242, (2011) · Zbl 1298.90062
[10] Burer, S., Yang, B.: The Trust Region Subproblem with Non-intersecting Linear Constraints, Manuscript. University of Iowa, Iowa City (2013) · Zbl 1308.90121
[11] Chen, J; Burer, S, Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 33-52, (2012) · Zbl 1257.90065
[12] Cheung, K.W., Ma, W.K., So, H.C.: Accurate approximation algorithm for toa-based maximum likelihood mobile location using semidefinite programming. In: Proceedings of ICASSP, vol. 2, pp. 145-148 (2004)
[13] Gay, DM, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 186-197, (1981) · Zbl 0467.65027
[14] Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences, pp. 95-110. Springer, Berlin (2008). http://stanford.edu/ boyd/graph_dcp.html · Zbl 1205.90223
[15] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1, (March 2014) http://cvxr.com/cvx · Zbl 1390.94091
[16] Hsia, Y., Sheu, R.L.: Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity (2013). arXiv:1312.1398
[17] Jeyakumar, V; Li, GY, Trust-region problems with linear inequality constraints: exact sdp relaxation, global optimality and robust optimization, Math. Program. Ser. A, 147, 171-206, (2014) · Zbl 1297.90105
[18] Martínez, JM, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 159-176, (1994) · Zbl 0801.65057
[19] Moré, JJ, Generalizations of the trust region subproblem, Optim. Methods Softw., 2, 189-209, (1993)
[20] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[21] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Berlin (2000) · Zbl 1104.65059
[22] Sorensen, DC, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19, 409-426, (1982) · Zbl 0483.65039
[23] Sturm, J; Zhang, S, On cones of nonnegative quadratic functions, Math. Oper. Res., 288, 246-267, (2003) · Zbl 1082.90086
[24] Ye, Y; Zhang, S, New results on quadratic minimization, SIAM J. Optim., 14, 245-267, (2003) · Zbl 1043.90064
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.