1
$\begingroup$

I intend to solve for vector $ x \in \mathbb{R}^{N \times 1} $ by solving the following optimization problem

\begin{align} \arg \min_{x} Tr( (\mathbf{K} \mathbf{W})^T \mathbf{P} ( \mathbf{K} \mathbf{W})) - 2Tr( \mathbf{P} \mathbf{K} \mathbf{W}) \end{align} \begin{align} \text{subject to } & x_{i}^{min} \leq x_{i} \leq x_{i}^{max} \\ \end{align} where $Tr()$ is the trace operator, $\mathbf{P} \in \mathbb{R}^{M \times M}$, $\mathbf{W}=\mathbf{A}diag(\mathbf{B} x)$, and $\mathbf{W} \in \mathbb{R}^{D \times M}$, and $\mathbf{K} \in \mathbb{R}^{M \times D}$.

$\mathbf{A} \in \mathbb{R}^{D \times M}$ and $\mathbf{B} \in \mathbb{R}^{M \times N}$ are both positive metrices.

How do I solve it as an inequality constrained optimization problem for $X$ ?

$\endgroup$
12
  • 5
    $\begingroup$ I’m voting to close this question because it's not directly related to signal processing. It's about optimization and should probably be asked on math.SE. $\endgroup$
    – Matt L.
    Apr 28 '20 at 19:13
  • $\begingroup$ If $ A $ is invertible then once you solved for $ A X $ you solved for $ X $. The questions is, what do you know about $ A $? $\endgroup$
    – Royi
    Apr 29 '20 at 21:15
  • $\begingroup$ thanks for your answer @Royi. you may be surprised that I was hoping you answer my question because I saw similar problems solved by you here in stack exchange. actually, I don't have problem finding $\mathbf{X}$ from $\mathbf{AX}$. my main challenge is which constraints should I apply to the above problem. does $\mathbf{X}_{ik}^{min}<\mathbf{X}_{ik}<\mathbf{X}_{ik}^{max}$ mean that $\mathbf{lb}_{ik}<\mathbf{AX}_{ik}<\mathbf{ub}_{ik}$ ? in other words, if $\mathbf{X}$ is bounded, does it mean that $\mathbf{AX}$ is bounded as well? $\endgroup$
    – SJ93
    Apr 30 '20 at 20:10
  • $\begingroup$ I am not so sure I understood your question. $\endgroup$
    – Royi
    Apr 30 '20 at 20:22
  • $\begingroup$ lets look at this problem. if I have a matrix $\mathbf{X}$ in which each element is bounded between a minimum and maximum( $\mathbf{X}_{ik}^{min}<\mathbf{X}_{ik}<\mathbf{X}_{ik}^{max}$). Can I say that each element of $\mathbf{AX}$ has mimum and maximum? if this is not correct, so I can not find $\mathbf{X}$ by simply taking the inverse of $\mathbf{A}$ and multiply it by the solution. $\endgroup$
    – SJ93
    Apr 30 '20 at 21:06
2
$\begingroup$

The problem is given by:

$$\begin{aligned} \arg \min_{x} \quad & \operatorname{Tr} \left( {\left( K A \operatorname{diag} \left( B x \right) \right)}^{T} \left( K A \operatorname{diag} \left( B x \right) \right) \right) - 2 \operatorname{Tr} \left( P K A \operatorname{diag} \left( B x \right) \right) \\ \text{subject to} \quad & {a}_{i} \leq {x}_{i} \leq {b}_{i} \; \forall i \end{aligned}$$

The problem here is the $ \operatorname{diag} \left( \cdot \right) $ operator which makes it hard to infer the gradient.

Yet:

$$ \operatorname{diag} \left( B x \right) = I \circ \left( \boldsymbol{1} {\left( B x \right)}^{T} \right) = I \circ \left( \boldsymbol{1} {x}^{T} {B}^{T} \right) $$

Where $ \circ $ is the Hadamard Product.

Now you can plug it in and use some Matrix Calculus to find the gradient (It seems that using the Frobenius Norm will be useful).
Once you have the gradient you can solve it easily with Projected Gradient Descent Method.

Probably due to use of the Trace Operator you can get better equivalent forms of the problem that takes advantage of $ A $ and $ B $ being Positive definite matrices. As since they are solving for $ y = B x $ is like solving for $ x $.

Remark:

