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.
Finding the closest vector subject to an absolute constraint
-
0Yes you are correct, I guess there is no optimum solution for |Ab|
A are MXN and M<– 2012-09-09
2 Answers
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$
-
0@atom: If you have 3 complex decision variables, why don't you use 6 real decision variables? MATLAB won't accept complex numbers. I really have no idea why you're using complex decision variables. What kind of problem are you trying to solve? – 2012-09-13
A quadratic program doesn't have strict inequality constraints.
Writing the absolute constraint out explicitly as $Ab