8.2 Exponential Optimization

8.2.1 Problem Definition

An exponential optimization problem has the form

(1)\[\begin{split}\begin{array} {lccll} \mbox{minimize} & \sum_{k \in J_0} { c_k e^{\left\lbrace \sum_{j=0}^{n-1} a_{k,j}x_j \right\rbrace } } & & & \\ \mbox{subject to} & \sum_{k \in J_i} { c_k e^{\left\lbrace \sum_{j=0}^{n-1} a_{k,j}x_j \right\rbrace } } & \leq & 1, & i=1,\ldots ,m, \\ & x \in \real^n & & & \end{array}\end{split}\]

where it is assumed that

\[\bigcup_{i=0}^m J_k = \{1,\ldots ,T\}\]

and

\[J_i \cap J_j = \emptyset\]

if \(i \neq j\).

Given

\[c_i >0, \quad i=1,\ldots ,T\]

the problem (1) is a convex optimization problem which can be solved using MOSEK. We will call

\[c_t e^{ \left\lbrace \sum_{j=0}^{n-1} a_{t,j} x_j \right\rbrace } = e^{\left\lbrace \log (c_t) + \sum_{j=0}^{n-1} a_{t,j}x_j \right\rbrace }\]

a single term and hence the number of terms is \(T\).

As stated the problem (1) is a nonseparable problem. However, using

\[v_t = \log (c_t) + \sum_{j=0}^{n-1} a_{tj} x_j\]

we obtain the separable problem

(2)\[\begin{split}\begin{array} {lccll} \mbox{minimize} & \sum_{t \in J_0} e^{v_t} & & & \\ \mbox{subject to} & \sum_{t \in J_i} e^{v_t} & \leq & 1, & i=1,\ldots ,m, \\ & \sum_{j=0}^{n-1} a_{t,j} x_j - v_t & = & -\log (c_t), & t=0,\ldots ,T. \end{array}\end{split}\]

A warning about this approach is that computing the function

\[e^x\]

using double-precision floating point numbers is only possible for \(x\) of small absolute value. It is also possible to reformulate the exponential optimization problem (1) as a dual geometric geometric optimization problem, see Section 8.3. This is often the preferred solution approach because it is computationally more efficient and the numerical problems associated with evaluating \(e^x\) for moderately large \(x\) values are avoided.

Moreover, exponential optimization problems may in some cases have an optimal solution involving infinite values. Consider the simple example

\[\begin{split}\begin{array} {rl} \minimize & e^x \\ \st & x\in \real, \end{array}\end{split}\]

which has the optimal objective value 0 at \(x=-\infty\). Similar problems can occur in constraints. Such a solution can not in general be obtained by numerical methods, which means that MOSEK will act unpredictably in these situations — possibly failing to find a meaningful solution or simply stalling.

8.2.2 The Command Line tool

In the following we will discuss the program mskexpopt, which is included in the MOSEK distribution together with its source code. Hence, you can solve exponential optimization problems using the operating system command line or directly from your own C program. The interface enables:

  • Reading and writing a data file with an exponential optimization problem.
  • Verifying that the input data is reasonable.
  • Solving the problem in primal or dual form.
  • Writing a solution file.

8.2.2.1 The Input Format

The program can read a description of an exponential problem from a file in the following format:

\[\begin{split}\begin{array}{lll} \mathtt{*This is a comment} & & \\ \mathtt{numcon} & & \\ \mathtt{numvar} & & \\ \mathtt{numter} & & \\ c_{\mathtt{1}} & & \\ c_{\mathtt{2}} & & \\ \vdots & & \\ c_{\mathtt{numter}} & & \\ i_{\mathtt{1}} & & \\ i_{\mathtt{2}} & & \\ \vdots & & \\ i_{\mathtt{numter}} & & \\ t_{\mathtt{1}} & j_{\mathtt{1}} & a_{\mathtt{t_1,j_1}} \\ t_{\mathtt{2}} & j_{\mathtt{}}2 & a_{\mathtt{t_2,j_2}}\\ \vdots & \vdots & \vdots \end{array}\end{split}\]

The first line is an optional comment line. In general everything occurring after a * is considered a comment. Lines 2 to 4 inclusive define the number of constraints (\(m\)), the number of variables (\(n\)), and the number of terms \(T\) in the problem. Then follows three sections containing the problem data.

The first section

\[\begin{split}\begin{array}{ll} c_\mathtt{1} & \\ c_\mathtt{2} & \\ \vdots & \\ c_{\mathtt{numter}} & \end{array}\end{split}\]

lists the coefficients \(c_t\) of each term \(t\) in their natural order.

The second section

\[\begin{split}\begin{array}{l} i_\mathtt{1} \\ i_\mathtt{2} \\ \vdots \\ i_{\mathtt{numter}} \end{array}\end{split}\]

specifies to which constraint each term belongs. Hence, for instance \(i_2=5\) means that the term number 2 belongs to constraint 5. \(i_t = 0\) means that term number \(t\) belongs to the objective.

The third section

\[\begin{split}\mathtt{ \begin{array}{lll} t_1 & j_1 & a_{t_1,j_1} \\ t_2 & j_2 & a_{t_2,j_2} \\ \vdots & \vdots & \vdots \end{array}}\end{split}\]

