1
$\begingroup$

My problem is as follows:

\begin{align} \underset{\boldsymbol{x}}\max \quad & \boldsymbol r^T\boldsymbol x-\boldsymbol t^T\boldsymbol x \\ \text{s.t.} \quad & \boldsymbol1^T\boldsymbol x = N \\ & e^{- x_i/N} \geq \eta_i \quad \forall i \in \left\{ 1, 2, ... , card(\boldsymbol x) \right\} \quad and \quad \boldsymbol 0 \leq \boldsymbol \eta \leq \boldsymbol 1\\ \end{align}

It is a convex problem (LP), and thus I can solve with CVX using solvers. However, in doing that, I have to give heuristic inputs for $\eta_i$. That is, I make a "grid" for $\eta_i$ in the range [0,1] like (0, 0.1, 0.2,...,1), and then run the optimisation on the different values to find which value(s) of $\boldsymbol \eta$ give the best $\boldsymbol x$. But this way of doing parameter selection is time consuming and tedious, as I need to run solve the optimisation problem for each $\boldsymbol \eta$. So, I would like to have an analytic solution (closed form?) for $\boldsymbol x$ in terms of the variable $\boldsymbol \eta$ and the constants $N$, $\boldsymbol r$ and $\boldsymbol t$. Granted, I would still need to solve the problem for each $\boldsymbol \eta$, but I could at least save time for running the optimisation if there is a closed form solution. Is it possible to do so? Alternately, is there a better way of optimal parameter selection that bypasses the need to "randomly" try out values for $\boldsymbol \eta$ from a grid?

$\endgroup$
  • $\begingroup$ Taking the log of both sides, the inequality constraint becomes $$x_i \leq N \log \left( \frac{1}{\eta_i} \right)$$ $\endgroup$ – Rodrigo de Azevedo Aug 11 '17 at 5:54
  • $\begingroup$ @RodrigodeAzevedo Ok, and then? $\endgroup$ – Kristada673 Aug 11 '17 at 6:00
  • $\begingroup$ And then you have a linear program. Wouldn't looking for an analytical solution be too ambitious? $\endgroup$ – Rodrigo de Azevedo Aug 11 '17 at 6:03
  • $\begingroup$ Yeah, that's true. But if it is achievable by relaxing the constraint(s) (meaningfully and frugally), I'm ok with it. Because having an approximate analytical solution is better than having an accurate solution with heuristic inputs. $\endgroup$ – Kristada673 Aug 11 '17 at 6:06
  • $\begingroup$ Why are you looking for an explicit formula? If we can translate it to a linear program, then an explicit formula exists. It just takes $O(2^{card(\mathbb{x})})$ time to compute. Don't you prefer a computatonally cheap way to solve the problem, instead of an explicit formulaa? $\endgroup$ – Alex Shtof Aug 12 '17 at 14:45
0
$\begingroup$

For starters, when $r_i < t_i$, then $x_i$ is obviously $0$. So you can assume wlog that $\boldsymbol{r} \ge \boldsymbol{t}$. Second, since the $x_i$ are continuous, not discrete (otherwise you would have an NP-hard knapsack problem), you can use a greedy algorithm: sort the $x_i$ in decreasing order of $r_i-t_i$ and set, using Rodrigo de Azevedo's reformulation of the second constraint, namely $x_i\le N\log(1/\eta_i)$, $$ x_1 = \min\left\{N, N\log\left({{1}\over{\eta_1}}\right)\right\},$$ $$ x_2 = \max\left\{0,\min\left\{N-x_1, N\log\left({{1}\over{\eta_2}}\right)\right\}\right\},$$ and so on. This is not quite a closed-form solution, but it is probably the best you can do.

$\endgroup$
  • $\begingroup$ Do you have a proof of optimality? For example, I am not sure that your construction will lead to a feasible vector. How do you know that $\mathbb{1}^T \mathbb{x} = N$ is satisfied? Some of the $x_i$'s might be the second term of the minimum, and not the first one. $\endgroup$ – Alex Shtof Aug 13 '17 at 8:22
  • $\begingroup$ If the problem has a feasible solution, this procedure will find it, and the tail of the $x$ vector will have zeroes. If feasibility is a concern, then verify that the $x_i$ sum to $N$. If they do not, the problem is infeasible. The idea is simple: Allocate as much as possible to the most profitable dimension. If there is nothing left over, great. (This means $x_1=N$.) If there is, allocate as much of the rest as possible to the second dimension, etc. If at the end you have not allocated everything, you have an infeasible problem. $\endgroup$ – user3697176 Aug 13 '17 at 11:35
  • 1
    $\begingroup$ This is not a proof. The greedy algorithm may fail to find a feasible solution, since maybe allocating as much as possible to the first dimensions isn't a part of any feasible solution, but a different ordering might still find a feasible solution. $\endgroup$ – Alex Shtof Aug 13 '17 at 11:59

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.