Multivariate convex optimization problem involving logarithms

87 Views Asked by At

Question-1: $$\min_{a, b} \sum_{i=1}^K b_i f(\frac{a_i}{b_i}) $$

s.t. $$ f(x) = (1+x) \log(1+x) -\log(x) - (1+x) \log(2)$$

$$ \sum_{i=1}^K a_i = 1.$$

$$ \sum_{i=1}^K b_i = 1.$$

$$ a,b > 0. $$

My attempt so far: $f(x)$ is convex. I wrote the Lagrangian, but could not solve for $x$. Also, $\nabla_x f(x)$ is zero at $x=1$. Then minimum for f(x) is at $x=1$. I am not sure if this helps.

Question-2: Thanks a lot to David M. for the answer to the Question-1. Now, I like to extend the question a little more to include solutions with $a_i=0$ or $b_i=0$.

$$\min_{a, b} \sum_{i=1}^K b_i I(a_i>0, b_i>0)f(\frac{a_i}{b_i}) $$

s.t. $$ f(x) = (1+x) \log(1+x) -\log(x) - (1+x) \log(2)$$

$$ \sum_{i=1}^K a_i = 1.$$

$$ \sum_{i=1}^K b_i = 1.$$

$$ a,b\geq 0. $$

1

There are 1 best solutions below

3
On BEST ANSWER

Your objective function is a separable perspective function (see slide 20 of these lecture notes). Basically, because $f(\cdot)$ is convex, the function $g(a,b)=b\cdot f(a/b)$ is convex in $(a,b)$. Hence, your objective is convex as a sum of convex functions. Because both the equality constraints are affine, the KKT conditions are sufficient for this problem, since the Slater Condition is satisfied by the point $a_i=b_i=1/K$ for all $i=1,\dots,K$. In fact, we will show that this point is optimal.

The partial derivative of the objective function with respect to $a_i$ is $$ f'\big(\frac{a_i}{b_i}\big), $$ and the partial derivative of the objective function with respect to $b_i$ is $$ f\big(\frac{a_i}{b_i}\big)-\frac{a_i}{b_i}\cdot f'\big(\frac{a_i}{b_i}\big) $$ If we let $\lambda$ and $\pi$ denote the dual multipliers for the constraints $\sum{a_i}=1$ and $\sum{b_i}=1$, respectively, then the stationarity condition is $$ f'\big(\frac{a_i}{b_i}\big)+\lambda=0\text{ for all }i=1,\dots,K $$ $$ f\big(\frac{a_i}{b_i}\big)-\frac{a_i}{b_i}\cdot f'\big(\frac{a_i}{b_i}\big)+\pi=0\text{ for all }i=1,\dots,K $$ If we plug in $a_i=b_i=1/K$, then, since $f(1)=f'(1)=0$, these two conditions are satisfied by $\lambda=\pi=0$. The points $a_i=b_i=1/K$ are clearly primal feasible, and thus the KKT conditions are satisfied for the proposed point, proving that it is indeed optimal.


Edit There's actually a simpler ad hoc argument here that doesn't use duality theory or the convexity of $f$ (though it's far less general). For your particular function $f$, we have that $f(t)\geq0$ for all $t\geq0$ (let's define $f(0)=\infty$ for simplicity). Hence, the objective function $\sum_ib_if(a_i/b_i)\geq0$ for all $a,b\geq0$ (i.e. this is a globally-valid lower bound). Since $f(1)=0$, this lower bound is attained when $a_i=b_i$ for all $i=1,\dots,K$. The equality constraints dictate that $a_i=1/K$ for all $i$, and thus $a_i=b_i=1/K$ for all $i=1,\dots,K$ is the global minimizer.