2
$\begingroup$

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.

  • 0
    What does $\|d - b\|$ mean? Is it $\|d - b\|_2$? Or $\|d - b\|_ {\infty}$? Or $\|d - b\|_1$?2012-09-09
  • 0
    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?2012-09-09
  • 0
    its the euclidean norm $\|d-b\|_2$2012-09-09
  • 0
    I meant absolute element wise. Absolute value for every element in the vector.2012-09-09
  • 0
    What are the dimensions of matrix $A$?2012-09-09
  • 0
    Does the constraint inequality need to be strict, or would $A b \leq y$ work?2012-09-09
  • 0
    Yes you are correct, I guess there is no optimum solution for |Ab|2012-09-09

2 Answers 2

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

  • 0
    That was very neat. Thanks for the help Rod.2012-09-09
  • 0
    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?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
  • 0
    It 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.html2012-09-13
  • 0
    @atom: I never solved an optimization problem with complex decision variables. I never saw one before.2012-09-13
  • 0
    Please 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
  • 0
    The 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
  • 0
    Yes 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
1

A quadratic program doesn't have strict inequality constraints.

Writing the absolute constraint out explicitly as $Ab and $-Ab 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.