2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ do you mean symmetric positive definite (SPD)? $\endgroup$ – Aron Ahmadia May 7 '12 at 11:53
  • $\begingroup$ I mean positive semi-definite (PSD) matrix. $\endgroup$ – mko May 7 '12 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$ – Wolfgang Bangerth May 7 '12 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 May 8 '12 at 9:13
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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