Abstract
Given then×p orthogonal matrixA and the convex functionf:R n→R, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.
Similar content being viewed by others
References
Ben-Israel, A., Ben-Tal, A., andZlobec, S.,Optimality in Nonlinear Programming: A Feasible Directions Approach, Wiley, New York, New York, 1981.
Wolkowicz, H.,Geometry of Optimality Conditions and Constraint Qualifications: The Convex Case, Mathematical Programming, Vol. 19, pp. 32–60, 1980.
Wolkowicz, H.,The Method of Reduction in Convex Programming, Journal of Optimization Theory and Applications, Vol. 40, pp. 349–378, 1983.
Wolkowicz, H.,Calculating the Cone of Directions of Constancy, Journal of Optimization Theory and Applications, Vol. 25, pp. 451–457, 1978.
Baart, M. L.,The Use of Autocorrelation for Pseudo-Rank Determination in Noisy Ill-Conditioned Linear Least-Squares Problems, IMA Journal of Numerical Analysis, Vol. 2, pp. 241–247, 1982.
Golub, G., Klema, V., andStewart, G. W.,Rank Degeneracy and Least Squares Problems, Stanford University, Research Report, 1976.
Rockafellar, R. T.,Some Convex Programs Where Duals Are Linearly Constrained, Nonlinear Programming, Edited by J. B. Rosen, O. L. Mangasarian, and K. Ritter, Academic Press, New York, New York, pp. 293–322, 1970.
Coleman, T. F., andSorensen, D. C.,A Note on the Computation of an Orthonormal Basis for the Null Space of a Matrix, Cornell University, Department of Computer Science, Technical Report No. 82–510, 1982.
Parlett, B. N.,Analysis of Algorithms for Reflections in Bisectors, SIAM Review, Vol. 13, pp. 197–208, 1971.
Parlett, B. N.,The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, New Jersey, 1980.
Wilkinson, J. H.,Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, New Jersey, 1963.
Author information
Authors and Affiliations
Additional information
Communicated by A. V. Fiacco
This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).
Rights and permissions
About this article
Cite this article
Lamoureux, M., Wolkowicz, H. Numerical decomposition of a convex function. J Optim Theory Appl 47, 51–64 (1985). https://doi.org/10.1007/BF00941315
Issue Date:
DOI: https://doi.org/10.1007/BF00941315