This chapter provides information about additional problem classes and functionality provided in the C API.
In this section we will discuss solution of nonlinear separable convex optimization problems using MOSEK. We allow both nonlinear constraints and objective, but restrict ourselves to separable functions.
A general separable nonlinear optimization problem can be specified as follows:
![]() |
(6.1.1) |
where
This implies that the ith constraint essentially has the form
![]() |
The problem (6.1.1) must satisfy the three important requirements:
Separability: This requirement implies that all nonlinear functions can be written on the form
![]() |
and
![]() |
where
![]() |
Hence, the nonlinear functions can be written as a sum of functions which depends only one variable.
Differentiability: All functions should be twice differentiable for all satisfying
![]() |
if occurs in at least one nonlinear function.
Subsequently, we will use the following example to demonstrate the solution of a separable convex optimization problem using MOSEK:
![]() |
(6.1.2) |
First note that the problem (6.1.2) is not a separable optimization problem because the logarithmic term in the objective is not a function of a single variable. However, by introducing a constraint and a variable the problem can be made separable as follows
![]() |
(6.1.3) |
This problem is obviously separable and equivalent to the previous problem. Moreover, note that all nonlinear functions are well defined for x values satisfying the variable bounds strictly, i.e.
![]() |
This assures sure that function evaluation errors will not occur during the optimization process because MOSEK will only evaluate for
.
Frequently the method employed above can be used to make convex optimization problems separable even if these are not formulated as such initially. The reader might object that this approach is inefficient because additional constraints and variables are introduced to make the problem separable. However, in our experience this drawback is offset largely by the much simpler structure of the nonlinear functions. Particularly, the evaluation of the nonlinear functions, their gradients and Hessians is much easier in the separable case.
scopt is an easy-to-use interface to MOSEKs nonlinear capabilities for solving separable convex problems. As currently implemented scopt is not capable of handling arbitrary nonlinear expressions. In fact scopt can handle only the nonlinear expressions ,
,
, and
. However, in a subsequent section we will demonstrate that it is easy to expand the number of nonlinear expressions that scopt can handle.
All the linear data of the problem, such as c and A, is inputted to MOSEK as usual, i.e. using the relevant functions in the MOSEK API.
The nonlinear part of the problem is specified using some arrays which indicate the type of the nonlinear expressions and where these should be added.
For example given the three int arrays — oprc, opric, and oprjc — and the two double arrays — oprfc and oprgc — the nonlinear expressions in the constraints can be coded in those arrays using the following table:
oprc[k] | opric[k] | oprjc[k] | oprfc[k] | oprgc[k] | oprhc[k] | Expression added |
to constraint i | ||||||
0 | i | j | f | g | h | ![]() |
1 | i | j | f | g | h | ![]() |
2 | i | j | f | g | h | ![]() |
3 | i | j | f | g | h | ![]() |
Hence, oprc[k] specifies the nonlinear expression type, opric[k] indicates to which constraint the nonlinear expression should be added. oprfc[k] and oprgc[k] are parameters used when the nonlinear expression is evaluated. This implies that nonlinear expressions can be added to an arbitrary constraint and hence you can create multiple nonlinear constraints.
Using the same method all the nonlinear terms in the objective can be specified using opro[k], oprjo[k], oprfo[k] and oprho[k] as shown below:
opro[k] | oprjo[k] | oprfo[k] | oprgo[k] | oprho[k] | Expression added |
in objective | |||||
0 | j | f | g | h | ![]() |
1 | j | f | g | h | ![]() |
2 | j | f | g | h | ![]() |
3 | j | f | g | h | ![]() |
Suppose we want to add the nonlinear expression to the objective. This is an expression on the form
where f=-1, g=1, h=0 and j=3. This can be represented by:
opro[0] = 2 oprjo[0] = 3 oprfo[0] = -1.0 oprgo[0] = 1.0 oprho[0] = 0.0
The source code for scopt consists of the files:
These three files are all available in the directory
mosek\6\tools\examples\c
We will not discuss the implementation of scopt in details but rather refer the reader to the source code found in scopt.c which is included in the distribution. However, the driver program tstscopt.c which solves the example (6.1.2).
scopt handles only a limited number of nonlinear expression types. However, it is easy to add a new operator such as the square root operator. First step is to define the new operator in the file scopt.h that after modification contains the lines
#define MSK_OPR_ENT 0 #define MSK_OPR_EXP 1 #define MSK_OPR_LOG 2 #define MSK_OPR_POW 3 #define MSK_OPR_SQRT 4 /* constant for square root operator */
Next the function evalopr in the file scopt.c should be modified. The purpose of evalopr is to compute the function value, the gradient (first derivative), and the Hessian (second derivative) for a nonlinear expression. The modified function has the form:
An exponential optimization problem has the form
![]() |
(6.2.1) |
where it is assumed that
![]() |
and
![]() |
if .
Given
![]() |
the problem (6.2.1) is a convex optimization problem which can be solved using MOSEK. We will call
![]() |
for a term and hence the number of terms is T.
As stated the problem (6.2.1) is a nonseparable problem. However, using
![]() |
we obtain the separable problem
![]() |
(6.2.2) |
which could be solved using the scopt interface discussed in Section 6.1. A warning about this approach is that computing the function
![]() |
using double-precision floating point numbers is only possible for small values of x in absolute value. Indeed grows very rapidly for larger x values, and numerical problems may arise when solving the problem on this form.
It is also possible to reformulate the exponential optimization problem (6.2.1) as a dual geometric geometric optimization problem (6.4.1). This is often the preferred solution approach because it is computationally more efficient and the numerical problems associated with evaluating for moderately large x values are avoided.
The MOSEK distribution includes the source code for a program that enables you to:
In the following we will discuss the program mskexpopt, which is included in the MOSEK distribution, in both source code and compiled form. Hence, you can solve exponential optimization problems using the operating system command line or directly from your own C program.
First we will define a text input format for specifying an exponential optimization problem. This is as follows:
![]() |
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
![]() |
lists the coefficients of each term t in their natural order.
The second section
![]() |
specifies to which constraint each term belongs. Hence, for instance means that the term number 2 belongs to constraint 5.
means that term number t belongs to the objective.
The third section
![]() |
defines the non-zero values. For instance the entry
![]() |
implies that for t=1 and j=3.
Please note that each should be specified only once.
One can choose to solve the exponential optimization problem directly in the primal form (6.2.2) or on the dual form. By default mskexpopt solves a problem on the dual form since usually this is more efficient. The command line option
-primal
chooses the primal form.
Consider the problem:
![]() |
(6.2.3) |
This small problem can be specified as follows using the input format:
* 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
Using the program mskexpopt included in the MOSEK distribution the example can be solved. Indeed the command line
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
The C source code for solving an exponential optimization problem is included in the MOSEK distribution. The relevant source code consists of the files:
Defines prototypes for the functions:
Reads a problem from a file.
Sets up a problem. The function takes the arguments:
*akj: akj[i] is coefficient of variable subj[i] in term subk[i], i.e.
![]() |
Solves the problem and returns the problem status and the optimal primal solution.
Frees data structures allocated by MSK_expoptsetup.
Implements the functions specified in expopt.h.
A command line interface.
As a demonstration of the interface a C program that solves (6.2.3) is included below.
Exponential optimization problem may in some cases have a final optimal objective value for a solution containing infinite values. Consider the simple example
![]() |
which has the optimal objective value 0 at x=-∞. 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.
MOSEK provides an interface for general convex optimization which is discussed in this section.
Using the general convex optimization interface in MOSEK is complicated. It is recommended to use the conic solver, the quadratic solver or the scopt interface whenever possible. Alternatively GAMS or AMPL with MOSEK as solver are well-suited for general convex optimization problems.
A general nonlinear convex optimization problem is to minimize or maximize an objective function of the form
![]() |
(6.3.1) |
subject to the functional constraints
![]() |
(6.3.2) |
and the bounds
![]() |
(6.3.3) |
Please note that this problem is a generalization of linear and quadratic optimization. This implies that the parameters c, A, , Q, and so forth denote the same as in the case of linear and quadratic optimization. All linear and quadratic terms should be inputted to MOSEK as described for these problem classes. The general convex part of the problems is defined by the functions f(x) and
, which must be general nonlinear, twice differentiable functions.
MOSEK makes two assumptions about the optimization problem.
The first assumption is that all functions are at least twice differentiable on their domain. More precisely, f(x) and g(x) must be at least twice differentiable for all x so that
![]() |
The second assumption is that
![]() |
(6.3.4) |
must be a convex function if the objective is minimized. Otherwise if the objective is maximized it must be a concave function. Moreover,
![]() |
(6.3.5) |
must be a convex function if
![]() |
and a concave function if
![]() |
Note in particular that nonlinear equalities are not allowed.
If these two assumptions are not satisfied, then it cannot be guaranteed that MOSEK produces correct results or works at all.
MOSEK receives information about the general convex terms via two call-back functions implemented by the user:
The call-back functions are passed to MOSEK with the function MSK_putnlfunc.
For an example of using the general convex framework see Section 6.4.
Dual geometric is a special class of nonlinear optimization problems involving a nonlinear and nonseparable objective function. In this section we will show how to solve dual geometric optimization problems using MOSEK.
Consider the dual geometric optimization problem
![]() |
(6.4.1) |
where and all other quantities have conforming dimensions. Let t be an integer and p be a vector of t+1 integers satisfying the conditions
![]() |
Then f can be stated as follows
![]() |
where is a vector positive positive values.
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.
For a thorough discussion of geometric optimization see [18, pp. 531-538].
We will introduce the following definitions:
![]() |
which make it possible to state f on the form
![]() |
Furthermore, we have that
![]() |
and
![]() |
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, specificly in
![]() |
operations.
In the following we will use the data
![]() |
and the function f given by
![]() |
for demonstration purposes.
The generic dual geometric optimization problem and a numerical example have been presented and we will now develop a program which can solve the dual geometric optimization problem using the MOSEK API.
The first problem is how to feed the problem data into MOSEK. Since the constraints of the optimization problem are linear, they can be specified fully using an MPS file as in the purely linear case. The MPS file for the numerical data above will look as follows:
NAME ROWS N obj E c1 E c2 E c3 E c4 COLUMNS x1 obj 0 x1 c1 -1 x1 c2 -0.5 x1 c3 -1 x1 c4 1 x2 obj 0 x2 c1 1 x2 c3 1 x2 c4 1 x3 obj 0 x3 c1 1 x3 c2 1 x3 c3 1 x3 c4 1 x4 obj 0 x4 c1 -2 x4 c2 -2 x5 obj 0 x5 c2 0.5 x5 c3 -1 RHS rhs c4 1 RANGES BOUNDS ENDATA
Moreover, a file specifying f is required so for that purpose we define a file:
![]() |
Hence, for the numerical example this file has the format:
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
The source code for the dgopt consists of the files:
These files are available in the MOSEK distribution in the directory:
mosek/6/tools/examples/c
The basic functionality of dgopt can be gathered by studying the function main in mskdgopt.c. This function first loads the linear part of the problem from an MPS file into the task. Next, the nonlinear part of the problem is read from a file with the function MSK_dgoptread. Finally, the nonlinear function is created and inputted with MSK_dgoptsetup and the problem is solved. The solution is written to the file dgopt.sol.
The following functions in dgopt.c are used to set up the information about the evaluation of the nonlinear objective function:
The purpose of this function is to read data from a file which specifies the nonlinear function f in the objective.
This function creates the problem in the task. The information parsed to the function is stored in a data structure called nlhandt, defined in the program. This structure is later passed to the functions gostruc and goeval which are used to compute the gradient and the Hessian of f.
This function is a call-back function used by MOSEK. The function reports structural information about f such as the number of non-zeros in the Hessian and the sparsity pattern of the Hessian.
This function is a call-back function used by MOSEK. It reports numerical information about f such as the objective value and gradient for a particular x value.
Network flow problems are a special class of linear optimization problems which has many applications. A network consists of a set of points connected by a set of lines. Usually the points and lines are called nodes and arcs. Arcs may have an direction on them. The network is directed if all arcs are directed. The class of network flow problems is defined as follows.
Let be a directed network of nodes
and arcs
. Associated with every arc
is a cost
and a capacity
. Moreover, associated with each node
in the network is a lower limit
and an upper limit
on the demand (supply) of the node. The minimum cost of a network flow problem can be stated as follows:
![]() |
(6.5.1) |
A classical example of a network flow problem is the transportation problem where the objective is to distribute goods from warehouses to customers at lowest possible total cost, see [7] for a detailed application reference.
The above graph formulation of the network flow problem implies the structural properties. Each variable appears in exactly two constraints with a numerical value of either or
.
It is well-known that problems with network flow structure can be solved efficiently with a specialized version of the simplex method. MOSEK includes such a network simplex implementation which can be called either directly using MSK_netoptimize or indirectly by letting the standard simplex optimizer extract the embedded network. This section shows how to solve a network problem by a direct call to MSK_netoptimize. For further details on how to exploit embedded network in the standard simplex optimizer, see Section 8.3.1.
The following is an example of a linear network optimization problem:
![]() |
(6.5.2) |
having the bounds .
The corresponding graph is displayed in fig.6.1.
In this section we will show how to solve (6.5.2) with the network optimizer.
The C program included below, which solves this problem, is distributed with MOSEK and can be found in the directory
mosek\6\tools\examples\c
There are a few important differences between the linear network optimization example in section 6.5.1.1 and the general linear optimization problem in section 5.2.
Often problems contains both large parts with network structure and some non-network constraints or variables — such problems are said to have embedded network structure.
A linear optimization with embedded network structure problem can be written as :
![]() |
(6.6.1) |
Where the constraints
![]() |
(6.6.2) |
defines a network as explained in section 6.5, and the constraints
![]() |
(6.6.3) |
defines the general non-network linear constraints. As an example consider the small linear optimization problem
![]() |
(6.6.4) |
with the bounds
![]() |
Recalling the network flow problem structural properties from section 6.5.1, each variable should appear in exactly two constraints with coefficients of either or
.
At first glance it does not seem to contain any network structure, but if we scale constraints 1-4 by respectively 2.0, 2.0, 4.0, 4.0 and columns 1-2 by -1.0, 0.1 we get the following problem :
![]() |
(6.6.5) |
with the bounds
![]() |
This corresponds to the network flow problem in section 6.5.1 plus one extra non-network constraint. We cannot use the network optimizer directly on the above problem since the last constraint destroys the network property. Finding the largest possible network structure in a linear optimization problem is computationally difficult, so MOSEK offers a heuristic MSK_netextraction that attempts to find suitable scaling factors maximizing numbers of network constraints and variables. Assuming that the embedded network structure is dominant and the problem has few non-network constraints, we can exploit this structure and potentially speed up the optimization. Since the network constraints can be handled efficiently by the specialized network optimizer, the following idea is used:
An embedded network can be exploited by this scheme in two ways:
The first method is more difficult than the second, but also offers much more flexibility. In 6.6.1 the first method is demonstrated by a code example below. For further details on exploiting embedded network structure in the standard simplex optimizer, see section 8.3.1.
MOSEK is distributed with some network examples which can be found in the directory
mosek\6\tools\examples
The example given in this section demonstrates how to extract and optimize embedded network structure in a arbitrary linear optimization problem. The following idea is used
In the above example we only optimize the embedded network problem. We still need to use the found network solution as a hot-start for the simplex optimizer and solve the original problem. This involves unscaling the network solution back to same unit measure as the original problem. In the example
mosek\6\tools\examples\c\network3.c
we show how to convert the network solution into a valid hot-start for the simplex optimizer.
A linear optimization problem always has an optimal solution which is also a basic solution. In an optimal basic solution there are exactly m basic variables where m is the number of rows in the constraint matrix A. Define
![]() |
as a matrix consisting of the columns of A corresponding to the basic variables.
The basis matrix B is always non-singular, i.e.
![]() |
or equivalently that exists. This implies that the linear systems
![]() |
(6.7.1) |
and
![]() |
(6.7.2) |
each has a unique solution for all w.
MOSEK provides functions for solving the linear systems (6.7.1) and (6.7.2) for an arbitrary w.
To use the solutions to (6.7.1) and (6.7.2) it is important to know how the basis matrix B is constructed.
Internally MOSEK employs the linear optimization problem
![]() |
(6.7.3) |
where
![]() |
The basis matrix is constructed of m columns taken from
![]() |
If variable is a basis variable, then the j'th column of A denoted
will appear in B. Similarly, if
is a basis variable, then the i'th column of -I will appear in the basis. The ordering of the basis variables and therefore the ordering of the columns of B is arbitrary. The ordering of the basis variables may be retrieved by calling the function:
MSK_initbasissolve (MSKtask_t task MSKidxt *basis);
This function initializes data structures for later use and returns the indexes of the basic variables in the array basis. The interpretation of the basis is as follows. If
![]() |
then the i'th basis variable is . Moreover, the i'th column in B will be the i'th column of -I. On the other hand if
![]() |
then the i'th basis variable is variable
![]() |
and the i'th column of B is the column
![]() |
For instance if and
, then since
, the first basis variable is
. Therefore, the first column of B is the fourth column of -I. Similarly, if
, then the second variable in the basis is
. Hence, the second column of B is identical to
.
Consider the linear optimization problem:
![]() |
(6.7.4) |
Suppose a call to MSK_initbasissolve returns an array basis so that
basis[0] = 1, basis[1] = 2.
Then the basis variables are and
and the corresponding basis matrix B is
![]() |
(6.7.5) |
Please note the ordering of the columns in B.
The following program demonstrates the use of MSK_solvewithbasis.
In the example above the linear system is solved using the optimal basis for (6.7.4) and the original right-hand side of the problem. Thus the solution to the linear system is the optimal solution to the problem. When running the example program the following output is produced.
basis[0] = 1 Basis variable no 0 is xc1. basis[1] = 2 Basis variable no 1 is x0. Solution to Bx = b: x0 = 2.000000e+00 xc1 = -4.000000e+00 Solution to B^Tx = c: x1 = -1.000000e+00 x0 = 1.000000e+00
Please note that the ordering of the basis variables is
![]() |
and thus the basis is given by:
![]() |
(6.7.6) |
It can be verified that
![]() |
is a solution to
![]() |
MOSEK can be used to solve an arbitrary (rectangular) linear system
![]() |
using the MSK_solvewithbasis function without optimizing the problem as in the previous example. This is done by setting up an A matrix in the task, setting all variables to basic and calling the MSK_solvewithbasis function with the b vector as input. The solution is returned by the function.
Below we demonstrate how to solve the linear system
![]() |
(6.7.7) |
with b=(1,-2) and b=(7,0).
The most important step in the above example is the definition of the basic solution using the MSK_putsolutioni function, where we define the status key for each variable. The actual values of the variables are not important and can be selected arbitrarily, so we set them to zero. All variables corresponding to columns in the linear system we want to solve are set to basic and the slack variables for the constraints, which are all non-basic, are set to their bound.
The program produces the output:
Solution to Bx = b: x1 = 1 x0 = 3 Solution to Bx = b: x1 = 7 x0 = 7
and we can verify that is indeed a solution to (6.7.7).
Some of the API function calls, notably MSK_optimize, may take a long time to complete. Therefore, during the optimization a call-back function is called frequently. From the call-back function it is possible
The following source code example documents how the progress call-back function can be used.
You can customize the warning and error reporting in the C API. The MSK_putresponsefunc function can be used to register a user-defined function to be called every time a warning or an error is encountered by MOSEK. This user-defined function will then handle the error/warning as desired.
The following code shows how to define and register an error handling function:
The output from the code above is:
MOSEK reports error number 1204: The index value 10 occurring in argument 'i' is too large. Return code - 1204
All strings i.e. char * in the C API are assumed to be UTF8 strings. Please note that
For more information about UTF8 encoded strings, please see http://en.wikipedia.org/wiki/UTF-8.
It is possible to convert a wchar_t string to a UTF8 string using the function MSK_wchartoutf8. The inverse function MSK_utf8towchar converts a UTF8 string to a wchar_t string.
The example below documents how to convert a wchar_t string to a UTF8 string.
Please note that the MPS and LP format are based ASCII formats whereas the OPF, MBT, and XML are UTF8 based formats. This implies that problems which contains non-ASCII variable or constraint names cannot be written correctly to an MPS or LP formatted file.