Convexifying Optimization Problem

108 Views Asked by At

Let $\mathbf{V} \in \mathbb{R}_{+}^{n \times m}$ and $\mathbf{E} \in \mathbb{R}_{+}^{n \times m}$.

I am trying to convexify the following program which solves for $\mathbf{X} \in \mathbb{R}^{n \times m}$:

\begin{align} &\max &\sum_{i = 1}^n \log \left(\sum_{j = 1}^n V_{ij}\left( X_{ij} - E_{ij} \right)\right) - \sum_{i = 1}^n \log\left(\sum_{j = 1}^m X_{ij} - E_{ij}\right)\\ &\forall j \in \{1, \dots, m\} & \sum_{i = 1}^n X_{ij} \leq 1\\ &\forall i \in \{1, \dots, n\}, j \in \{1, \dots, m\} & X_{ij} \geq 0 \end{align}

I tried putting $\sum_{i = 1}^n \log(\sum_{j = 1}^m X_{ij} - E_{ij})$ as a constraint using a dummy variable but I do not think I am doing it correctly since my solver tells me that the program is not convex.

How can I convexify this problem?

1

There are 1 best solutions below

3
On BEST ANSWER

This can be convexified by Difference of Convex (DC) Programming.

See DC Programming: The Optimization Method You Never Knew You Had To Know.

Variations and extension of the convex–concave procedure, Thomas Lipp1 and Stephen Boyd

A modeling system such as CVXPY which supports Disciplined Convex-Concave Programming (DCCP) makes it easy to enter this problem, and let the modeling syetm do the dirty work for you, while reducing human error propensity.