Optimize quadratic problem under collinearity boundary condition

Question

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.

Answer 1

I just solved my own problem. For the records, here the solution I used, as a rough sketch.

The boundary condition $d_i-d_k=\mu(d_k-d_j)$ may be added without problems for fixed $\mu$. For this $\mu$, the usual quadratic programming approaches allow to find $d_\mu^*$ that solves the optimization problem with respect to those conditions.

Resulting is some one-dimensional optimization problem $$ \min_{\mu\in\mathbb{R}} (d_\mu^*)^TQd_\mu^*+cd_\mu^* $$

The derivatives of this objective function may be computed without to much additional work. Thus, Newtons method may be applied for finding a suitable $\mu$ with only a few iterations.

This is not direct solution, as I would have preferred, but it is fast and has the advantage that the parameter $\mu$ is estimated directly and can be reused for other purposes.

Answer 2

So by your collinearity condition, taking any three vectors in the rows of $d$, say $d_i,d_j,d_k$, you can form the equation $c_1 d_i + c_2 d_j + c_3 d_k=0$, with some of the co-efficients not being zero. This amounts to saying that they are linearly dependent. Since you are saying this is true for $i,j,k$. It means that your matrix $d$ is a rank two matrix. Thats all. In terms of column vectors, it means, your first column, should never be a scalar multiple of the second column Now for your optimization problem. You can reformulate it using the $vec$ operator. $vec(d)$ is a $2n\times 1$ vector with its first $n$ elements as the first column of $d$ and the next $n$ elements as next column of $d$. Now use the following identities.

\begin{align} trace(d^TQd)=vec(d)^T(I\otimes Q)vec(d) \\ trace(Cd)=vec(C^{T})vec(d) \end{align} (Please confirm them, am writing them from my memory, but you should get the idea). Defining $c=vec(C^{T})$, $M=(I\otimes Q)$ (kronecker product) and $x=vec(d)$. Thus your problem becomes, \begin{align} \min_{x~\epsilon~\mathbb{R}^{2n\times 1}}~x^{T}Mx+c^{T}x \end{align} This is a quadratic programming problem. Now the condition you wanted was the columns of $d$ shouldn't be scalar multiples of each other. That will depend on the nature of $M$ and $c$ in here.

EDIT--- If you make your collinearity condition little more explicit, say $d_i-d_k=c(d_k-d_j)$, for some given constant 'c', then this is equivalent to putting some linear equality constraints on the orginal problem. In detail, let $A_1$ be a $1\times n$ vector. You can always find a $A_1$ such that $A_1 d=d_i-d_k$, similarly another $A_2$ such that $A_2 d=d_k-d_j$. Combining both you have the linearity equality constraint $(A_1-cA_2)d=0$. But if you try to make $c$ also a variable, then i am not sure how to proceed.