# Linear Programming

In this section we describe how linear programming problems can be solved with VSDP. In particular, two linear programs are considered in detail.

## First example

Consider the linear program in primal standard form

$$\begin{array}{ll} \text{minimize} & 2x_{2} + 3x_{4} + 5x_{5}, \\ \text{subject to} & \begin{pmatrix} -1 & 2 & 0 & 1 & 1 \\ 0 & 0 & -1 & 0 & 2 \end{pmatrix} x = \begin{pmatrix} 2 \\ 3 \end{pmatrix}, \\ & x \in \mathbb{R}^{5}_{+}, \end{array}$$

with its corresponding dual problem

$$\begin{array}{ll} \text{maximize} & 2 y_{1} + 3 y_{2}, \\ \text{subject to} & z = \begin{pmatrix} 0 \\ 2 \\ 0 \\ 3 \\ 5 \end{pmatrix} - \begin{pmatrix} -1 & 0 \\ 2 & 0 \\ 0 & -1 \\ 1 & 0 \\ 1 & 2 \end{pmatrix} y \in \mathbb{R}^{5}_{+}. \end{array}$$

The unique exact optimal solution is given by $x^{*} = (0, 0.25, 0, 0, 1.5)^{T}$, $y^{*} = (1, 2)^{T}$ with $\hat{f_{p}} = \hat{f_{d}} = 8$.

The input data of the problem in VSDP are

To create a VSDP object of the linear program data above, we call the VSDP class constructor and do not suppress the output.

The output seems quite verbose in the beginning, but it contains all relevant information about the possibilities of VSDP, including the commands, that can be run to compute rigorous bounds or certificates for infeasibility. After these computations, the results are displayed as short summary in the same context.

By calling the solve method on the VSDP object obj, we can compute an approximate solution x, y, z, for example by using SDPT3. When calling solve without any arguments, the user is asked to choose one of the supported solvers.

The solver output is often quite verbose. Especially for large problem instances it is recommended to display the solver progress. To suppress solver messages, the following option can be set:

To permanently assign an approximate solver to a VSDP object, use the following option:

By simply typing the VSDP object’s name, the user gets a short summary of the solution state.

On success, one can obtain the approximate x and y solutions.

The approximate solution is close to the optimal solution $x^{*} = (0, 0.25, 0, 0, 1.5)^{T}$, $y^{*} = (1, 2)^{T}$.

With this approximate solution, a rigorous lower bound fL of the primal optimal value $\hat{f_{p}}$ can be computed by calling:

Similarly, a rigorous upper bound fU of the dual optimal value $\hat{f_{d}}$ can be computed by calling:

All this information is available in the summary of the VSDP object and must only be extracted if necessary.

Despite the rigorous lower bound fL, the solution object obj.solutions.rigorous_lower_bound contain more information:

1. Y is a rigorous interval enclosure of a dual feasible near optimal solution and
2. Zl a lower bound of of each cone in $z = c - A^{*} y$. For a linear program this is a lower bound on each component of z.

Since Zl is positive, the dual problem is strictly feasible, and the rigorous interval vector Y contains a dual interior solution. Here only some significant digits of this interval vector are displayed. The upper and lower bounds of the interval Y can be obtained by using the sup and inf routines of INTLAB. For more information about the intval data type see [Rump1999].

The information returned by rigorous_upper_bound() is similar:

1. X is a rigorous interval enclosure of a primal feasible near optimal solution and
2. Xl a lower bound of of each cone in X. Again, for a linear program this is a lower bound on each component of X.

Since Xl is a positive vector, X is contained in the positive orthant and the primal problem is strictly feasible.

Summarizing, we have obtained a primal dual interval solution pair with an accuracy measured by

$$\mu(a, b) = \dfrac{a-b}{\max\{1.0, (|a| + |b|)/2\}},$$

see [Jansson2006].

## Second example with free variables

How a linear program with free variables can be solved with VSDP is demonstrated by the following example with one free variable $x_{3}$:

$$\begin{array}{ll} \text{minimize} & x_{1} + x_{2} - 0.5 x_{3}, \\ \text{subject to} & x_{1} - x_{2} + 2 x_{3} = 0.5, \\ & x_{1} + x_{2} - x_{3} = 1, \\ & x_{1} \geq 0, \\ & x_{2} \geq 0. \end{array}$$

The optimal solution pair of this problem is $x^{*} = (\frac{5}{6}, 0, -\frac{1}{6})^{T}$, $y^{*} = (\frac{1}{6}, \frac{5}{6})^{T}$ with $\hat{f_{p}} = \hat{f_{d}} = \frac{11}{12} \approx 9.166\ldots$.

When entering a problem the order of the variables is important: Firstly free variables, secondly nonnegative variables, thirdly second order cone variables, and last semidefinite variables. This order must be maintained in the matrix A as well as in the primal objective c. In the given example, the free variable is $x_{3}$, the nonnegative variables are $x_{1}$, $x_{2}$. Second order cone variables and semidefinite variables are not present. Therefore, the problem data are

The whole VSDP computation can be done in a few lines of code:

Yielding

Published with GNU Octave 4.4.1