I think the question: Given $ y = A x $ where $ A $ is PD matrix and it is known that $ {a}_{i} \leq {x}_{i} \leq {b}_{i} $ what can be said on $ y $ (Namley how it is bounded) deserves its own question.

Update

Thinking of it, one could calculate the gradient of the Frobenius norm directly:

$$ \frac{\mathrm{d} }{\mathrm{d} x} \frac{1}{2} {\left\| A \operatorname{diag} \left( B x \right) \right\|}_{F}^{2} = {B}^{T} \operatorname{diag} \left( {A}^{T} A \operatorname{diag} \left( B x \right) \right) $$

$\endgroup$
3
  • $\begingroup$ thank you for such a useful explanations. it really helped me to find the right direction. actually, I used the Frobenius product properties to find the gradient with respect to $x$ and then I applied the projected gradient descent to find the solution. in fact I'm not completely sure about my calculations and Matlab implementation. here is my email address: mahshad.javidan@gmail.com I really appreciate if you can send me an email so that I can share my notes with you to make sure they are correct. $\endgroup$
    – SJ93
    May 4 '20 at 19:53
  • $\begingroup$ You can share what you did in the question and I will address it. $\endgroup$
    – Royi
    May 4 '20 at 23:34
  • $\begingroup$ Some tricks related to diag() derivative: math.stackexchange.com/questions/2978183, math.stackexchange.com/questions/3393883, math.stackexchange.com/questions/2611248. $\endgroup$
    – Royi
    May 13 '20 at 8:31
0
$\begingroup$

The problem is given by:

$$\begin{aligned} \arg \min_{x} \quad & \operatorname{Tr} \left( {\left( K A \operatorname{diag} \left( B x \right) \right)}^{T} P \left( K A \operatorname{diag} \left( B x \right) \right) \right) - 2 \operatorname{Tr} \left( P K A \operatorname{diag} \left( B x \right) \right) \\ \text{subject to} \quad & {a}_{i} \leq {x}_{i} \leq {b}_{i} \; \forall i \end{aligned}$$ in order to solve this problrm with Projected gradient descent we need to take the derivative of the first and second term with respect to $x$. for the first term, we can take the advantage of matrix $P$ which is positive-definite matrix and can be wrritten as $P=C^{T}C$. the first term then can be treated as frobenius norm:

$$\begin{aligned} \operatorname{Tr} \left( {\left( K A \operatorname{diag} \left( B x \right) \right)}^{T} P \left( K A \operatorname{diag} \left( B x \right) \right) \right) = {\left\| K A \operatorname{diag} \left( B x \right) C \right\|}_{F}^{2} \end{aligned}$$

then the gradient of the first term can be calculated as

$$\begin{aligned} 2{B}^{T} \operatorname{diag} \left( {(K A)}^{T} (K A) \operatorname{diag} \left( B x \right) CC^{T}\right) \end{aligned}$$

if we consider the second term to be $T=- 2 \operatorname{Tr} \left( P K A \operatorname{diag} \left( B x \right) \right)$ we then have:

$dT=-2(PKA)^{T}:dX$ in which $dX=diag(Bx)$. using the properties of frobenius product we can write:

$dT=diag(-2(PKA)^{T}):di$ and $di=Bdx$ so:

$dT=B^{T}diag(-2A^{T}K^{T}(P)):dx$ and

$dT/dx=-2B^{T}diag(A^{T}K^{T}(P))$

overall the gradient of the above equation can be calculated as:

$$\begin{aligned} 2{B}^{T} \operatorname{diag} \left( {(K A)}^{T} (K A) \operatorname{diag} \left( B x \right) CC^{T}\right) -2B^{T}diag(A^{T}K^{T}P) \end{aligned}$$

I appreciate if you can check and find out whether I am in a right direction or not?

$\endgroup$
3
  • $\begingroup$ I updated my answer with the direct gradient to your formulation, does it help making things simpler? $\endgroup$
    – Royi
    May 7 '20 at 8:17
  • $\begingroup$ I think you forgot to include matrix $P$ in your problem statement above but that's no big deal since $P$ is the covariance matrix and is always semi-positive definite, it can be decomposed into $P=C^{T}C$. I will update my answer based on your update and what I said for the first term. but how about the second term? can I still use the same procedure as before (I mean using frobenius product properties)? $\endgroup$
    – SJ93
    May 7 '20 at 16:43
  • $\begingroup$ Well yes, the same trick. But now that I we have the explicit gradient the problem is easy. $\endgroup$
    – Royi
    May 7 '20 at 16:52

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.