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
    Yes you are correct, I guess there is no optimum solution for |Ab|Aare MXN and M<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
    @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.