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

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

1 Answer 1

Reset to default
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

Improve this answer
$\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, 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$
    – Arnold Neumaier
    May 8, 2012 at 15:43

Your Answer

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

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