Top

Neural Computing and Applications

Published in:

20-04-2019 | Original Article

Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition

Authors: Anh-Huy Phan, Masao Yamagishi, Danilo Mandic, Andrzej Cichocki

Published in: Neural Computing and Applications | Issue 11/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A novel algorithm to solve the quadratic programming (QP) problem over ellipsoids is proposed. This is achieved by splitting the QP problem into two optimisation sub-problems, (1) quadratic programming over a sphere and (2) orthogonal projection. Next, an augmented-Lagrangian algorithm is developed for this multiple constraint optimisation. Benefitting from the fact that the QP over a single sphere can be solved in a closed form by solving a secular equation, we derive a tighter bound of the minimiser of the secular equation. We also propose to generate a new positive semidefinite matrix with a low condition number from the matrices in the quadratic constraint, which is shown to improve convergence of the proposed augmented-Lagrangian algorithm. Finally, applications of the quadratically constrained QP to bounded linear regression and tensor decomposition paradigms are presented.

previous article Antlion optimization algorithm for pairwise structural alignment with bi-objective functions

next article Design of nature-inspired heuristic paradigm for systems in nonlinear electrical circuits

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Anandkumar A, Ge R, Hsu D, Kakade S, Telgarsky M (2014) Tensor decompositions for learning latent variable models. J Mach Learn Res 15:2773–2832MathSciNetMATH

ApS M (2015) The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28). http://docs.mosek.com/7.1/toolbox/index.html

Arima N, Kim S, Kojima M (2013) A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J Optim 23(4):2320–2340. https://doi.org/10.1137/120890636 MathSciNetCrossRefMATH

Bao X, Sahinidis NV, Tawarmalani M (2011) Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math Program 129(1):129. https://doi.org/10.1007/s10107-011-0462-2 MathSciNetCrossRefMATH

Baron DP (1972) Quadratic programming with quadratic constraints. Naval Res Logist Q 19(2):253–260MathSciNetCrossRef

Ben X, Zhang P, Yan R, Yang M, Ge G (2016) Gait recognition and micro-expression recognition based on maximum margin projection with tensor representation. Neural Comput Appl 27(8):2629–2646. https://doi.org/10.1007/s00521-015-2031-8 CrossRef

Ben-Tal A, Teboulle M (1996) Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math Program 72(1):51–63. https://doi.org/10.1007/BF02592331 MathSciNetCrossRefMATH

Biswas P, Lian TC, Wang TC, Ye Y (2006) Semidefinite programming based algorithms for sensor network localization. ACM Trans Sen Netw 2(2):188–220. https://doi.org/10.1145/1149283.1149286 CrossRef

Bose S, Gayme DF, Chandy KM, Low SH (2015) Quadratically constrained quadratic programs on acyclic graphs with application to power flow. IEEE Trans Control Netw Syst 2(3):278–287. https://doi.org/10.1109/TCNS.2015.2401172 MathSciNetCrossRefMATH

10.

Boumal N, Mishra B, Absil PA, Sepulchre R (2014) Manopt, a Matlab toolbox for optimization on manifolds. J Mach Learn Res 15:1455–1459MATH

11.

Boyd S, El Ghaoui L, Feron E, Balakrishnan V (1994) Linear matrix inequalities in system and control theory. Studies in applied mathematics, vol 15. SIAM, Philadelphia

12.

Burer S, Kim S, Kojima M (2014) Faster, but weaker, relaxations for quadratically constrained quadratic programs. Comput Optim Appl 59(1):27–45. https://doi.org/10.1007/s10589-013-9618-8 MathSciNetCrossRefMATH

13.

Cardoso JF (1991) Super-symmetric decomposition of the fourth-order cumulant tensor. blind identification of more sources than sensors. In: Proceedings of the IEEE international conference on acoustics, speech, and signal processing (ICASSP91), Toronto, vol 5, pp 3109–3112

14.

Chen Y, Gao DY (2013) Global solutions to large-scale spherical constrained quadratic minimization via canonical dual approach. ArXiv e-prints arXiv:1308.4450v1

15.

de Almeida ALF, Luciani X, Stegeman A, Comon P (2012) CONFAC decomposition approach to blind identification of underdetermined mixtures based on generating function derivatives. IEEE Trans Signal Process 60(11):5698–5713MathSciNetCrossRef

16.

