# Quadratic optimization with parameter in constraint

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!

-
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