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)$ ?

  • $\begingroup$ do you mean symmetric positive definite (SPD)? $\endgroup$ Commented May 7, 2012 at 11:53
  • $\begingroup$ I mean positive semi-definite (PSD) matrix. $\endgroup$
    – mko
    Commented May 7, 2012 at 11:55
  • $\begingroup$ 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? $\endgroup$ Commented May 7, 2012 at 20:47
  • $\begingroup$ 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. $\endgroup$
    – mko
    Commented May 8, 2012 at 9:13

1 Answer 1


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$.

For optimization software, see my page http://www.mat.univie.ac.at/~neum/glopt/software_l.html

  • $\begingroup$ Hi, thanks for the answer. I will try your solution, but i dont know exactly what B is... $\endgroup$
    – mko
    Commented May 7, 2012 at 20:09
  • $\begingroup$ @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$. $\endgroup$ Commented May 8, 2012 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.