1
$\begingroup$

Let $\mathbf{x}$ be a vector of $N$ variables. Then, how can I solve the following optimization problem? \begin{align} \max_\mathbf{x}&\quad \sum_{n} \log(1+\frac{x_n}{\alpha+\sum_{m}\beta_m^{(n)}x_m})\\ \text{subject to}&\quad\mathbf{A}\mathbf{x}\leq \mathbf{p}. \end{align}

Constraints are linear. How about objective function? Is it quasiconcave?

$\endgroup$
  • $\begingroup$ The objective is neither concave not convex. For example, let $n=2, x1 = x2 = \alpha = \beta_1 = 1, \beta_2 = 3$, then Hessian s indefinite (one positive eigenvalue, one negative eigenvalue). Either use a DC (difference of concave or convex) approach in which the non-convex optimization term is iteratively handled (which at best produces a local optimum), or use a non-convex solver (local or global). $\endgroup$ – Mark L. Stone Apr 23 '20 at 23:41
1
$\begingroup$

Here is an attempt for a special case. Let me write your problem as the following: $$ \begin{align} \max_\mathbf{x}&\quad \sum_{n} \log\left(1+\frac{x_n}{f_n(x)}\right)\\ \text{subject to}&\quad\mathbf{A}\mathbf{x}\leq \mathbf{p}. \end{align}. $$ Assume the following: (i) $x> 0$, (ii)the coefficients of $f_n(x)$ are all positive $\forall ~n$, and (iii) all elements of $A$ and $p$ are positive.

Firstly, using AM-GM inequality: $$ 1+\frac{x_n}{f_n(x)} \geq 2\sqrt{\frac{x_n}{f_n(x)}}. $$ This leads to the relaxed problem (barring constants added/multiplied): $$ \begin{align} \max_\mathbf{x}&\quad \sum_{n} \log\left(\frac{x_n}{f_n(x)}\right)\\ \text{subject to}&\quad\mathbf{A}\mathbf{x}\leq \mathbf{p}, ~\mathbf{x}>0. \end{align}. $$ Now, introduce variables $t_n> 0, \forall n$, such that: $$ \frac{x_n}{f_n(x)} \geq \frac{1}{t_n} \Rightarrow x^{-1}_nt_n^{-1}f_n(x) \leq 1. $$ And then the relaxed problem is equivalent to (removing $\log$ as its a monotonic): $$ \begin{align} \min_\mathbf{x}&\quad \prod_{n} t_n\\ \text{subject to}&\quad\mathbf{A}\mathbf{x}\leq \mathbf{p},~\mathbf{x}> 0\\ &~~~~~\mathbf{t}>0,~x^{-1}_nt_n^{-1}f_n(x) \leq 1~ \forall n. \end{align}. $$ Note that the cost function and constraints are all posynomials, with the assumptions made. Thus, this is in the form of a Geometric Program (see https://en.wikipedia.org/wiki/Geometric_programming), which can be converted to a convex program. In fact, softwares like CVXPY will readily solve a problem in this form.

As far as relaxation gap is concerned, that still needs some thought. Anyway, hope this helps.

$\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.