# zbMATH — the first resource for mathematics

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 $$\phi(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:
 65K05 Numerical mathematical programming methods 15A09 Theory of matrix inversion and generalized inverses 15A24 Matrix equations and identities 15A63 Quadratic and bilinear forms, inner products 15B10 Orthogonal matrices 15B57 Hermitian, skew-Hermitian, and related matrices
Full Text:
##### References:
 [1] Krafft, O., A matrix optimization problem, Linear algebra appl., 51, 137-142, (1983) · Zbl 0504.15013 [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 [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 [4] Chen, Y., Nonnegative definite matrices and their applications to matrix quadratic programming problems, Linear multilinear algebra, 33, 189-201, (1993) · Zbl 0764.15010 [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 [6] Martin, D.H., Finite criteria for conditional definiteness of quadratic forms, Linear algebra appl., 39, 9-21, (1981) · Zbl 0464.15012 [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 [9] Dyn, N.; Ferguson, W.E., The numerical solution of equality-constrained quadratic programming problems, Math. comp., 41, 165-170, (1983) · Zbl 0527.49030 [10] El Ghaoui, L.; Niculescu, S., Advances in linear matrix inequality methods in control, (2000), SIAM · Zbl 0943.93024 [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 [12] Galligani, E.; Zanni, L., Error analysis of an algorithm for equality-constrained quadratic programming problems, Computing, 58, 47-67, (1997) · Zbl 0865.65042 [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 [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 [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 [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 [17] Maddocks, J.H., Restricted quadratic forms, inertia theorems and the Schur complement, Linear algebra appl., 108, 1-36, (1988) · Zbl 0653.15020 [18] Majthay, A., Optimality conditions for quadratic programming, Math. program., 1, 359-365, (1971) · Zbl 0246.90038 [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 [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 [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 [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 [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 [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 [27] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press · Zbl 1058.90049 [28] Candes, E.; Recht, B., Exact matrix completion via convex optimization, Found. comput. math., 9, 717-772, (2009) · Zbl 1219.90124 [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, (), 206-217 · Zbl 1027.68063 [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, (), 221-229 [35] Mahajan, M.; Sarma, J., On the complexity of matrix rank and rigidity, (), 269-280 · Zbl 1188.68158 [36] Mesbahi, M., On the rank minimization problem and its control applications, Systems control lett., 33, 31-36, (1998) · Zbl 0902.93027 [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 [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 [40] Schaible, S., On factored quadratic functions, Math. methods oper. res., 17, 179-181, (1973) · Zbl 0265.90037 [41] Swarup, K., Programming with indefinite quadratic function with linear constraints, RAIRO rech. oper., 8, 132-136, (1966) · Zbl 0141.17505 [42] Anderson, W.N., Shorted operators, SIAM J. appl. math., 20, 522-525, (1971) · Zbl 0217.05503 [43] Anderson, W.N.; Trapp, G.E., Shorted operators II, SIAM J. appl. math., 28, 60-71, (1975) · Zbl 0295.47032 [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 [45] Tian, Y., Equalities and inequalities for inertias of Hermitian matrices with applications, Linear algebra appl., 433, 263-296, (2010) · Zbl 1205.15033 [46] Tian, Y., Maximization and minimization of the rank and inertia of the Hermitian matrix expression $$A - B X -(B X)^\ast$$ with applications, Linear algebra appl., 434, 2109-2139, (2011) · Zbl 1211.15022 [47] Marsaglia, G.; Styan, G.P.H., Equalities and inequalities for ranks of matrices, Linear multilinear algebra, 2, 269-292, (1974) [48] Liu, Y.; Tian, Y., Max – min problems on the ranks and inertias of the matrix expressions $$A - B X C \pm(B X C)^\ast$$ with applications, J. optim. theory appl., 148, 593-622, (2011) · Zbl 1223.90077 [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 $$A X = C, X B = D$$,, Linear algebra appl., 59, 171-181, (1984) [51] Tian, Y., Extremal ranks of a quadratic matrix expression with applications, Linear multilinear algebra, 59, 627-644, (2011) · Zbl 1220.15006 [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 [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 [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 [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 [58] Dubovoj, V.K.; Fritzsche, B.; Kirstein, B., On a class of matrix completion problems, Math. nachr., 143, 211-226, (1989) · Zbl 0683.15005 [59] Mathis, R.F., Completion of a symmetric uinitary matrix, SIAM rev., 11, 261-263, (1969) · Zbl 0179.05204 [60] Johnson, C.R.; Rodman, L., Completion of partial matrices to contractions, J. funct. anal., 69, 260-267, (1986) · Zbl 0626.47015 [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 [62] Liu, Y.; Tian, Y., More on extremal ranks of the matrix expressions $$A - B X \pm X^\ast B^\ast$$ with statistical applications, Numer. linear algebra appl., 15, 307-325, (2008) · Zbl 1212.15029 [63] Liu, Y.; Tian, Y., Extremal ranks of submatrices in an Hermitian solution to the matrix equation $$A X A^\ast = B$$ with applications, J. appl. math. comput., 32, 289-301, (2010) · Zbl 1194.15014 [64] Liu, Y.; Tian, Y., A simultaneous decomposition of a matrix triplet with applications, Numer. linear algebra appl., 18, 69-85, (2011) · Zbl 1249.15020 [65] Liu, Y.; Tian, Y.; Takane, Y., Ranks of Hermitian and skew-Hermitian solutions to the matrix equation $$A X A^\ast = B$$, Linear algebra appl., 431, 2359-2372, (2009) · Zbl 1180.15018 [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 [67] Beck, A., Quadratic matrix programming, SIAM J. optim., 17, 1224-1238, (2006) · Zbl 1136.90025 [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 [69] Cohen, N.; Dancis, J., Inertias of block band matrix completions, SIAM J. matrix anal. appl., 19, 583-612, (1998) · Zbl 0974.15009 [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 [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
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.