Maximize function consisting of Sum, Vectors and Signum function

98 Views Asked by At

Edit: Thanks for edit :-)

Can I ask please, how to maximize
$$\sum ({v_3 \text{sign}({xv_1+yv_2)}})\quad\text{where}$$ (edit: sum of i in 1..1000 ... 1 to length(v1) .. 3 vectors of same length $$\sum_{i=1}^n ({v_3[i] \text{sign}({xv_1[i]+yv_2[i])}})\quad\text{where}$$

$v1,v2,v3,\cdots\space $-vector(s) are real numbers, generated around $0\space$ [x,y=...value(s)] to find

I even don't how to partially derivate it... that signum function

I need find vales $(x,y)$. (in future I will try to use $n$ number of vectors, but solution for $2$ is best start. For one vector it's easy but for $2$ vectors - high mathematician skill required)

thanks a lot if somebody know how to solve it

1

There are 1 best solutions below

8
On BEST ANSWER

I don't there exists as a closed form solution of this. So there might not be a formula that expresses the optimal solution.

However you express your problem as Quadratically Constrained Linear Program.

First we introduce a vector of dummy variables $s$ and rewrite our objective as: $$\max \sum_i v_3[i]s[i]$$ subject to some additional constraints. We observer that $s$ has to have the same values as $\text{sign}$ term: $\forall i: \ s[i] \in \{-1,0,1\}$. This can be expressed as the constraint $s^2 = s^4$ which can be expressed as two quadratic constraints by yet another vector of dummy variables $j$. So we now got the constraints: $$j[i] = s[i]^2$$ $$j[i]^2 = s[i]^2$$

Please observe that the value of $xv_1[i]+yv_2[i]$ is irrelvant only the sign matters, so we loose no information by constraining it's value to be $\in \{-1,0,1\}$. Using this we can formulate this constraint:

$$s[i] = x*v_1[i] + y*v_2[i]$$

The following QCLP gives you your solution: $$\max_{s[1],...,s[n],j[1],...,j[n],x,y} \sum_{i=1}^n v_3[i]s[i]$$ subject to

$$\forall i \in \{1, ..., n\}: \ j[i] = s[i]^2$$ $$\forall i \in \{1, ..., n\}: \ j[i]^2 = s[i]^2$$ $$\forall i \in \{1, ..., n\}: \ s[i] = x*v_1[i] + y*v_2[i]$$

There is a large array of programs that can solve QCLP some of them might also be callable from R.