5
$\begingroup$

Is there a way to transform the following optimization problem into an equivalent convex problem:

$ \mathrm{min}_x \, \Large \left\{ \sum\limits_{i=1}^n \frac{\langle x,a_i \rangle}{\langle x,b_i\rangle} \right\} $

with $x \in \mathcal{X}$, and $ \mathcal{X} \subset \mathbb{R}^n$ is a convex subset of $\mathbb{R}^n$, and $\langle\cdot,\cdot\rangle$ denotes the standard scalar-product in $\mathbb{R}^n$. Moreover, $a_i, b_i \in \mathbb{R}^n$ and $b_i > 0 \,\,\, \forall \, i$ (i.e. all components of the vectors $b_i$ are positive. If necessary, the problem could be reformulated such that also the vectors $a_i$ have only positive components).

The convex set $\mathcal{X}$ is defined via the inequalities

$c_1 \leq x \leq c_2, \,\,\,\,\,\, c_1,c_2 >0$

$\sum_{i=1}^n \langle x, A_i\, x \rangle \,\, \leq c_3$

with positive vectors $c_1$ and $c_2$ and a positive constant $c_3$ and symmetric, positive semi-definite matrices $A_i$. Moreover, there are further linear equality constraints of the form

$f(x) =c_4$ with a linear function $f$.

I want to transform this problem to an equivalent convex optimization problem.

I have constructed several possibilities to transform this problem to a convex one for $n=1$. In this case I can also prove several nice properties. However, for $n>1$ I was not able to transform this problem to a convex one. Does anybody know whether this is possible, and if yes how can it be done?

Thank you very much!

$\endgroup$
  • $\begingroup$ @Michael it is a common way to write scalar products. $\endgroup$ – mathreadler Feb 16 '18 at 17:11
  • $\begingroup$ yep sometimes is written $(x,A_i x)$ instead $\endgroup$ – mathreadler Feb 16 '18 at 17:13
  • $\begingroup$ seas.ucla.edu/~vandenbe/ee236a/lectures/lfp.pdf $\endgroup$ – AndreaCassioli Feb 16 '18 at 17:53
  • $\begingroup$ Ah, thank you for the editing. Yes, I should have used the \langle and \rangle commands. Indeed, I mean the scalar product. $\endgroup$ – Nicolai Feb 16 '18 at 18:00
  • $\begingroup$ @ AndreaCassioli: Ah, thank you. This is indeed very similar to what I have done for the n=1 case. Unfortunately, it does not deal with the general case where there is a sum over n of such terms. $\endgroup$ – Nicolai Feb 16 '18 at 18:03
3
$\begingroup$

General problems of the type you give are NP-hard. However, structured classes can be solved. Here is an argument that shows hardness in general:

Consider the (hard) integer program of finding a vector $x \in \mathbb{R}^n$ to satisfy the following constraints:
\begin{align} &Ax \leq b \\ &\sum_{i=1}^n x_i = k\\ &x_i \in \{0, 1\} \quad, \forall i \in \{1, ..., n\} \end{align}

Assume the integer program is feasible (so there exists an integer solution that satisfies the constraints). Let's define a new (non-integer) problem of the general type you pose, then show it could be used to solve the above (hard) problem. The new problem is:

\begin{align} \mbox{Minimize:} \quad & \sum_{i=1}^n \frac{x_i}{1+x_i} \\ \mbox{Subject to:} \quad & A x\leq b\\ &\sum_{i=1}^n x_i = k \\ &x_i \in [0,1] \quad , \forall i \in \{1, ..., n\} \end{align}

Claim: If the integer program is feasible, then the new problem is also feasible and its solution satisfies the constraints of the integer program.

