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.


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.

  • $\begingroup$ Thanks for your input. However, after reading your answer, I'm not sure I made myself clear enough - in fact, my original question was misleading in one point: I like the vectors $d_i-d_k$ and $d_k-d_j$ to be collinear for given, specific values of $i,j,k$. Furthermore, I believe your argument is valid only in one direction. If $d_i, d_j, d_k$ are linearly dependent (which is always true in the 2-d case), their differences still do not have to be collinear. The reformulation using $vec$ was what I did in my original question, just without your notational trick. $\endgroup$ – Thilo Nov 8 '12 at 10:08
  • $\begingroup$ oh kk,,, then it is more involved,,I agree. I didn't see your elaborate version,,,thats why that happened,,let me see what i can do $\endgroup$ – dineshdileep Nov 8 '12 at 10:20
  • $\begingroup$ @Thilo see the edit $\endgroup$ – dineshdileep Nov 8 '12 at 10:32
  • $\begingroup$ Yep, I already had the idea with the fixed $c$. However, the application definitely allows no a priori knowledge on the length differences of those vectors (Application: The $d_i$ are control points of splines representing movements. Collinearity means same direction of derivatives at some points, without restrictions on the velocity. Fixing $c$ would mean to require a certain ratio of velocities, which I can not assume.) $\endgroup$ – Thilo Nov 8 '12 at 10:39
  • $\begingroup$ oh ok,,out of my league now!!:) $\endgroup$ – dineshdileep Nov 8 '12 at 10:42

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.


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.