2
$\begingroup$

Fix $\{w_n\}_n$ a sequence of positive real numbers, fix positive integers $N,K$, and fix $\eta>1$. I'm looking for a sequence of integers $\{k_n\}_n$ optimizing the following problem:

$$ \begin{aligned} \min \sum_{i=1}^n \frac{w_i}{k_i} \\ \mbox{s.t.}\\ \sum_{i=1}^n k_ik & = K\\ i^{\eta} w_i & \leq k_{i} \qquad \mbox{ for } i=1,\dots,n\\ N & \leq n \end{aligned} $$

Are such problems studied? How to go about it? Since usually $n$ is bounded...

$\endgroup$
5
  • $\begingroup$ Where are $N$ and $\eta$ supposed to be in the optimization problem? Currently they're all $n$'s, which doesn't make sense. Also, what is $\delta$? Is $k$ fixed ahead of time too? $\endgroup$ May 1, 2020 at 12:22
  • $\begingroup$ A distinct but related (now deleted) question was asked a few hours ago by user "probably a human", also using a username of the same style. Are you the same person behind these accounts? $\endgroup$
    – YCor
    May 1, 2020 at 13:00
  • $\begingroup$ Never heard of this person. What did their question ask? (I clicked on the link you posted but I cant see the post) $\endgroup$
    – ABIM
    May 1, 2020 at 13:04
  • 1
    $\begingroup$ I think this question is more suited to: math.stackexchange.com $\endgroup$
    – ABIM
    May 1, 2020 at 14:41
  • $\begingroup$ I'll keep it here for a bit and if nothing I'll move it there. Thanks for the comment. $\endgroup$
    – ABIM
    May 1, 2020 at 16:18

1 Answer 1

1
$\begingroup$

Presuming $k_i$ are constrained to be positive (which I'm assuming to be the case), this can be solved as a Mixed-Integer Second Order Cone Program (MISOCP). Specifically, the reciprocal in the objective function can be handled by use of a rotated Second Order Cone constraint for each term in the objective function.

I will assume that the "k" in the first constraint is either extraneous (i.e., a typo), or is a constant - in either case, that constraint would be linear. Presumably the "constraint" $N \le n$ isn't really a constraint, but a statement about the input values $N$ and $n$; but $N$ doesn't even appear. So I'll handle the essence of what I think the problem is, and assume the rest can be handled by fixing typos in the problem statement.

If a convex optimization modeling tool, such as CVX, CVXPY, or CVXR is used, handling of the reciprocal can be accomplished with a high level function (such as CVX's inv_pos), resulting in an under the hood transformation to SOCP formulation.

Here is CVX code (assume w is a column vector whose ith element is $w_i$), and let kk take the role of k in the 1st constraint, because I am using k as a (column) vector whose ith element is $k_i$.

cvx_begin
variable k(n) integer
minimize(w'*inv_pos(k))  % inv_pos(k) is vector of 1/k_i
subject to
kk*sum(k) == K
(1:n)'.^eta.*w <= k % this is a vector of n constraints
cvx_end

This requires an MISOCP solver, such as Gurobi or Mosek, or if using CVXPY, also CPLEX. Depending on the the input data, it may take a while for the solver to solve it (it is NP-hard, but only because of the integer constraint).

Here is how the reformulation to SOCP constraint works. The term $w_i/k_i$ is handled by introducing a new variable $t_i$, changing the term $w_i/k_i$ to $w_it_i$, and introducing the rotated second order cone constraint (to enforce $t_i = w_i/k_i$, accomp0lished via epigraph formulation due to minimization driving the inequality to be satisfied with equality at the optimum): $$\|1\|_2 \le \sqrt{k_it_i}, t_i \ge 0, k_i \ge 0$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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