2
$\begingroup$

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum.

Question: Given a function $q: \mathbb R^{N\times N}\mapsto \mathbb R$,

$$ q(\Omega) = \vec r^T\vec r - \vec w^T\vec r\quad\quad\text{s.t.}\quad\quad \|\Omega\|_2^2 =1 $$ where $\vec r$ is the fixed point of the dynamics $$ \dot{\vec r} = \vec w - (\Omega + \lambda I)\vec r\quad\quad\text{s.t.}\quad\quad\vec r > 0. $$ Here $\Omega\in\mathbb R^{N\times N}, \vec r, \vec w\in\mathbb R^{N}$ and $I\in R^{N\times N}$ is the identity matrix. What is the "gradient" $\partial q$ that minimizes $q(\Omega)$?

First attempt: My current hope is to minimize $q$ using subgradient calculus. In a slightly related problem, the function

$$ q(\lambda) = \inf_x \left(f(x) + \lambda g(x)\right) $$

can be shown to be minimized by the subgradient $\partial q = g(x)$ (and convergence can be proofed). However, in my problem the argument of $q$ is in the constraint. For parameters in the constraint an approach like multi-parametric quadratic constrained optimization might go in the right direction. However, they rely on branch-and-cut algorithms whereas I want a distributed gradient approach.

Convex reformulation: I found a way to reformalize my original problem in a convex way:

$$ q(\Omega) = \|\vec w - \Omega{\vec r}\|_2^2 + \lambda \|\vec r\|_2^2\quad\quad\text{s.t.}\quad\quad \|\Omega\|_2^2 =1 $$ with $\vec r$ defined as above. However, now I have the argument both in the objective as well as the "constraint", i.e. in the dynamics of $\vec r$.

Further problem reduction: The problem can be solved using subgradient calculus if the subgradient of the non-differentiable function $\vec r(\Omega)$ can be represented as some analytic expression (which might be impossible due to the positivity constraint).

Thanks for any hints and comments!

$\endgroup$
4
  • $\begingroup$ Is $\Omega + \lambda I$ positive semi-definite? Are you interested in an approximate numerical solution, or a closed-form expression? $\endgroup$
    – Gilead
    May 1, 2013 at 17:00
  • $\begingroup$ p.s. KKT conditions are undefined for open-sets. However if $\Omega + \lambda I \succeq 0$, it would seem that the infimum is 0, attained at $r = 0$. $\endgroup$
    – Gilead
    May 1, 2013 at 17:09
  • $\begingroup$ @Gilead: good point. Actually, in general this problem is ill posed because $(\Omega + \lambda I)\vec r = \vec w$ is usually not fulfilled under positivity constraint. This part has to be framed as a quadratic programming problem. I'll edit the question to reflect this. $\endgroup$
    – Wieland
    May 1, 2013 at 18:53
  • $\begingroup$ @Gilead: I am interested in a gradient descent solution. $\endgroup$
    – Wieland
    May 1, 2013 at 20:14

0

Your Answer

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