8
$\begingroup$

I have a problem in vectors $\mathbf{x} = (x_1,\ldots,x_n)$ and $\mathbf{y}=(y_1,\ldots,y_n)$, where every $x_i,y_i\in\mathbb{R}_{\geq 0}$,

$$\begin{array}{ll} \text{maximize} & \displaystyle\sum_{i=1}^n \left(\frac{y_i}{x_i}\right)^ux_i\\ \text{subject to} & \displaystyle\sum_{i=1}^n x_i = 1\\ & \displaystyle\sum_{i=1}^n y_i = 1\\ & \mathbf{a} \leq \mathbf{x} \leq \mathbf{b}\\ & \mathbf{c} \leq \mathbf{y} \leq \mathbf{d}\end{array}$$

where $u \in (0,1)$ and nonnegative vectors $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$, $\mathbf{d}$ are given. My questions are:

  • Is there an efficient algorithm to solve this?
  • Have you ever seen the same or a very similar optimization problem like the one above?

Addendum: The following conditions are also known: $$ \sum_{i=1}^n a_i<1,\ \sum_{i=1}^n c_i<1,\quad \mbox{and}\quad \sum_{i=1}^n b_i>1,\ \sum_{i=1}^n d_i>1 $$

$\endgroup$
4
  • 1
    $\begingroup$ How large is the $n$ in the problem? $\endgroup$
    – A.Γ.
    May 2, 2017 at 21:53
  • $\begingroup$ @A.Γ. it is chosen by the user. I would say like 100 and at most 1000. The vectors $\mathbf{x}$ and $\mathbf{y}$ are obtained from discretizing two density functions, respectively.. so like if the densities are mean shifted gaussian, I guess around 100 to 1000 samples would be okay. $\endgroup$ May 2, 2017 at 22:06
  • $\begingroup$ A suggestion: You can recast this problem as follows: Replace $y_i$ with $Y_i = y_i^u$ and $x_i$ with $X_i = x_i^{1-u}$, and similarly for the limits $a_i, b_i, c_i, d_i$. Then your problem becomes $$\max_{\mathbf{X},\mathbf{Y}}\sum_{i=1}^n \frac{Y_i}{X_i}\\\mbox{s.t.}\,\,\sum_{i=1}^nX_i^{1/(1-u)}=1,\,\,\sum_{i=1}^nY_i^{1/u}=1\\A_i<X_i<B_i,\quad\forall X_i\\C_i<Y_i<D_i,\quad\forall Y_i$$ Not sure if pushing the exponents to the conditions will be useful or not. $\endgroup$ May 3, 2017 at 0:28
  • $\begingroup$ @PaulSinclair yes. can also be written as vector multiplication like $\mathbf{x}\mathbf{y}^{T}$, where the exponents are put inside. I dont know how it can help. $\endgroup$ May 3, 2017 at 0:36

1 Answer 1

2
$\begingroup$

The minimum with strict inequalities for $a<x<b$, $c<y<d$ is most likely not to exist, as the optimal solution would most probably occur on the boundary and get equalities for some $x_i,y_i$. Is it critical?

Otherwise the objective function

$$\sum_{i=1}^n x_i^{1-u} y_i^u$$

is concave for $u\in(0,1)$ and positive $x,y$, the constraints are simple, the number of variables is not too many, it is a medium-scale problem, so I would expect most of algorithms perform quite well here, for example, the primal-dual interior point method or even Quasi-Newton/Newton method.

Another possibility is to do the dual decomposition. If we introduce the Lagrange multipliers for the equality constraints, the Lagrangian becomes \begin{align} L(x,y,\lambda,\mu)&=\sum_{i=1}^nx_i^{1-u}y_i^u+\lambda\left(\sum_{i=1}^nx_i-1\right)+\mu\left(\sum_{i=1}^ny_i-1\right)\\ &=\sum_{i=1}^n(x_i^{1-u}y_i^u+\lambda x_i+\mu y_i)-\lambda-\mu, \end{align} thus, to calculate the dual problem for given $\lambda,\mu$ one has to solve $n$ independent scalar problems $$ g_i(\lambda,\mu)=\max\ x_i^{1-u}y_i^u+\lambda x_i+\mu y_i\quad\text{subject to } a_i\le x_i\le b_i,\ c_i\le y_i\le d_i $$ and then get the solution from the unconstraint dual problem $$ \min_{\lambda,\mu}\left(\sum_{i=1}^ng_i(\lambda,\mu)-\lambda-\mu\right). $$ If the inequality constraints are compatible with the equalities, i.e. $$ \sum a_i<1,\ \sum c_i<1,\ \sum b_i>1,\ \sum d_i>1 $$ then there is no duality gap, and the primal solution can be constructed from the dual solution.

$\endgroup$
1
  • $\begingroup$ The current version of the answer unfortunately does not help me to solve the problem. $\endgroup$ May 3, 2017 at 22:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .