3
$\begingroup$

Let $x_1,\dots,x_n$ be a set of given vectors in $\mathbb{R}_{+}^d$. Let $c_1,\dots,c_n$ be given positive constants. I am interested in finding the vectors $w_1,\dots,w_n$ in $\mathbb{R}_{+}^d$ that solves the optimization problem \begin{align} \max_{w_1,\dots,w_n}\sum_{i=1}^{n}c_i\frac{\exp(w_i^Tx_i)}{\sum_{j=1}^{n}\exp(w_j^Tx_i)} \end{align} I am not even sure how to start around this and I currently use a out-of-the-box optimization algorithm. Is this type of problem known in literature? What would be some starting point?

$\endgroup$
1
$\begingroup$

Here is an approach which is quite possibly sub-optimal, but I hope it helps.

Let me use a special form of AM-GM inequality (see ``Proofs from the Book'' for a beautiful proof) to get a lower bound on you cost function. Given positive numbers $\{a_1,\cdots, a_n\}$ and positive numbers $\{p_1,\cdots, p_n\}$ such that $\sum^n_{k=1}p_k = 1$, the following is true: $$ p_1a_1+\cdots+p_na_n \geq a_1^{p_1}a_2^{p_2}\cdots a_n^{p_n}. $$ The same applied inequality substituting $a_i = \frac{\exp(w_i^Tx_i)}{\sum_{j=1}^{n}\exp(w_j^Tx_i)}$ and $p_i = \frac{c_1}{\sum^n_{k=1}c_k}$, we get: $$ \sum_{i=1}^{n}\left(\frac{c_1}{\sum^n_{k=1}c_k}\right)\frac{\exp(w_i^Tx_i)}{\sum_{j=1}^{n}\exp(w_j^Tx_i)} = \sum_{i=1}^{n}\tilde{c_i}\frac{\exp(w_i^Tx_i)}{\sum_{j=1}^{n}\exp(w_j^Tx_i)} \geq \prod_{i=1}^n \left(\frac{\exp(w_i^Tx_i)}{\sum_{j=1}^{n}\exp(w_j^Tx_i)}\right)^{\tilde{c_i}}. $$ Maximizing the last term in the last inequalities would serve as a relaxation to the original problem. Towards that end, we maximize instead the $\log$ of the last term, since composing wtth a monotonic function does not change optima. Thus, the relaxed problem is given by (post $\log$): $$ \max_{w_1,\dots,w_n} \left\{\left(\sum^n_{i=1}\tilde{c_i}\left(w_i^Tx_i\right)\right) - \sum^n_{i=1}\tilde{c_i}\log\left(\sum_{j=1}^{n}\exp(w_j^Tx_i)\right)\right\}, ~\mbox{subject to}~ w_i\geq 0~\forall i. $$ The above optimization problem is concave and can be solved easily using CVXPY, or optimizers alike.

As far as the extent of sub-optimality is concerned, note that $\sum_{i=1}^n c_i$ is a natural upper bound for the cost function. Thus the relaxation gap be at most the difference between $\sum_{i=1}^n c_i$ and the value at the $\arg\max$ of the relaxed problem. Also, if the relaxed problem is unbounded, the original problem is unbounded as well.

$\endgroup$

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.