Proof: Let $y^*$ be a solution to the integer problem. Then $y_i^* \in \{0,1\}$ and $\sum_{i=1}^n y_i^*=k$. Notice that the function $x/(1+x)$ satisfies $$ (Fact 1): \quad \frac{x}{1+x} \geq \frac{x}{2} \quad , \forall x \in [0,1], \mbox{with equality iff $x\in \{0,1\}$} $$ Hence $$ \sum_{i=1}^n \frac{y_i^*}{1+y_i^*} = \sum_{i=1}^n \frac{y_i^*}{2} = k/2 $$ Notice that $y^*$ satisfies the constraints of the new problem and achieves an objective value of $k/2$. So the new problem is feasible, and its optimal objective value is less than or equal to $k/2$.

Now let $x^*$ be an optimal solution to the new problem. It suffices to show $x^*$ is a binary vector. Since the optimal objective value is no more than $k/2$, we have: $$ \sum_{i=1}^n \frac{x_i^*}{1+x_i^*} \leq k/2 $$ On the other hand: $$ k/2 \geq \sum_{i=1}^n \frac{x_i^*}{1+x_i^*} \overset{(a)}{\geq} \sum_{i=1}^n \frac{x_i^*}{2} \overset{(b)}{=} k/2 $$ where (a) holds by Fact 1 and (b) holds because $x^*$ satisfies the constraint $\sum_{i=1}^n x_i^*=k$. It follows that $$ \sum_{i=1}^n\frac{x_i^*}{1+x_i^*} = \sum_{i=1}^n \frac{x_i^*}{2}$$ But for each $i \in \{1, ..., n\}$, we know by Fact 1 that $$\frac{x_i^*}{2} \geq \frac{x_i^*}{1+x_i^*}$$
So equality must hold in each term $i$, that is, $\frac{x_i^*}{2} = \frac{x_i^*}{1+x_i^*}$, which implies $x_i^* \in \{0,1\}$ by Fact 1. $\Box$


The "structured classes" of problems I mentioned above are generalizations of linear fractional problems where denominator terms can be grouped over separate variables, such as \begin{align} \mbox{Minimize:} \quad & \sum_{i=1}^G \frac{g_i(x)}{T_i(x)} \\ \mbox{Subject to:} \quad & \sum_{i=1}^G \frac{h_{i,k}(x)}{T_i(x)} \leq c_k, \quad \forall k \in \{1, ..., K\} \\ \end{align} where $G$ is the number of groups, and where for each group $i \in \{1, ..,G\}$, the functions $g_i(x)$ and $T_i(x)$, $h_{i,k}(x)$ are functions of a disjoint set of components of the $x$ vector. For example, group 1 uses only components $x_1, x_2$. Group 2 uses components $x_3, x_4$, and so on. I've done some work in more complicated stochastic scenarios that use this structure, for example Theorem 1 here (which is unfortunately written for a more complicated system, a simplified version could be written for this problem):

http://ee.usc.edu/stochastic-nets/docs/asynch-markov-v8.pdf

$\endgroup$
  • $\begingroup$ Observation: I realize now that you want the denominator to be linear and not affine. One way to do reuse my argment but formally put it in your form is to introduce new variables $y_i$ and then the objective function is $\sum_{i=1}^n \frac{x_i}{y_i+x_i}$, but then add "linear" constraints $y_i=1$ for all $i$. $\endgroup$ – Michael Feb 16 '18 at 18:47
  • $\begingroup$ Observation 2: Lipschitz continuity arguments could potentially be used to show that even $\epsilon$-approximate solutions to the new (non-integer) problem could be used to solve the integer problem, provided $\epsilon$ is sufficiently small. $\endgroup$ – Michael Feb 16 '18 at 19:05
  • $\begingroup$ That is a cute transformation (the ${x \over 1+x}$), is this a standard trick with ILPs? $\endgroup$ – copper.hat Feb 16 '18 at 19:18
  • $\begingroup$ @copper.hat : I don't know, I just made it up. But likely others have done similar things, it just exploits the fact that minimizing concave functions is "hard." $\endgroup$ – Michael Feb 16 '18 at 19:21
  • 1
    $\begingroup$ Yes, there is no (known) way to convexify or efficiently solve. In particular, if we could solve problems of the general type you specify, then, we could also solve known "hard" integer constrained problems. $\endgroup$ – Michael Feb 19 '18 at 18:27

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.