zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method. (English) Zbl 1236.65070

The author considers a group of closed-form formulas for calculating the global maximum and minimum ranks and inertias of the quadratic Hermitian matrix function φ(X)=Q-XPX * with respect to the variable matrix X by using a linearization method and some known formulas for extremum ranks and inertias of linear Hermitian matrix functions, where both P and Q are complex Hermitian matrices and X * is the conjugate transpose of X.

Examples are presented to illustrative applications of the equality-constrained quadratic optimization in some matrix completion problems.

MSC:
65K05Mathematical programming (numerical methods)
15A09Matrix inversion, generalized inverses
15A24Matrix equations and identities
15A63Quadratic and bilinear forms, inner products
15B10Orthogonal matrices
15B57Hermitian, skew-Hermitian, and related matrices
References:
[1]Krafft, O.: A matrix optimization problem, Linear algebra appl. 51, 137-142 (1983) · Zbl 0504.15013 · doi:10.1016/0024-3795(83)90154-4
[2]Badawia, F. A.: On a quadratic matrix inequality and the corresponding algebraic Riccati equation, Internat. J. Control 6, 313-322 (1982) · Zbl 0486.93059 · doi:10.1080/00207178208932895
[3]Bunch, J. R.; Kaufman, L.: A computational method for the indefinite quadratic programming problem, Linear algebra appl. 34, 341-370 (1980) · Zbl 0473.65036 · doi:10.1016/0024-3795(80)90172-X
[4]Chen, Y.: Nonnegative definite matrices and their applications to matrix quadratic programming problems, Linear multilinear algebra 33, 189-201 (1993) · Zbl 0764.15010 · doi:10.1080/03081089308818194
[5]Farebrother, R. W.: Necessary and sufficient conditions for a quadratic form to be positive whenever a set of homogeneous linear constraints is satisfied, Linear algebra appl. 6, 39-42 (1977) · Zbl 0348.15014 · doi:10.1016/0024-3795(77)90017-9
[6]Martin, D. H.: Finite criteria for conditional definiteness of quadratic forms, Linear algebra appl. 39, 9-21 (1981) · Zbl 0464.15012 · doi:10.1016/0024-3795(81)90286-X
[7]Stoica, P.; Jakobsson, A.; Li, J.: Matrix optimization result with DSP applications, Digit. signal process. 6, 195-201 (1996)
[8]Chabrillac, Y.; Crouzeix, J. -P.: Definiteness and semidefiniteness of quadratic forms revisited, Linear algebra appl. 63, 283-292 (1984) · Zbl 0548.15027 · doi:10.1016/0024-3795(84)90150-2
[9]Dyn, N.; Jr., W. E. Ferguson: The numerical solution of equality-constrained quadratic programming problems, Math. comp. 41, 165-170 (1983) · Zbl 0527.49030 · doi:10.2307/2007773
[10]El Ghaoui, L.; Niculescu, S.: Advances in linear matrix inequality methods in control, (2000)
[11]Evans, D. J.; Sun, W.; De Sampaio, R. J. B.; Yuan, J. Y.: The restricted generalized inverses corresponding to constrained quadratic system, Int. J. Comput. math. 62, 285-296 (1996) · Zbl 0867.15004 · doi:10.1080/00207169608804544
[12]Galligani, E.; Zanni, L.: Error analysis of an algorithm for equality-constrained quadratic programming problems, Computing 58, 47-67 (1997) · Zbl 0865.65042 · doi:10.1007/BF02684471
[13]Gill, P. E.; Murray, W.; Saunders, M. A.; Wright, M. H.: Inertia-controlling methods for general quadratic programming, SIAM rev. 33, 1-36 (1991) · Zbl 0734.90062 · doi:10.1137/1033001
[14]Giribet, J. I.; Maestripieri, A.; Pería, F. M.: A geometrical approach to indefinite least squares problems, Acta appl. Math. 111, 65-81 (2010) · Zbl 1202.46090 · doi:10.1007/s10440-009-9532-3
[15]Gould, N. I. M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem, Math. program. 32, 90-99 (1985) · Zbl 0591.90068 · doi:10.1007/BF01585660
[16]Gould, N. I. M.; Hribar, M. E.; Nocedal, J.: On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. comput. 23, 1376-1395 (2001) · Zbl 0999.65050 · doi:10.1137/S1064827598345667
[17]Maddocks, J. H.: Restricted quadratic forms, inertia theorems and the Schur complement, Linear algebra appl. 108, 1-36 (1988) · Zbl 0653.15020 · doi:10.1016/0024-3795(88)90177-2
[18]Majthay, A.: Optimality conditions for quadratic programming, Math. program. 1, 359-365 (1971) · Zbl 0246.90038 · doi:10.1007/BF01584097
[19]Markowitz, H.: The optimization of a quadratic function subject to linear constraints, Nav. res. Logist. Q. 3, 111-133 (1956)
[20]Murty, K. G.; Kabadi, S. N.: Some NP-complete problems in quadratic and nonlinear programming, Math. program. 39, 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948
[21]Padalos, P. M.; Schnitger, G.: Checking local optamality in constrained quadratic programming is NP-hard, Oper. res. Lett. 7, 33-35 (1988) · Zbl 0644.90067 · doi:10.1016/0167-6377(88)90049-1
[22]Pardalos, P. M.; Vavasis, S. A.: Quadratic programming with one negative eigenvalue is NP-hard, J. global optim. 1, 15-22 (1991) · Zbl 0755.90065 · doi:10.1007/BF00120662
[23]Thng, I.; Cantoni, A.; Leung, Y. H.: Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints, Appl. math. Optim. 34, 164-182 (1996) · Zbl 0911.90270 · doi:10.1007/BF01182622
[24]Wright, S.: A fast algorithm for equality-constrained quadratic programming on the alliant FX/8, Ann. oper. Res. 14, 225-243 (1988)
[25]Vavasis, S. A.: Quadratic programming is in NP, Inform. process. Lett. 36, 73-77 (1990) · Zbl 0719.90052 · doi:10.1016/0020-0190(90)90100-C
[26]Tian, Y.: Completing block Hermitian matrices with maximal and minimal ranks and inertias, Electron. J. Linear algebra 21, 124-141 (2010) · Zbl 1207.15029 · doi:emis:journals/ELA/ela-articles/abstracts/abs_vol21pp124-141.pdf
[27]Boyd, S.; Vandenberghe, L.: Convex optimization, (2004)
[28]Candes, E.; Recht, B.: Exact matrix completion via convex optimization, Found. comput. Math. 9, 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[29]M. Fazel, H. Hindi, S. Boyd, A rank minimization heuristic with application to minimum order system approximation, in: Proceedings of the 2001 American Control Conference, 2001, pp. 4734–4739.
[30]M. Fazel, H. Hindi, S. Boyd, Rank minimization and applications in system theory, in: Proceedings of the 2004 American Control Conference, 2004, pp. 3273–3278.
[31]Hoang, T. M.; Thierauf, T.: The complexity of the inertia, Lecture notes in computer science 2556, 206-217 (2002) · Zbl 1027.68063 · doi:http://link.springer.de/link/service/series/0558/bibs/2556/25560206.htm
[32]T.M. Hoang, T. Thierauf, The complexity of the inertia and some closure properties of GapL, in: Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, 2005, pp. 28–37.
[33]Y. Kim, M. Mesbahi, On the rank minimization problem, in: Proceedings of the 2004 American Control Conference, Boston, 2004, pp. 2015–2020.
[34]Laurent, M.: Matrix completion problems, Encyclopedia of optimization, 221-229 (2001)
[35]Mahajan, M.; Sarma, J.: On the complexity of matrix rank and rigidity, Lecture notes in computer science 4649, 269-280 (2007) · Zbl 1188.68158 · doi:10.1007/978-3-540-74510-5_28
[36]Mesbahi, M.: On the rank minimization problem and its control applications, Systems control lett. 33, 31-36 (1998) · Zbl 0902.93027 · doi:10.1016/S0167-6911(97)00111-4
[37]M. Mesbahi, G.P. Papavassilopoulos, Solving a class of rank minimization problems via semi-definite programs, with applications to the fixed order output feedback synthesis, in: Proceedings of the American Control Conference, 1997, pp. 77–80.
[38]Recht, B.; Fazel, M.; Parrilo, P. A.: Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization, SIAM rev. 52, 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[39]Amato, H.; Mensch, G.: Rank restrictions on the quadratic form in indefinite quadratic programming, Math. methods oper. Res. 15, 214-216 (1971) · Zbl 0245.90028 · doi:10.1007/BF01939829
[40]Schaible, S.: On factored quadratic functions, Math. methods oper. Res. 17, 179-181 (1973) · Zbl 0265.90037 · doi:10.1007/BF01951416
[41]Swarup, K.: Programming with indefinite quadratic function with linear constraints, RAIRO rech. Oper. 8, 132-136 (1966) · Zbl 0141.17505
[42]Jr., W. N. Anderson: Shorted operators, SIAM J. Appl. math. 20, 522-525 (1971) · Zbl 0217.05503 · doi:10.1137/0120053
[43]Jr., W. N. Anderson; Trapp, G. E.: Shorted operators II, SIAM J. Appl. math. 28, 60-71 (1975) · Zbl 0295.47032 · doi:10.1137/0128007
[44]Mitra, S. K.; Puri, M. L.: Shorted matrices–an extended concept and some applications, Linear algebra appl. 42, 57-79 (1982) · Zbl 0478.15012 · doi:10.1016/0024-3795(82)90138-0
[45]Tian, Y.: Equalities and inequalities for inertias of Hermitian matrices with applications, Linear algebra appl. 433, 263-296 (2010) · Zbl 1205.15033 · doi:10.1016/j.laa.2010.02.018
[46]Tian, Y.: Maximization and minimization of the rank and inertia of the Hermitian matrix expression A-BX-(BX)* with applications, Linear algebra appl. 434, 2109-2139 (2011) · Zbl 1211.15022 · doi:10.1016/j.laa.2010.12.010
[47]Marsaglia, G.; Styan, G. P. H.: Equalities and inequalities for ranks of matrices, Linear multilinear algebra 2, 269-292 (1974) · Zbl 0297.15003
[48]Liu, Y.; Tian, Y.: MAX–MIN problems on the ranks and inertias of the matrix expressions A-BXC±(BXC)* with applications, J. optim. Theory appl. 148, 593-622 (2011) · Zbl 1223.90077 · doi:10.1007/s10957-010-9760-8
[49]Penrose, R.: A generalized inverse for matrices, Proc. Cambridge philos. Soc. 51, 406-413 (1955) · Zbl 0065.24603
[50]Mitra, S. K.: The matrix equations AX=C,XB=D, Linear algebra appl. 59, 171-181 (1984) · Zbl 0543.15011 · doi:10.1016/0024-3795(84)90166-6
[51]Tian, Y.: Extremal ranks of a quadratic matrix expression with applications, Linear multilinear algebra 59, 627-644 (2011) · Zbl 1220.15006 · doi:10.1080/03081081003774268
[52]Gregory, D. A.; Shader, B. L.; Watts, V. L.: Biclique decompositions and Hermitian rank, Linear algebra appl. 292, 267-280 (1999) · Zbl 0929.05056 · doi:10.1016/S0024-3795(99)00042-7
[53]Blondel, V.; Gevers, M.: Simultaneous stabilizability question of three linear systems is rationally undecidable, Math. control signals systems 6, 135-145 (1994) · Zbl 0792.93109 · doi:10.1007/BF01211744
[54]S. Ibaraki, M. Tomozuka, Rank minimization approach for solving BMI problems with random search, in: Proceedings of the American Control Conference, 2001, pp. 1870–1876.
[55]Nemirovskii, A.: Several NP-hard problems arising in robust stability analysis, Math. control signals systems 6, 99-105 (1994) · Zbl 0792.93100 · doi:10.1007/BF01211741
[56]O. Toker, H. Özbay, On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback, in: Proceedings of the 1995 American Control Conference, 1995, pp. 2525–2526.
[57]Bini, D. A.; Eidelman, Y.; Gemignani, L.; Gohberg, I.: The unitary completion and QR iterations for a class of structured matrices, Math. comp. 77, 353-378 (2008) · Zbl 1141.65025 · doi:10.1090/S0025-5718-07-02004-2
[58]Dubovoj, V. K.; Fritzsche, B.; Kirstein, B.: On a class of matrix completion problems, Math. nachr. 143, 211-226 (1989) · Zbl 0683.15005 · doi:10.1002/mana.19891430117
[59]Mathis, R. F.: Completion of a symmetric uinitary matrix, SIAM rev. 11, 261-263 (1969) · Zbl 0179.05204 · doi:10.1137/1011042
[60]Johnson, C. R.; Rodman, L.: Completion of partial matrices to contractions, J. funct. Anal. 69, 260-267 (1986) · Zbl 0626.47015 · doi:10.1016/0022-1236(86)90091-1
[61]Tian, Y.; Takane, Y.: The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems, Comput. math. Appl. 57, 1294-1304 (2009) · Zbl 1186.15005 · doi:10.1016/j.camwa.2009.01.025
[62]Liu, Y.; Tian, Y.: More on extremal ranks of the matrix expressions A-BX±X*b* with statistical applications, Numer. linear algebra appl. 15, 307-325 (2008) · Zbl 1212.15029 · doi:10.1002/nla.553
[63]Liu, Y.; Tian, Y.: Extremal ranks of submatrices in an Hermitian solution to the matrix equation AXA*=B with applications, J. appl. Math. comput. 32, 289-301 (2010) · Zbl 1194.15014 · doi:10.1007/s12190-009-0251-8
[64]Liu, Y.; Tian, Y.: A simultaneous decomposition of a matrix triplet with applications, Numer. linear algebra appl. 18, 69-85 (2011)
[65]Liu, Y.; Tian, Y.; Takane, Y.: Ranks of Hermitian and skew-Hermitian solutions to the matrix equation AXA*=B, Linear algebra appl. 431, 2359-2372 (2009) · Zbl 1180.15018 · doi:10.1016/j.laa.2009.03.011
[66]Tian, Y.; Liu, Y.: Extremal ranks of some symmetric matrix expressions with applications, SIAM J. Matrix anal. Appl. 28, 890-905 (2006) · Zbl 1123.15001 · doi:10.1137/S0895479802415545
[67]Beck, A.: Quadratic matrix programming, SIAM J. Optim. 17, 1224-1238 (2006) · Zbl 1136.90025 · doi:10.1137/05064816X
[68]Beck, A.: Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, J. optim. Theory appl. 142, 1-29 (2009) · Zbl 1188.90190 · doi:10.1007/s10957-009-9539-y
[69]Cohen, N.; Dancis, J.: Inertias of block band matrix completions, SIAM J. Matrix anal. Appl. 19, 583-612 (1998) · Zbl 0974.15009 · doi:10.1137/S0895479895296471
[70]Fujioka, H.; Hara, S.: State covariance assignment problem with measurement noise: a unified approach based on a symmetric matrix equation, Linear algebra appl. 203–204, 579-605 (1994) · Zbl 0802.93044 · doi:10.1016/0024-3795(94)90215-1
[71]Khatskevich, V. A.; Ostrovskii, M. I.; Shulman, V. S.: Quadratic inequalities for Hilbert space operators, Integral equations operator theory 59, 19-34 (2007) · Zbl 1133.47012 · doi:10.1007/s00020-007-1511-3