Finding the closest vector subject to an absolute constraint

Question

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.

Answer 1

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$$

Answer 2

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.