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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Apr 23, 2020 at 23:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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