# Solving PSD matrix in Newton's method

I have functions defined as follows:

$f1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f2(A) = \sum\|x_k-x_l\|^2_A$ where A is PSD matrix, x are number vectors.

Task is to minimize function $f(A) = f2(A)$ subject to: $f1(A) \geq 1$ and $A \succeq 0$ . I can compute its gradient and hessian to use in Newton's method for minimization (which i want to use).

My question is: how can i incorporate above constraints (to be satisfied) to the algorithm?

Can be first constraint solved by rewriting the main function $f(A)$ to contain slack variable -> something like: $f(A) = f2(A) + 1 - f1(A)$ ?

• do you mean symmetric positive definite (SPD)? – Aron Ahmadia May 7 '12 at 11:53
• I mean positive semi-definite (PSD) matrix. – mko May 7 '12 at 11:55
• Did you mean to say that the $x_i,x_j,x_k,x_l$ are all vectors? Or do these symbols refer to elements of a single vector $x$? Only the first interpretation appears to make sense to me, but it's worth asking. Also, do you sum over all possible indices in both $f_1$ and $f_2$? How are they different then? – Wolfgang Bangerth May 7 '12 at 20:47
• Hi. Yes, $x_i,x_j,x_k,x_l$ are all number vectors (e.g. $x_i = [1,2,3], x_j = [2,3,4]$). Yes i sum over all indices. Difference between $f_1$ and $f_2$ is that in $f_2$ i sum over similar vectors (i have information about that) and in $f_1$ dissimilar. – mko May 8 '12 at 9:13

insert $A=R^TR$ with upper traingual $R$ to get rid of the semidefinite constraint (and reformulate $f_2(A)$ as the trace of $R BR^T$ to save function evaluation cost).
Then solve the resulting constraint problem using a constrianed optimization routine, as you cannot eliminate the constraint on $f_1$.
• @mko: $\sum_j \|z_j\|_A^2=\sum_j Z_j^TAz_j= \sum_j z_j^TR^TRz_j=\sum_j \trace Rz_jz_j^TR^T = \trace RBR^T$, where $B=\sum_j z_jz_j^T$. – Arnold Neumaier May 8 '12 at 15:43