Summary
Given the optimization problem $ \min_{d\in\mathbb{R}^{n\times 2}} \text{trace}\big( d^T Q d+Cd\big) $ for some $n\times n$-matrix $Q$ and another matrix $C\in\mathbb{R}^{2\times n}$, I'd like to add the boundary conditions on the collinearity of differences of rows of $d$.
Formally speaking: Let $d=[d_1,\ldots, d_n]^T$ with $d_i\in\mathbb{R}^2$. For given $i, j, k$ I'd like the vectors $d_i-d_k$ and $d_k-d_j$ to be collinear. What is the most efficient way to solve a problem like this?
More elaborated problem
Of course I can modify the original optimization problem to be of the form $ \min_{d\in\mathbb{R}^{2n}} d^T \tilde{Q} d + \tilde{c}d $ with $ \tilde{Q}=\begin{bmatrix} Q & 0 \\ 0 & Q\end{bmatrix},\quad \tilde{c}=[c_1, c_2], $ and $c_1, c_2$ the rows of $C$. This problem may be solved by solving a system of linear equations as it is well known in theory and practice.
My boundary condition furthermore may be formulated as (those are the characterizations I could think of)
- $\det(d_i-d_k, d_k-d_j)=0$
- $\frac{\langle d_i-d_k, d_k-d_j\rangle}{\| d_i-d_k\|\cdot \|d_k-d_j\|}=\pm 1$
The most promising is the determinant. Using the correct indices, the determinant may be written as $d^t A d$ with $d\in\mathbb{R}^{2n}$. My first thought was to reformulate my optimization problem like this: $ \min_{d\in\mathbb{R}^{2n}} d^T \tilde{Q} d + \tilde{c}d +\mu d^TAd, $ which still would be quadratic. However, as it is obvious, $d^TAd$ may be arbitrary small, thus that idea is flawed. Of course, one could do $ \min_{d\in\mathbb{R}^{2n}} d^T \tilde{Q} d + \tilde{c}d +\mu (d^TAd)^2. $ That one, however, is not even close to quadratic anymore, which catapults the complexity of the problem to a whole new level.
Note, that $n$ is not very big ($n=20$ may be a reasonable guess). However, that problem has to be solved thousands and thousands of times as fast as possible.
My favorite solution would be to get the boundary conditions written as something at most quadratic. If that is not possible, I am looking forward to your ideas on what the most performant optimization algorithm for that particular problem is.
P.S.: There are other boundary conditions of the form $d_i=d_{i+1}$. Those, however, do not really form a problem and probably can be ignored for the matter at hand.