×

Computing the signed distance between overlapping ellipsoids. (English) Zbl 1334.49100

The authors deal with the computing problem for the signed distance between two ellipsoids \(E_i=E(b_i,A_i),\;i=1,2\). It is defined by \[ \text{dist}(E_1,E_2)=\max_{\|w\|=1}\left(\langle w,b_1\rangle-\sqrt{\langle w,A_1w\rangle} -\langle w,b_2\rangle-\sqrt{\langle w,A_1w\rangle}\right) \] with \(\langle\cdot,\cdot\rangle\) the inner product in \(\mathbb{R}^n\). It coincides with the typical distance of two sets in the case of nonoverlapping ellipsoids. In the overlapping case the problem of computing the signed distance is nonconvex. The authors show that it is equivalent to minimizing the norm along the boundary of the Minkowski difference. They derive the Karush-Kuhn-Tucker conditions and then identify the smallest KKT point with the smallest signed distance. The problem is reduced to a two-parameter quadratic eigenvalue problem. The paper provides the first algorithm for computing the signed distance between overlapping ellipsoids with polynomial complexity.

MSC:

49M37 Numerical methods based on nonlinear programming
49M05 Numerical methods based on necessary conditions
90C30 Nonlinear programming
90C25 Convex programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] W. Ai and S. Zhang, {\it Strong duality for the CDT subproblem: A necessary and sufficient condition}, SIAM J. Optim., 19 (2009), pp. 1735-1756. · Zbl 1187.90290
[2] F. V. Atkinson, {\it Multiparameter Eigenvalue Problems}, Academic Press, New York, London, 1972. · Zbl 0555.47001
[3] C. Bhattacharyya, {\it Second order cone programming formulations for feature selection}, J. Mach. Learn. Res., 5 (2003/04), pp. 1417-1433. · Zbl 1222.68147
[4] D. Bienstock, {\it A Note on Polynomial Solvability of the CDT Problem}, preprint, arXiv:1406.6429, 2015. · Zbl 1382.90083
[5] D. A. Bini and A. Marco, {\it Computing curve intersection by means of simultaneous iterations}, Numer. Algorithms, 43 (2006), pp. 151-175. · Zbl 1111.65019
[6] I. M. Bomze and M. L. Overton, {\it Narrowing the difficulty gap for the Celis-Dennis-Tapia problem}, Math. Program. Ser. B, 151 (2015), pp. 459-476. · Zbl 1328.90095
[7] S. P. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[8] W. Briec, {\it Minimum distance to the complement of a convex set: Duality result}, J. Optim. Theory Appl., 93 (1997), pp. 301-319. · Zbl 0901.90157
[9] M. R. Celis, J. E. Dennis, and R. A. Tapia, {\it A trust region strategy for nonlinear equality constrained optimization}, in Numerical Optimization, P. T. Boggs, R. H. Byrd, and R. B. Schnabel, eds., SIAM, Philadelphia, 1985, pp. 71-82. · Zbl 0566.65048
[10] J. Demmel and B. K\aagström, {\it The generalized Schur decomposition of an arbitrary pencil \(A- γ B\): Robust software with error bounds and applications. {\it I}. Theory and algorithms}, ACM Trans. Math. Software, 19 (1993), pp. 160-174. · Zbl 0889.65042
[11] M. El-Alem, {\it A global convergence theory for the Celis-Dennis-Tapia trust-region algorithm for constrained optimization}, SIAM J. Numer. Anal., 28 (1991), pp. 266-290. · Zbl 0725.65061
[12] G. E. Forsythe and G. H. Golub, {\it On the stationary values of a second-degree polynomial on the unit sphere}, J. Soc. Indust. Appl. Math., 13 (1965), pp. 1050-1068. · Zbl 0168.03005
[13] I. Gohberg, P. Lancaster, and L. Rodman, {\it Matrix Polynomials}, SIAM, Philadelphia, 2009. \newblock Unabridged republication of book first published by Academic Press in 1982. · Zbl 0482.15001
[14] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 4th ed., The Johns Hopkins University Press, Baltimore, 2012. · Zbl 1268.65037
[15] N. J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, 2nd ed., SIAM, Philadelphia, 2002. · Zbl 1011.65010
[16] M. E. Hochstenbach, A. Muhič, and B. Plestenjak, {\it On linearizations of the quadratic two-parameter eigenvalue problem}, Linear Algebra Appl., 436 (2012), pp. 2725-2743. · Zbl 1245.65042
[17] S. Iwata, Y. Nakatsukasa, and A. Takeda, {\it Global optimization methods for extended Fisher discriminant analysis}, in Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS), JMLR W&CP 33, 2014, pp. 411-419.
[18] E. Jarlebring and M. E. Hochstenbach, {\it Polynomial two-parameter eigenvalue problems and matrix pencil methods for stability of delay-differential equations}, Linear Algebra Appl., 431 (2009), pp. 369-380. · Zbl 1170.65063
[19] A. A. Kurzhanskiy and P. Varaiya, {\it Ellipsoidal Toolbox}, Tech. Report UCB/EECS-2006-46, Electrical Engineering and Computer Sciences, UC Berkeley, Berkeley, CA, 2006.
[20] L. Lerer and M. Tismenetsky, {\it The Bézoutian and the eigenvalue-separation problem for matrix polynomials}, Integral Equations Operator Theory, 5 (1982), pp. 386-445. · Zbl 0504.47020
[21] A. Lin and S.-P. Han, {\it On the distance between two ellipsoids}, SIAM J. Optim., 13 (2002), pp. 298-308. · Zbl 1027.49026
[22] J. M. Martínez, {\it Local minimizers of quadratic functions on Euclidean balls and spheres}, SIAM J. Optim., 4 (1994), pp. 159-176. · Zbl 0801.65057
[23] A. Muhič and B. Plestenjak, {\it On the quadratic two-parameter eigenvalue problem and its linearization}, Linear Algebra Appl., 432 (2010), pp. 2529-2542. · Zbl 1189.65070
[24] Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Computing the common zeros of two bivariate functions via Bézout resultants}, Numer. Math., 129 (2015), pp. 181-209. · Zbl 1308.65076
[25] J. S. Nath and C. Bhattacharyya, {\it Maximum margin classifiers with specified false positive and false negative error rates}, in Proceedings of the 2007 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2007, pp. 35-46.
[26] L. Nirenberg, {\it Functional Analysis}, Literary Licensing, LLC, 1961.
[27] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[28] V. Noferini, \newblock{\it private communication}, University of Manchester, UK, 2013.
[29] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[30] A. Takeda, H. Mitsugi, and T. Kanamori, {\it A unified classification model based on robust optimization}, Neural Comput., 25 (2013), pp. 759-804. · Zbl 1269.68085
[31] F. Tisseur and K. Meerbergen, {\it The quadratic eigenvalue problem}, SIAM Rev., 43 (2001), pp. 235-286. · Zbl 0985.65028
[32] C. Uhler and S. J. Wright, {\it Packing ellipsoids with overlap}, SIAM Rev., 55 (2013), pp. 671-706. · Zbl 1282.90124
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.