Ding S, Zhang N, Zhang X, Wu F (2017) Twin support vector machine: theory, algorithm and applications. Neural Comput Appl 28(11):3119–3130. https://doi.org/10.1007/s00521-016-2245-4 CrossRef

17.

Dostál Z (2009) Optimal quadratic programming algorithms: with applications to variational inequalities, 1st edn. Springer, New YorkMATH

18.

Dostál Z, Kozubek T (2012) An optimal algorithm and superrelaxation for minimization of a quadratic function subject to separable convex constraints with applications. Math Program 135(1):195–220. https://doi.org/10.1007/s10107-011-0454-2 MathSciNetCrossRefMATH

19.

Gander W, Golub GH, von Matt U (1989) A constrained eigenvalue problem. Special Issue Dedicated to Alan J. Hoffman, Linear Algebra Appl 114:815–839. https://doi.org/10.1016/0024-3795(89)90494-1 MathSciNetCrossRefMATH

20.

Gentile C, Li S, Kar P, Karatzoglou A, Zappella G, Etrue E (2017) On context-dependent clustering of bandits. In: Precup D, Teh YW (eds) Proceedings of the 34th international conference on machine learning, proceedings of machine learning research. PMLR, International Convention Centre, Sydney, vol 70, pp 1253–1262

21.

Gershman AB, Sidiropoulos ND, Shahbazpanahi S, Bengtsson M, Ottersten B (2010) Convex optimization-based beamforming. IEEE Signal Process Mag 27(3):62–75. https://doi.org/10.1109/MSP.2010.936015 CrossRef

22.

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145. https://doi.org/10.1145/227683.227684 MathSciNetCrossRefMATH

23.

Hager WW (2001) Minimizing a quadratic over a sphere. SIAM J Optim 12(1):188–208. https://doi.org/10.1137/S1052623499356071 MathSciNetCrossRefMATH

24.

Holmström K (1997) TOMLAB—an environment for solving optimization problems in MATLAB. In: Proceedings for the Nordic Matlab conference ’97, pp 27–28

25.

Kar P, Li S, Narasimhan H, Chawla S, Sebastiani F (2016) Online optimization methods for the quantification problem. In: Proceedings of the 22 ACM SIGKDD international conference on knowledge discovery and data mining, KDD’16. New York, pp 1625–1634. https://doi.org/10.1145/2939672.2939832

26.

Kim S, Kojima M (2000) Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim Methods Softw 15:201–224MathSciNetCrossRef

27.

Kim S, Kojima M (2003) Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput Optim Appl 26(2):143–154. https://doi.org/10.1023/A:1025794313696 MathSciNetCrossRefMATH

28.

Korda N, Szörényi B, Li S (2016) Distributed clustering of linear bandits in peer to peer networks. In: Proceedings of the 33nd international conference on machine learning, ICML 2016, pp 1301–1309

29.

Li S (2016) The art of clustering bandits. PhD thesis, Universitá degli Studi dell‘Insubria

30.

Li S, Karatzoglou A, Gentile C (2016) Collaborative filtering bandits. In: Proceedings of the 39th international ACM SIGIR conference on research and development in information retrieval, SIGIR’16. ACM, New York, pp 539–548 https://doi.org/10.1145/2911451.2911548

31.

Lim L, Comon P (2014) Blind multilinear identification. IEEE Trans Inf Theory 60(2):1260–1280. https://doi.org/10.1109/TIT.2013.2291876 MathSciNetCrossRefMATH

32.

Linderoth J (2005) A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math Program 103(2):251–282. https://doi.org/10.1007/s10107-005-0582-7 MathSciNetCrossRefMATH

33.

Locatelli M (2015) Some results for quadratic problems with one or two quadratic constraints. Oper Res Lett 43(2):126–131. https://doi.org/10.1016/j.orl.2014.12.002 MathSciNetCrossRefMATH

34.

Luo Z, Ma W, So AM, Ye Y, Zhang S (2010) Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process Mag 27(3):20–34. https://doi.org/10.1109/MSP.2010.936019 CrossRef

35.

Muti D, Bourennane S (2005) Multiway filtering based on fourth order cumulants. Appl Signal Proc EURASIP 7:1147–1159MATH

36.

Nesterov Y, Wolkowicz H, Ye Y (2000) Semidefinite programming relaxations of nonconvex quadratic optimization. Springer, New York, pp 361–419. https://doi.org/10.1007/978-1-4615-4381-7_13

