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
-
0What does $\|d - b\|$ mean? Is it $\|d - b\|_2$? Or $\|d - b\|_ {\infty}$? Or $\|d - b\|_1$? – 2012-09-09
-
0If $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? – 2012-09-09
-
0its the euclidean norm $\|d-b\|_2$ – 2012-09-09
-
0I meant absolute element wise. Absolute value for every element in the vector. – 2012-09-09
-
0What are the dimensions of matrix $A$? – 2012-09-09
-
0Does the constraint inequality need to be strict, or would $A b \leq y$ work? – 2012-09-09
-
0Yes you are correct, I guess there is no optimum solution for |Ab|
– 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$$
-
0That was very neat. Thanks for the help Rod. – 2012-09-09
-
0What 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? – 2012-09-10
-
0@atom: a QP solver can handle problems with 1000s of decision variables. You have only three. Why do you care about "complexity"? – 2012-09-12
-
0It takes quite some time to solve this problem with the optimization toolbox in Matlab, That's why I'm concerned about the complexity. – 2012-09-13
-
0@atom: Are you using the *quadprog* function? http://www.mathworks.com/help/optim/ug/quadprog.html – 2012-09-13
-
0@atom: I never solved an optimization problem with complex decision variables. I never saw one before. – 2012-09-13
-
0Please let me know if know if I'm thinking correctly. if $x \in \mathbb{C}^n $, the objective function (the minimization of the euclidean distance) would consist of two quadratic functions, one for the real part and one for imaginary. $$\| x - y \|_2^2 = Re\{x^T\} I_{n \times n} x - 2 Re\{y^T\} x + \|Re\{y\}\|_2^2 + Img\{x^T\} I_{n \times n} x - 2 Img\{y^T\} x + \|Img\{y\}\|_2^2 $$Minimization of the whole objective function is equivalent to minimizing each quadratic function separately. – 2012-09-13
-
0The constraints $|(A x)_i|^2 \leq c_i$ are now equivalent to $(A Re\{x\})_i)^2 + (A Img\{x\})_i)^2 \leq c_i$. I guess this would be satisfied if $(A Re\{x\})_i)^2 \leq 0.5c_i$ and $(A Img\{x\})_i)^2 \leq 0.5c_i$ – 2012-09-13
-
0Yes I'm using quadprog and it does not accept any complex inputs. I'm trying to manipulate the problem and separate it into two real quadratic functions with two real constraints. – 2012-09-13
-
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