# Finding the closest vector subject to an absolute constraint

I'm trying to solve the following problem: $$\min_b \|d-b\| \\ \text{s.t. } |Ab|^2 \leq y$$ or equivalently $$\min_b \|d-b\| \\ \text{s.t. } |Ab| \leq c = \sqrt{y}$$ Both $d$ and $b$ are vectors. I know how to solve $$\min_b \|d-b\| \\ \text{s.t. } Ab \leq y$$ which is a quadratic program, but I'm not sure whether the problem with the absolute is still a quadratic program. I know that $|Ab|\leq c$ is equivalent to $-c\leq Ab\leq c$, but I guess now that changes the whole problem. I'd be grateful if you guys can provide some guidance. Thanks.

-
What does $\|d - b\|$ mean? Is it $\|d - b\|_2$? Or $\|d - b\|_ {\infty}$? Or $\|d - b\|_1$? – Rod Carvalho Sep 9 '12 at 1:19
If $b$ is a vector, then I assume that $A$ is a matrix and, thus, $A b$ is also a vector? What do you mean by $|A b|$? How can you take the absolute value of a vector? – Rod Carvalho Sep 9 '12 at 1:21
its the euclidean norm $\|d-b\|_2$ – ca_redditor Sep 9 '12 at 1:25
I meant absolute element wise. Absolute value for every element in the vector. – ca_redditor Sep 9 '12 at 1:30
What are the dimensions of matrix $A$? – Rod Carvalho Sep 9 '12 at 2:03

I don't like your notation, so I will use $x$ and $y$ instead of $b$ and $d$, respectively. I will also use strict inequalities. And minimizing the $2$-norm does not yield a quadratic program, but minimizing the squared $2$-norm does.

Let $x \in \mathbb{R}^n$ be the decision variable. We are given vectors $y \in \mathbb{R}^n$ and $c \in \mathbb{R}^m$, and matrix $A \in \mathbb{R}^{m \times n}$. Let $(A x)_i$ denote the $i$-th entry of vector $A x$, and let $c_i$ denote the $i$-th entry of vector $c$. We have $m$ inequality constraints $|(A x)_i|^2 \leq c_i$, which become $-\sqrt{c_i} \leq (A x)_i \leq \sqrt{c_i}$. Let $b := \sqrt{c}$ denote the element-wise square-root of vector $c$. We then have the (strict) linear inequality

$$\left[\begin{array}{c} A\\ -A\end{array}\right] x \leq \left[\begin{array}{c} b\\ b\end{array}\right]$$

which we can write in a more compressed form as $\tilde{A} x \leq \tilde{b}$. We finally obtain a quadratic program in standard form

$$\displaystyle\min_{x \in \mathbb{R}^n} \| x - y \|_2^2 \quad{} \text{subject to} \quad{} \tilde{A} x \leq \tilde{b}$$

Note that the objective function is indeed quadratic and positive definite

$$\| x - y \|_2^2 = (x-y)^T (x-y) = x^T I_{n \times n} x - 2 y^T x + \|y\|_2^2$$

-
That was very neat. Thanks for the help Rod. – ca_redditor Sep 9 '12 at 17:38
What would be the computational complexity here. I'm trying to visualize the problem and I believe the solution in $\mathbb{R}^n$ is either the intersection of the $2m$ linear equation or the orthogonal projection of the original vector on one of the lines and that's only a limited number of possibilities. Would that reduce the complexity? – ca_redditor Sep 10 '12 at 4:31
@atom: a QP solver can handle problems with 1000s of decision variables. You have only three. Why do you care about "complexity"? – Rod Carvalho Sep 12 '12 at 20:04
It takes quite some time to solve this problem with the optimization toolbox in Matlab, That's why I'm concerned about the complexity. – ca_redditor Sep 13 '12 at 2:07
@atom: Are you using the quadprog function? mathworks.com/help/optim/ug/quadprog.html – Rod Carvalho Sep 13 '12 at 2:32

A quadratic program doesn't have strict inequality constraints.

Writing the absolute constraint out explicitly as $Ab<y$ and $-Ab<y$ gives you entirely a set of linear constraints, which are much easier to solve than the absolute value of the constraint. Your main issue, however, is the strict inequality. If it can be relaxed as @Rod Carvalho suggests, when writing the absolute value out explicitly will allow you to use quadratic programming techniques, as per the above link.

-