1
$\begingroup$

I have a function $f(A,B)$ that maps a pair of two (tall) matrices, $A$ and $B$, to a scalar cost that I want to minimize. $A$ and $B$ both have $K$ columns. I also want to impose a set of equality constraints, s.t. $\text{exp}(A)^T \text{exp}(B)=J_K$, where $J_K$ is the $K\times K$ matrix of ones. In other words, for every pair of columns in $\text{exp}(A)$ and $\text{exp}(B)$, the dot product of these columns must equal 1.

How would you approach this problem? I've been looking into different kinds of constrained optimization techniques but I haven't managed to get a good sense of which (if any) would be the most promising for my setting.

Edit: To clarify, the $\text{exp}$ function is applied entry-wise to these matrices. An example of a solution that satisfies the constraints is: $$ A = \log \left( \frac{1}{12} \begin{bmatrix} 11 & 1\\ 11 & 1\\ 1 & 11\\ 1 & 11 \end{bmatrix} \right), \text{ } B = \log \left( \frac{1}{12} \begin{bmatrix} 11 & 1\\ 1 & 11\\ 11 & 1\\ 1 & 11 \end{bmatrix} \right) $$ (where the $\log$ function is also applied element-wise.)

If it helps, you can assume that $f$ has the following form: $$ f(A,B) = -(\sum_i {\vec{x}^T}^{(i)} A\vec{y}^{(i)} + {\vec{x}^T}^{(i)} B\vec{z}^{(i)} ) $$ where $\vec{x}$, $\vec{y}$, and $\vec{z}$ are all strictly non-negative column vectors, which happen have the further property that $\vec{x}^T\vec{1}=\vec{y}^T\vec{1}=\vec{z}^T\vec{1}=1$ (i.e. the sum of the entries of each vector equals 1 - not sure if this is relevant but I'll mention it just in case it is). $i$ indexes separate instances of these vectors that we sum over.

$\endgroup$
9
  • 1
    $\begingroup$ Yes, $\text{exp}$ is applied to each entry separately - I have clarified this in my question. There definitely are solutions that satisfy the constraint, and I have provided an example. $\endgroup$ Aug 19 '20 at 14:54
  • 1
    $\begingroup$ Thank you: your example clearly reveals how I misinterpreted your question. I had thought you wanted "every pair of columns in $\exp(A)$ and $\exp{B}$" to mean "every pair of columns in $\exp(A)$" and "every pair of columns in $\exp(B).$" But why introduce $\exp$ at all? It is superfluous because it can be absorbed into $f,$ about which you make no assumptions whatsoever. How one approaches an optimization problem depends very much on the assumed properties of the function one is optimizing. It would also help to indicate how your question may be of any statistical interest. $\endgroup$
    – whuber
    Aug 19 '20 at 14:58
  • 1
    $\begingroup$ I use $\exp$ because it implements the further constraint that $\exp(A)$ and $\exp(B)$ be strictly positive (assuming we're working with real numbers only). I'll add some information about the function, in case that helps. $\endgroup$ Aug 19 '20 at 15:02
  • 2
    $\begingroup$ It helps immensely because it reveals $f$ is a linear function of $(A,B),$ which is a huge simplification. $\endgroup$
    – whuber
    Aug 19 '20 at 15:17
  • 1
    $\begingroup$ Ruben van Bergen, could you help others to gain some intuition behind this problem, by explaining the origin where it comes from. What sort of problem follows these boundaries and cost function? $\endgroup$ Aug 23 '20 at 20:50
3
+100
$\begingroup$

I'm posting some work I've done on your problem, this is not a full answer but I think it almost covers it all.

Loss function

$f$, as you wrote it, is linear. This is good enough, but that equation can be developed a bit to simplify the problem. Let's define two new matrices:

$$ W_A= \sum_i \vec{x}_{(i)}\vec{y}^T_{(i)}; \qquad W_B= \sum_i \vec{x}_{(i)}\vec{z}^T_{(i)}. $$

$W_A$ and $W_B$ have the same shape of $A$ and $B$ and provide the weight for each of their elements, for computing $f$. Actually, the utility function is just the weighted sum of all elements in $A$ and $B$.

Parametrization

Let's call $A' = exp(A)$ and $B' = exp(B)$. You can of course optimize $A$ and $B$, with $f$ strictly linear, but a very complex bounded domain, or optimize $A'$ and $B'$, with the addictional constrain of positiveness, but still a simpler domain (linearly bounded). Of course from $A'$ and $B'$ you can immediately find $A$ and $B$.

I would rather do the latter: even if this way $f$ is not linear anymore, it's still trivially derivable. A quick google search for a viable solver brought me here.

However...

If you multiply any row of $A'$ to some (strictly positive) value $k$, and you divide the corresponding row of $B'$ by the same value, $A'^T B'$ is unchanged (constraints respected), but $f(A, B)$ may do change, and if it does it changes linearly with $k$, because of the properties of logarithm. This means that $k$ either is undetermined or diverges.

$\endgroup$
2
  • $\begingroup$ I think that $k$ is undetermined because the sum of the elements in $W_A$ and $W_B$ are equal (that further property makes it equal to the number of $i$) $\endgroup$ Aug 23 '20 at 21:06
  • $\begingroup$ you are right!. $\endgroup$
    – carlo
    Aug 23 '20 at 21:08

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.