1

I want to minimize an objective function of the following form: $$ \begin{split} \text{Minimize} \quad & x^T D_x x + y^T D_y y + z^T D_z z + q_x^T x + q_y^T y + q_z^T z + \lambda \cdot \begin{Vmatrix} y - x \\ z - x \end{Vmatrix}_2 \end{split} $$

where $x, y, z \in R^n, \lambda > 0$ and $D \in R^{3n}$ is a positive-definite diagonal matrix. In addition, $n$ is "small" - less than 20.

I want to be able to solve it as efficiently as possible. I believe that there is a way to construct a dual that is a simple 1-D optimization problem over an interval that is quickly solvable, but I was not able to do so.

Alex Shtoff
  • 12
  • This problem has a trivial dual. To get the dual that you want, I think you need to move the norm into a constraint by adding a new variable $|(y-z,z-x)|_2\leq w$. – Michael Grant Dec 15 '14 at 04:27
  • 1
    Well, that's why I said "a dual" and not "the dual". There is a trick I am missing here. Using the idea you suggest, creating the dual is as hard as solving the original problem. Just look at the Lagrangian. That's why I believe that this does not lead to a useful dual problem. – Alex Shtoff Dec 15 '14 at 07:23

1 Answers1

2

Let's look at the generic problem $$\inf_x \tfrac{1}{2}x^TPx+q^Tx+\lambda\|Rx\|_2$$ We can use a little trick to quickly get a dual without going through the full Lagrangian motions: since $\|w\|_2=\sum_{\|v\|_2\leq 1}v^Tw$, we have $$\inf_x \sup_{\|w\|_2\leq 1} \tfrac{1}{2}x^TPx+q^Tx+w^TRx$$ Throwing caution to the wind (hey this isn't a journal article) we swap the $\inf$ and the $\sup$: $$\sup_{\|w\|_2\leq 1} \inf_x \tfrac{1}{2}x^TPx+q^Tx+w^TRx$$ Since $P$ is positive definite the inner problem has a unique minimizer: $$Px+q+R^Tw=0\quad\Longrightarrow\quad x = -P^{-1}(R^Tw+q)$$ Substitution yields $$\begin{aligned} &\sup_{\|w\|_2\leq 1} -\tfrac{1}{2}(R^Tw+q)^TP^{-1}(R^Tw+q)= -\inf_{\|w\|_2\leq 1} \tfrac{1}{2}\|P^{-1/2}(R^Tw+q)\|_2^2 \\&\qquad= -\inf_{\|w\|_2\leq 1} \tfrac{1}{2}w^TRP^{-1}R^Tw+q^TP^{-1}R^Tw+\tfrac{1}{2}q^TP^{-1}q \end{aligned}$$

This is easier to solve than the original problem, for sure.

In fact, it's the well-known trust region subproblem. Here's what we know about it. First, try computing the unconstrained minimizer $w=(RP^{-1}R^T)^{-1}RP^{-1}q$. If it happens to satisfy $\|w\|_2\leq 1$, you're done: that's your constrained optimum. Otherwise, we know that the solution $w$ is a solution of the problem $$\inf_w \|P^{-1/2}(R^Tw+q)\|_2^2+\bar{\lambda}\|w\|_2^2$$ where $\bar{\lambda}\geq 0$ is chosen so that $\|w\|_2=1$. For fixed $\bar{\lambda}$, the solution to this problem is just $(RP^{-1}R^T+\bar{\lambda}I)^{-1}RP^{-1}q$. You can use bisection to find the value of $\bar{\lambda}$.

If you're willing to compute the eigenvalue decomposition of $R^TP^{-1}R$ (or the SVD of $P^{-1/2}R$), you can solve it in $O(n)$ operations after that, I believe. But I don't know if you can readily exploit the structure of $P$ and $R$ here to speed up that SVD.

Michael Grant
  • 19,450