I am looking at a problem arising in finite element analysis. Let $K \subset R^2$ be a triangle, and assume that $\Phi := \{\phi_1, \ldots, \phi_N\}$ span some space $V(K)$. There is some function $v \in V(K)$; expressed in local coefficients, $v = \sum_i v_i \phi_i$.

I have a matrix $A$ (the local stiffness matrix: $A_{ij} = \int_K \nabla \phi_i \cdot \nabla \phi_j$), which is square, symmetric, positive semidefinite, but not invertible. I have a vector $\vec b$ (with $b_i = \int_K \phi_i$).

I am trying to solve the following quadratic programming problem:

Minimize $\frac{1}{2} (\vec x - \vec v)^\top A (\vec x - \vec v)$ for $\vec x$, subject to $\vec x^\top \vec b = \vec v^\top \vec b$.

Looking through quadratic programming texts, $\vec x$ exists and is unique when $A$ is invertible (which I obviously don't have). Can I prove existence and uniqueness some other way?


  • $\begingroup$ I am going to make a brain-dead remark. If $A=0$, of course you don't have uniqueness. Same goes with the matrix $A=\begin{bmatrix} 0&0\\ 0&1 \end{bmatrix}$ on the constraint $\vec x \cdot (0,1)=0$. Why do you expect uniqueness in your case? $\endgroup$ – Giuseppe Negro Apr 6 '17 at 14:41

Let $y = x-v$, your original problem becomes \begin{align*} \min\quad& \frac12y'Ay \\ \text{s.t}\quad & b'y = 0 \end{align*} If $y^*$ is a solution, then $y^*+z$ is also a solution as long as $z$ satisfies \begin{align} Az & = 0 \\ b'z & = 0 \end{align} That means $z$ is a eigenvector of $A$ with zero eigenvalue, and also $z$ is orthogonal to $b$. Only in the case $A$ has only one zero eigenvalue and $b$ is not orthogonal to the corresponding eigenvector, such $z$ doesn't exist.


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.