37.

Nie J (2017) Generating polynomials and symmetric tensor decompositions. Found Comput Math 17(2):423–465. https://doi.org/10.1007/s10208-015-9291-7 MathSciNetCrossRefMATH

38.

Phan AH, Cichocki A (2010) Tensor decompositions for feature extraction and classification of high dimensional datasets. Nonlinear Theory Appl IEICE 1(1):37–68CrossRef

39.

Phan AH, Tichavský P, Cichocki A (2019) Error preserving correction: a method for CP decomposition at a target error bound. IEEE Trans Signal Process 67(5):1175–1190. https://doi.org/10.1109/TSP.2018.2887192 MathSciNetCrossRefMATH

40.

Phan AH, Yamagishi M, Cichocki A (2017) An augmented Lagrangian algorithm for decomposition of symmetric tensors of order-4. In: 2017 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp 2547–2551. https://doi.org/10.1109/ICASSP.2017.7952616

41.

Reeves SJ (2014) Chapter 6 - image restoration: Fundamentals of image restoration. In: Trussell J, Srivastava A, Roy-Chowdhury AK, Srivastava A, Naylor PA, Chellappa R, Theodoridis S (eds) Academic press library in signal processing, vol 4. Elsevier, Amsterdam, pp 165–192. https://doi.org/10.1016/B978-0-12-396501-1.00006-6

42.

Rendl F, Wolkowicz H (1997) A semidefinite framework for trust region subproblems with applications to large scale minimization. Math Program 77:273–299. https://doi.org/10.1007/BF02614438 MathSciNetCrossRefMATH

43.

Rojas M, Santos SA, Sorensen DC (2008) Algorithm 873: LSTRS: Matlab software for large-scale trust-region subproblems and regularization. ACM Trans Math Softw 34(2):11:1–11:28. https://doi.org/10.1145/1326548.1326553 MathSciNetCrossRefMATH

44.

Shashua A, Zass R, Hazan T (2006) Multi-way clustering using super-symmetric non-negative tensor factorization. In: European conference on computer vision (ECCV), Graz. http://www.cs.huji.ac.il/~zass/ CrossRef

45.

Sorensen DC (1997) Minimization of a large-scale quadratic function subject to a spherical constraint. SIAM J Optim 7(1):141–161. https://doi.org/10.1137/S1052623494274374 MathSciNetCrossRefMATH

46.

Waldspurger I, d’Aspremont A, Mallat S (2015) Phase recovery, maxcut and complex semidefinite programming. Math Program 149(1–2):47–81. https://doi.org/10.1007/s10107-013-0738-9 MathSciNetCrossRefMATH

47.

Wen Z, Yin W (2012) A feasible method for optimization with orthogonality constraints. Math Program. https://doi.org/10.1007/s10107-012-0584-1 CrossRefMATH

48.

Yuen N, Friedlander B (1996) Asymptotic performance analysis of blind signal copy using fourth order cumulant. Int J Adapt Control Signal Process 10(2–3):239–265CrossRef

49.

Zhang LH, Liao LZ, Ng MK (2010) Fast algorithms for the generalized Foley–Sammon discriminant analysis. SIAM J Matrix Anal Appl 31(4):1584–1605. https://doi.org/10.1137/080720863 MathSciNetCrossRefMATH

50.

Zhu Y, Xue J (2017) Face recognition based on random subspace method and tensor subspace analysis. Neural Comput Appl 28(2):233–244. https://doi.org/10.1007/s00521-015-2052-3 CrossRef

Title: Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition
Authors: Anh-Huy Phan
Masao Yamagishi
Danilo Mandic
Andrzej Cichocki
Publication date: 20-04-2019
Publisher: Springer London
Published in: Neural Computing and Applications / Issue 11/2020
Print ISSN: 0941-0643
Electronic ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-019-04191-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 11/2020

A two-stage approach for automatic liver segmentation with Faster R-CNN and DeepLab

Stability property of impulsive inertial neural networks with unbounded time delay and saturating actuators

SP-J48: a novel optimization and machine-learning-based approach for solving complex problems: special application in software engineering for detecting code smells

Inferring region significance by using multi-source spatial data

Modular domain-to-domain translation network

Fabrication of a portable device for stress monitoring using wearable sensors and soft computing algorithms

Premium Partner