On the duality of quadratic minimization problems using pseudo inverses
Subject Areas : Numerical analysis
1 - Department of Statistics, Athens University of Economics and Business, 76 Patission Str 10434, Athens, Greece
2 - Department of Mathematics, School of Applied Mathematics and Physical Sciences, National Technical University of Athens, Iroon Polytexneiou 9, 15780 Zografou, Athens, Greece
Keywords: Moore-Penrose inverse, Lagrange multipliers, constrained optimization, general normal equation, duality principle, KKT conditions,
Abstract :
In this paper we consider the minimization of a positive semidefinite quadratic form, having a singular corresponding matrix $H$. We state the dual formulation of the original problem and treat both problems only using the vectors $x \in \mathcal{N}(H)^\perp$ instead of the classical approach of convex optimization techniques such as the null space method. Given this approach and based on the strong duality principle, we provide a closed formula for the calculation of the Lagrange multipliers $\\lambda$ in the cases when (i) the constraint equation is consistent and (ii) the constraint equation is inconsistent, using the general normal equation. In both cases the Moore-Penrose inverse will be used to determine a unique solution of the problems. In addition, in the case of a consistent constraint equation, we also give sufficient conditions for our solution to exist using the well known KKT conditions.
[1] A. B. Israel, Generalized inverses and the Bott-Duffin network analysis, J. Math. Anal. Appl. 7 (1963), 428-435.
[2] A. Ben-Israel, T. N. E. Grenville, Generalized Inverses: Theory and Applications, Springer-Verlag, Berlin, 2002.
[3] S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[4] S. L. Campbell, C. D. Meyer, Generalized Inverses of Linear Transformations, Dover Publications Inc, New York, 1991.
[5] W. S. Dorn, Duality in quadratic programming, Quarterly of Applied Mathematics. 18 (2) (1960), 155-162.
[6] C. W. Groetsch, Generalized inverses of linear operators, Marcel Dekker Inc, New York, 1977.
[7] D. Luenberger, Optimization by Vector Space Methods, Wiley Publ, New York, 1969.
[8] R. K. Manherz, S. L. Hakimi, The generalized inverse network analysis and quadratic-error minimization problems, IEEE Trans. Circuit Theory. (1969), 559-562.
[9] J. Nocedal, S. Wright, Numerical Optimization, Springer, 2006.
[10] D. Pappas, Minimization of constrained quadratic forms in Hilbert spaces, Ann. Funct. Anal. (2) (1) (2011), 1-12.
[11] D. Pappas, Restricted linear constrained minimization of quadratic functionals, Linear and Multilinear Algebra. 61 (10) (2013), 1394-1407.
[12] D. Pappas, A. Perperoglou, Constrained matrix optimization with applications, J. Appl. Math. Comput. 40 (2012), 357-369.
[13] H. Schwerdtfeger, Introduction to Linear Algebra and the Theory of Matrices, Noordhoff, Groningen, 1950.
[14] P. Stanimirovic, D. Pappas, S. Miljkovic, Minimization of quadratic forms using the Drazin-inverse solution, Linear and Multilinear Algebra. 62 (2) (2014), 252-266.
[15] P. Stoica, A. Jakobsson, J. Li, Matrix optimization result with DSP applications, Dig. Signal Proc. 6 (1996), 195-201.