2
$\begingroup$

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\mathbb{R}^{n\times n}$ are some given matrices and $\sigma(k)\in\{1,\dots,L\}$ is a scheduling signal. My goal is to obtain $\sigma(0),\dots,\sigma(N-1)$ such that $$ J = \sum_{k=0}^N \text{trace}(P_{k}) $$ is minimized, provided some initial positive definite matrix $P_0$.

My naive attempt: Up to now, I have only been able to solve this by enumerating all possible combinations of $[\sigma(0),\dots,\sigma(N-1)]\in\{1,\dots,L\}^N$, compute the cost for each of them and choose the one with the least cost. However, as you can see, this solution is not very efficient and can only be used for small $N$. In fact, this solution has complexity that grows as $L^N$.

The question(s):

  • Do you think there is a better way to solve this problem, say by a polynomial time algorithm, or using dynamic programming to find a more efficient (still exponential) solution?
  • Do you think there is a way to find an approximate solution to this problem which can be obtained in polynomial time?
  • Do any of the previous questions answers change if we change (in "high level") $P_{k+1} = F(P_k,\sigma(k))$ for some nonlinear function $F(\bullet,\sigma(k))$.

Any ideas, suggestions or references for me to read are appreciated.

Improve this question
$\endgroup$
11
  • $\begingroup$ Can you give us some concrete values for the parameters? e.g., typical values of $n$ and $N$ and $L$? $\endgroup$ Commented May 20, 2021 at 7:46
  • $\begingroup$ Do the matrices $H_1,\dots,H_L$ have some structure so that the number of possible values for $P_k$ is a lot less than $L^k$? $\endgroup$ Commented May 20, 2021 at 7:47
  • $\begingroup$ Do you require an algorithm that gives you the global minimum, or are you interested in algorithms that don't give the absolute optimum and trade off a suboptimal solution in exchange for more computational efficiency? $\endgroup$ Commented May 20, 2021 at 7:50
  • $\begingroup$ $L=2$ is a good starting point, but $N>100$ is of interest. The matrices $H_i$ do not have structure to simplify the possible values for $P_k$. I am not interested in the global optimum. I prefer focusing on on suboptimal solutions. Thanks $\endgroup$ Commented May 20, 2021 at 9:00
  • 1
    $\begingroup$ Well, it's possible that the trace is nevertheless guaranteed to remain nonnegative in your case, and I think it would be worth investigating whether this is true, since I think it may make the problem easier: It should then be possible to get the trace as low as possible, and thereafter choose matrices $H_i$ as close to $I$ as possible. As a first step, do you see negative traces in any of your examples? $\endgroup$ Commented May 21, 2021 at 9:06

0

Reset to default

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.