0
$\begingroup$

I need to run the following optimization problem in mobile phones. Therefore:

  • Need to run within 0.1 seconds using mobile phone's CPU (you know, kind of weak cpu)
  • Need the installation file to be small, so, for example, cannot package a whole cvx package into my app.

Since I am new to optimization, I do not know what should I do. Thanks for any suggestions!


EDIT:

Indeed I am a programmer, so the question is not about what concrete code to write, but instead about what algorithm/solver should I use. For example, should I use gradient descent? or ADMM (just an example, I know I should not use that)? or something else?

What I guess I should use: Maybe I can write down a optimization algorithm by hand? (For example, for the simplest problem, maybe just write down the gradient manually, then write down gradient descent manually within 10 lines of code). But I do not know what algorithm should I use (seems not "naive" gradient descent). Maybe I can use a optimization package? But is that an overkill, since I only need to optimize this one problem?


Problem details:

$$ \begin{aligned} \arg \min_s \ \ & k_1 \left( \max_{i \in {1...N}} \left( s_i + a_i \right) - \min_{i \in {1...N}} \left( s_i + b_i \right) \right) \\ & k_2 \left( \max_{i \in 1...l} (s_i + a_i) - \min_{i \in 1...l} (s_i + b_i) \right) + \\ & k_3 \left( \sum_{i=2}^N |s_i - s_{i-1}|_1 \right) + \\ & k_4 \left( \sum_{i=2}^{N-1} |2 s_i-s_{i-1}-s_{i+1}|_1^{1.5} \right) \\ s.t.\ \ & 0 \leq s_i \leq H \\ \text{where} \\ & a,b,s \in \mathbb{R}^N \\ & l, N \in \mathbb{N}, \;\; l < N \\ & k_1, k_2, k_3, k_4: \text{weights} \\ & H: \text{a big enough number that will not affect solution} \\ \end{aligned} $$

Explanations:

  • The row of "k2": Similar to the row of "k1", except that only operate with element 1 up to $l$, and ignore the rest elements.
  • The row of "k3": As if slope of $s$.
  • The row of "k4": As if curvature of $s$.

Things that can be changed:

  • The 1.5-th power in row of "k4" can be changed to 2nd power.
  • $0\leq s_i \leq H$ can be modified or deleted

Range:

  • $N \approx 1000$
  • $H \approx 200$
  • $0 \leq a_i \leq H$, $0 \leq b_i \leq H$
$\endgroup$
6
  • $\begingroup$ You should really ask on StackOverflow. $\endgroup$
    – Trebor
    Sep 15 at 1:19
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – Community Bot
    Sep 15 at 1:21
  • $\begingroup$ @Community edited. $\endgroup$
    – ch271828n
    Sep 15 at 1:39
  • $\begingroup$ @Trebor Hi I have edited the question. I think people in stackoverflow knows programming (I know programming as well), but people here know math. The core problem is, what math algorithm should I use? $\endgroup$
    – ch271828n
    Sep 15 at 1:39
  • $\begingroup$ Do you need an optimal solution, or just a "good enough" solution? $\endgroup$
    – 1Rock
    Sep 15 at 1:57
1
$\begingroup$

This will be much easier to solve efficiently if you're willing to change your objective a bit. Objectives with absolute values don't play nicely with basically anything else, while convex quadratic objectives with convex domains are easy to solve. I would suggest turning the first two parts of your problem into constraints (i.e. say $\max \{s_i+a_i\} \le c_1$ and $\min\{s_i +b_i\} \ge c_2$, which turns into $s_i\le c_1-a_i$ and $s_i \ge c_2-b_i$), turn the $|s_i-s_{i-1}|$ into an $(s_i-s_{i-1})^2$, and solve the constrained convex quadratic optimisation problem. Then re-run it all for a few different values of $c_1$ and $c_2$.

Edit: Another idea, you could split the problem into an $i \le l$ and an $i \ge l+1$ sub-problem (if you're able to replace $k_1\max\{s_i+a_i:1 \le i \le n\}+k_2\max\{s_i+a_i:1 \le i \le l\}$ with $(k_1+k_2)\max\{s_i+a_i:1 \le i \le l\}+k_1\max\{s_i+a_i:l+1 \le i \le n\}$). Then you could use a binary search to find a local minimum for $c_3-c_4$ and for $c_1-c_2$ separately. You could come up with some heuristic for the gradient at the crossover point (maybe just minimise $k_4((s_{l-1}-s_l)^2+(s_l-s_{l+1})^2)$, or work out the average gradient $c$ of $\frac{a_i+b_i}{2}$ and minimise $k_4((s_l-s_{l-1}-c)^2+(s_{l+1}-s_l)^2)$).

$\endgroup$
7
  • $\begingroup$ Thanks for the suggestion! I will change the objective and see whether the solution is acceptable or not. Then, how should I solve the constrained convex quadratic optimisation problem? e.g. gradient descent? or something more advanced? $\endgroup$
    – ch271828n
    Sep 15 at 3:26
  • $\begingroup$ In addition, "re-run it all for a few different values of 𝑐1 and c2" - indeed for the second row (marked with "k2") we also need c3 and c4 in order to use this proposed method. Then we have 4 variables to "try a few different values" :/ But these are important and have real meaning in my original problem, so I can say that only "trying a few" may not be good enough... $\endgroup$
    – ch271828n
    Sep 15 at 3:29
  • 1
    $\begingroup$ I haven't used quadratic programming myself, but there are dedicated algorithms for it (for the specific case when your objective matrix is positive semidefinite and your constraints are linear). You'll have to Google around to find a good algorithm (look for "convex quadratic programming"). $\endgroup$
    – 1Rock
    Sep 15 at 3:54
  • 1
    $\begingroup$ Depending how efficient the phone processors are, you might be able to use a few iterations of gradient descent to optimise your $c_1,c_2,c_3,c_4$. Note that increasing $c_1$ and $c_2$ by the same amount doesn't change the problem, so you only really need to optimise $c_1-c_2$ and $c_3-c_4$. $\endgroup$
    – 1Rock
    Sep 15 at 3:58
  • 1
    $\begingroup$ Gradient descent will be much slower than convex quadratic programming $\endgroup$
    – 1Rock
    Sep 15 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.