1
$\begingroup$

Here is a problem with its solution.

Let $\mathbf{s}_{n\times1}$ is a vector with elements $s_{j}\in\left[-1,1\right]$ for $j=1,2,\ldots,n$. I have the equality $$ \lambda\alpha\mathbf{s}=\mathbf{a} $$ where $\lambda$ is an unknown parameter, $\alpha\in\left(0,1\right)$ is a fixed constant and $\mathbf{a}$ is an $n\times1$ vector. We can show that the minimum value of $\lambda$ that satisfies this equality for some $s_{j}\in\left[-1,1\right]$ is $$ \lambda_{min}=\frac{1}{\alpha}\left\Vert \mathbf{a}\right\Vert _{\infty} $$ where $\left\Vert \mathbf{a}\right\Vert _{\infty}=\max_{j}\left|a_{j}\right|$. I would like to extend this equality with a fixed vector $\mathbf{b}$ like this: $$ \lambda(\alpha\mathbf{s}+\left(1-\alpha\right)\mathbf{b})=\mathbf{a} $$ The problem is the same: What is the minimum value of $\lambda$ (if exists) that satisfies this equality for some $s_{j}\in\left[-1,1\right]$?

I tried to use inequalities with absolute values but could not get a solution.

$\endgroup$
3
  • 1
    $\begingroup$ is $b$ fixed? do you mean 'for some s_j' (instead of 'for all')? $\endgroup$
    – LinAlg
    Commented Dec 27, 2018 at 21:02
  • $\begingroup$ Yes, thanks. I edited the question. $\endgroup$
    – mert
    Commented Dec 28, 2018 at 20:47
  • $\begingroup$ did you appreciate my answer? $\endgroup$
    – LinAlg
    Commented Jan 8, 2019 at 15:03

1 Answer 1

1
$\begingroup$

Your problem can be summarized as: $$\min_{x \in \mathbb{R},y \in [-\alpha,\alpha]^n} \{ x : xy + x(1-\alpha)b = a\}$$ Substitute $xy=z$: $$\min_{x \in \mathbb{R},z \in [-\alpha x,\alpha x ]^n} \{ x : z + x(1-\alpha)b = a\}$$ The dual problem is: $$ \max_{v \in \mathbb{R}^n,w_1 \in \mathbb{R}_+^n,w_2 \in \mathbb{R}_+^n} \{ a^Tv : (1-\alpha)b^Tv + \alpha e^T(w_1+w_2) = 1, \; e^T(v + w_1-w_2) = 0\}$$ I do not see an immediate solution to any of these problems, but the last two problems you can just feed to a linear optimization solver.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .