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