Semi-Definite Matrix Constraints in Optimization

Positive semi-definite matrix constraints arise in a number of optimization problems in which some or all of the elements of a matrix are variables, such as the educational testing and matrix modification problems. The structure of such constraints is developed, including expressions for the normal cone, feasible directions and their application to optimality conditions. A computational framework is given within which these concepts can be exploited and which permits the quantification of second order effects. The matrix of Lagrange multipliers in this formulation is shown to have an important relationship to the characterization of the normal cone. Modifications of various iterative schemes in nonlinear programming are considered in order to develop an effective algorithm for the educational testing problem, and comparative numerical experiments are described. It is shown that a particular choice of the penalty parameter for an l₁ exact penalty function is appropriate for this type of problem. The behaviour of the extreme eigenvalues (or sums thereof) of a matrix is related to the ideas of the paper, and the convexity of such functions is proved, together with expressions for subgradients.