Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
Is $\Omega + \lambda I$ positive semi-definite? Are you interested in an approximate numerical solution, or a closed-form expression? –  Gilead May 1 '13 at 17:00
    
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$. –  Gilead May 1 '13 at 17:09
    
@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. –  Wieland May 1 '13 at 18:53
    
@Gilead: I am interested in a gradient descent solution. –  Wieland May 1 '13 at 20:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.