3
$\begingroup$

Can we get the closed-form solution for this problem?

\begin{align} \min&\quad\sum_{i=1}^N\frac{K_i}{x_i\log_2(1+\frac{Q_i}{x_i})}\\ {\rm{s.t.}}&\quad\sum_{i=1}^N x_i\le X \end{align}

wherein $K_i>0$, $Q_i>0$ and $X>0$ are constants, and $x_i>0$ for $i\in\{1,\ldots,N\}$ is a continuous optimization variable.

$\endgroup$
2
  • 1
    $\begingroup$ It's easy to prove this is a convex optimization problem. It satisfies the lnearity constraint qualification. Therefore, the KKT conditions are necessary and sufficient for (global) optimality. Have you tried applying KKT? if so, what happened? if not, then please do so. $\endgroup$ – Mark L. Stone Sep 5 '20 at 13:04
  • 1
    $\begingroup$ I have tried this. I can get $$K_i*\left(\log_2(1+\frac{Q_i}{x_i})-\frac{1}{\ln2 (x_i+Q_i)}\right)=u$$ and $$\sum_i^Nx_i-X=0$$. However, I don't know how to eliminate multiplier $u$. Perhaps the Lambert function can be used to solve it, but the $u$ is also involved in the expression. What should I do? $\endgroup$ – qinqinxiaoguai Sep 5 '20 at 15:42
1
$\begingroup$

It's easy to prove this is a convex optimization problem, as can be seen in the DCP formulation below. The problem satisfies the linearity constraint qualification. Therefore, the KKT conditions are necessary and sufficient for (global) optimality. Nevertheless, perhaps the KKT conditions can only be solved numerically.

It is easy to enter this problem into a convex optimization modeling tool, such as CVX. Here is a CVX program to solve it. I will assume K and Q are column vectors, whose ith elements are $K_i$ and $Q_i$ respectively.

cvx_begin
variable x(N)
minimize(log(2)*K'*inv_pos(-rel_entr(x,x+Q)))
sum(x) <= X
cvx_end

The rel_entr function constrains its arguments, hence x, to be $\ge 0$.

CVX will call a solver, and if the solution status is Solved, x will be populated with its optimal value. Given the use of the exponential cone, Mosek, which natively supports it, is the preferred solver under CVX for this problem.. Otherwise, install CVXQUAD and its exponential.m replacement - see http://ask.cvxr.com/t/cvxquad-how-to-use-cvxquads-pade-approximant-instead-of-cvxs-unreliable-successive-approximation-for-gp-mode-log-exp-entr-rel-entr-kl-div-log-det-det-rootn-exponential-cone-cvxquads-quantum-matrix-entropy-matrix-log-related-functions/5598 .

Edit: In lieu of closed-form solutions, Differentiable Convex Optimization Layers, cvxpylayers, in CVXPY allows insertion of the solution of DCP-compliant convex optimization problems, such as this, as a differentiable layer in lieu of nonlinear activation functions - see the blog Differentiable Convex Optimization Layers - CVXPY creates powerful new PyTorch and TensorFlow layers

$\endgroup$
5
  • $\begingroup$ Thank you very much. I want to find a closed-form solution to this problem. If it can only be solved numerically, I will try to use CVX. $\endgroup$ – qinqinxiaoguai Sep 6 '20 at 2:47
  • $\begingroup$ @qinqinxiaoguai No one has provided a closed-form solution, so I doubt one is forthcoming. Numerical optimization programs wouldn't exist if all optimization problems had nice closed-form solutions. See my Edit for an alternative to closed-form solutions within neural networks. $\endgroup$ – Mark L. Stone Sep 6 '20 at 13:54
  • $\begingroup$ @qinqinxiaoguai I don't think a closed-form solution is forthcoming, so youi can feel free to accept this answer. $\endgroup$ – Mark L. Stone Sep 7 '20 at 12:14
  • $\begingroup$ The downvoter is welcome to post their closed-form solution.If a valid such solution is posted, I will downvote my answer. $\endgroup$ – Mark L. Stone Sep 7 '20 at 18:30
  • $\begingroup$ The closed-form solution may not be forthcoming. Thank you for your help. $\endgroup$ – qinqinxiaoguai Sep 10 '20 at 0:02

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.