defines the non-zero \(a_{t,j}\) values. For instance the entry

\[\begin{array} {lll} 1 & 3 & 3.3 \end{array}\]

implies that \(a_{t,j}=3.3\) for \(t=1\) and \(j=3\).

Please note that each \(a_{t,j}\) should be specified only once.

8.2.2.2 Choosing Primal or Dual Form

One can choose to solve the exponential optimization problem directly in the primal form (2) or in the dual form. By default mskexpopt solves a problem in the dual form since usually this is more efficient. The command line option

-primal

chooses the primal form.

8.2.2.3 An Example

Consider the problem:

(3)\[\begin{split}\begin{array}{lccr} \mbox{minimize} & 40 e^{-x_1 - \half x_2 - x_3} + 20 e^{x_1 + x_3} + 40 e^{x_1+x_2+x_3} & & \\ \mbox{subject to} & \frac{1}{3} e^{-2 x_1 -2 x_2} + \frac{4}{3} e^{\half x_2 - x_3} & \leq & 1. \end{array}\end{split}\]

This small problem can be specified using the input format shown in Listing 8.2.

Listing 8.2 Input file to specify problem (3).
* File : expopt1.eo

1   * numcon
3   * numvar
5   * numter

* Coefficients of terms

40           
20
40
0.3333333
1.3333333

* For each term, the index of the 
* constraints to the term belongs

0     
0
0
1
1

* Section defining a_kj

0 0 -1
0 1 -0.5
0 2 -1
1 0 1.0
1 2 1.0
2 0 1.0
2 1 1.0
2 2 1.0
3 0 -2
3 1 -2
4 1 0.5
4 2 -1.0

Now the command mskexpopt expopt1.eo will produce the solution file expopt1.sol shown below.

PROBLEM STATUS      : PRIMAL_AND_DUAL_FEASIBLE
SOLUTION STATUS     : OPTIMAL
PRIMAL OBJECTIVE    : 1.331371e+02

VARIABLES
INDEX   ACTIVITY
1       6.931471e-01
2       -6.931472e-01
3       3.465736e-01

8.2.3 The C interface

The C source code for solving an exponential optimization problem is included in expopt.h and expopt.c. Setting up an exponential problem begins with a call to MSK_expoptsetup, which provides a description of the problem in the form (1). The problem can then be solved using MSK_expoptimize. For details consult the API reference and the source file examples/c/mskexpopt.c.

An example that solves (3) is included below.

#include <string.h>

#include "expopt.h"

void MSKAPI printcb(void* handle, const char str[])
{
  printf("%s",str);
}

  
int main (int argc, char **argv)
{
  int          r = MSK_RES_OK, numcon = 1, numvar = 3 , numter = 5;
  
  int          subi[]   = {0,0,0,1,1};
  int          subk[]   = {0,0,0,1,1,2,2,2,3,3,4,4};
  double       c[]      = {40.0,20.0,40.0,0.333333,1.333333};
  int          subj[]   = {0,1,2,0,2,0,1,2,0,1,1,2};
  double       akj[]    = {-1,-0.5,-1.0,1.0,1.0,1.0,1.0,1.0,-2.0,-2.0,0.5,-1.0};
  int          numanz   = 12;
  double       objval;
  double       xx[3];
  double       y[5];
  MSKenv_t     env;
  MSKprostae   prosta;
  MSKsolstae   solsta;
  MSKtask_t    expopttask;
  expopthand_t expopthnd = NULL;
  /* Pointer to data structure that holds nonlinear information */
  
  if (r == MSK_RES_OK)
    r = MSK_makeenv (&env,NULL); 
        
  if (r == MSK_RES_OK)
    MSK_makeemptytask(env,&expopttask);
  
  if (r == MSK_RES_OK)
    r = MSK_linkfunctotaskstream(expopttask,MSK_STREAM_LOG,NULL,printcb);

  if (r == MSK_RES_OK)
  {
    /* Initialize expopttask with problem data */    
    r =  MSK_expoptsetup(expopttask,
                         1, /* Solve the dual formulation */      
                         numcon,
                         numvar,
                         numter,
                         subi,
                         c,
                         subk,
                         subj,
                         akj,
                         numanz,
                         &expopthnd
                         /* Pointer to data structure holding nonlinear data */
                         );
  }

  /* Any parameter can now be changed with standard mosek function calls */ 
  if (r == MSK_RES_OK)
    r = MSK_putintparam(expopttask,MSK_IPAR_INTPNT_MAX_ITERATIONS,200); 

  /* Optimize, xx holds the primal optimal solution,
   y holds solution to the dual problem if the dual formulation is used
  */
  
  if (r == MSK_RES_OK)
    r = MSK_expoptimize(expopttask,
                        &prosta,
                        &solsta,
                        &objval,
                        xx,
                        y,
                        &expopthnd);
    
  /* Free data allocated by expoptsetup */
  if (expopthnd)
    MSK_expoptfree(expopttask,
                   &expopthnd);
  
  MSK_deletetask(&expopttask);
  MSK_deleteenv(&env);
  
}