8.3 Dual Geometric Optimization

Dual geometric is a special class of nonlinear optimization problems involving a nonlinear and non-separable objective function. In this section we will show how to solve dual geometric optimization problems using MOSEK. For a thorough discussion of geometric optimization see [BSS93].

8.3.1 Problem Definition

Consider the dual geometric optimization problem

\[\begin{split}\begin{array} {lccl} \mbox{maximize} & f(x) & & \\ \mbox{subject to} & Ax & = & b ,\\ & x\geq 0, & & \end{array}\end{split}\]

where \(A \in \real^{m\times n}\) and all other quantities have conforming dimensions. Let \(t\) be an integer and \(p\) be a vector of \(t+1\) integers satisfying the conditions

\[\begin{split}\begin{array}{rcll} p_{0} & = & 0, &\\ p_{i} & < & p_{i+1}, & i=1,\ldots ,t, \\ p_{t} & = & n. & \end{array}\end{split}\]

Then \(f\) can be of the form

\[f(x) = \sum_{j=0}^{n-1} x_j \ln \left( \frac{v_j}{x_j} \right) + \sum_{i=1}^t \left( \sum_{j=p_i}^{p_{i+1}-1} x_j \right) \ln \left( \sum_{j=p_i}^{p_{i+1}-1} x_j \right)\]

where \(v \in \real^n_+\). Given these assumptions, it can be proven that \(f\) is a concave function and therefore the dual geometric optimization problem can be solved using MOSEK. We will introduce the following definitions:

\[\begin{split}x^{i} := \left[ \begin{array}{c} x_{p_i} \\ x_{p_i+1} \\ \vdots \\ x_{p_{i+1}-1} \end{array} \right], X^i := \mbox{diag}(x^i), \mbox{ and } e^i := \left[ \begin{array} {c} 1 \\ \vdots \\ 1 \end{array} \right] \in \real^{p_{i+1}-p_i}.\end{split}\]

which make it possible to state \(f\) on the form

\[f(x) = \sum_{j=0}^{n-1} x_j \ln \left( \frac{v_j}{x_j} \right) + \sum_{i=1}^t \left( (e^i)^T x^i \right) \ln \left( (e^i)^T x^i \right).\]

Furthermore, we have that

\[\begin{split}\nabla f(x) = \left[ \begin{array} {c} \ln (v_0) - 1 - \ln (x_0) \\ \vdots \\ \ln (v_j) - 1 - \ln (x_j) \\ \vdots \\ \ln (v_{n-1}) - 1 - \ln (x_{n-1}) \end{array} \right] + \left[ \begin{array} {c} 0 e^{0} \\ (1 + \ln ((e^1)^T x^1)) e^1 \\ \vdots \\ (1 + \ln ((e^i)^T x^i)) e^i \\ \vdots \\ (1+ \ln ((e^t)^T x^t)) e^t \end{array} \right]\end{split}\]

and

\[\begin{split}\begin{array}{c} \nabla^2 f(x) = \left[ \begin{array} {ccccc} - (X^0)^{-1} & 0 & 0 & \cdots & 0 \\ 0 & \frac{e^1 (e^1)^T}{(e^1)^T x^1}- (X^1)^{-1} & 0 & \cdots & 0 \\ 0 & 0 & \ddots & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \frac{e^t (e^t)^T}{(e^t)^T x^t} - (X^t)^{-1} \end{array} \right]. \end{array}\end{split}\]

Please note that the Hessian is a block diagonal matrix and, especially if \(t\) is large, it is very sparse — MOSEK will automatically exploit these features to speed up computations. Moreover, the Hessian can be computed cheaply, specifically in

\[O \left( \sum_{i=0}^t (p_{i+1} - p_i)^2 \right)\]

operations.

8.3.2 dgopt: A Program for Dual Geometric Optimization

8.3.2.1 Input format

A dual geometric optimization problem input consists of two files. Since the constraints of the optimization problem are linear, they can be specified using an MPS file as in the purely linear case. The objective \(f\) is defined in a separate file as a list of the following values:

\[\begin{split}\begin{array} {c} t \\ v_0\\ v_1 \\ \vdots \\ v_{n-1} \\ p_1 - p_0\\ p_2 - p_1 \\ \vdots \\ p_t - p_{t-1} \end{array}\end{split}\]

For example, the function \(f\) given by

\[\begin{split}\begin{array}{ll} f(x) = & x_0\ln\left(\frac{40}{x_0}\right) + x_1\ln\left(\frac{20}{x_1}\right) + x_2\ln\left(\frac{40}{x_2}\right) + x_3\ln\left(\frac{1}{3x_3}\right) + x_4\ln\left(\frac{4}{3x_4}\right) \\ & + (x_3+x_4) \ln (x_3+x_4) \end{array}\end{split}\]

would be represented as:

Listing 8.3 File containing the specification for the non-linear part. Click here to download.
2
40.0
20.0
40.0
0.33333333333333
1.33333333333333
3
2

The example is solved by executing the command line

mskdgopt examp/data/dgo.mps examples/data/dgo.f

8.3.2.2 The C interface

The source code for the dual geometric optimizer consists of the files dgopt.h and dgopt.c. To define an optimization problem the user should set up an ordinary task containing the linear part of the data and call MSK_dgosetup to append the nonlinear objective data. After that the standard method MSK_optimize solves the problem. See the file mskdgopt.c provided in examples/c for more information and the API reference for details.