# 11.1 Linear Optimization¶

A linear optimization problem can be written as

where

- \(m\) is the number of constraints.
- \(n\) is the number of decision variables.
- \(x \in \real^n\) is a vector of decision variables.
- \(c \in \real^n\) is the linear part of the objective function.
- \(A \in \real^{m \times n}\) is the constraint matrix.
- \(l^c \in \real^m\) is the lower limit on the activity for the constraints.
- \(u^c \in \real^m\) is the upper limit on the activity for the constraints.
- \(l^x \in \real^n\) is the lower limit on the activity for the variables.
- \(u^x \in \real^n\) is the upper limit on the activity for the variables.

A primal solution \((x)\) is *(primal) feasible* if it satisfies all constraints in (1). If (1) has at least one primal feasible solution, then (1) is said to be (primal) feasible.

In case (1) does not have a feasible solution, the problem is said to be *(primal) infeasible*

## 11.1.1 Duality for Linear Optimization¶

Corresponding to the primal problem (1), there is a dual problem

If a bound in the primal problem is plus or minus infinity, the corresponding dual variable is fixed at 0, and we use the convention that the product of the bound value and the corresponding dual variable is 0. E.g.

This is equivalent to removing variable \((s_l^x)_j\) from the dual problem. A solution

to the dual problem is feasible if it satisfies all the constraints in (2). If (2) has at least one feasible solution, then (2) is *(dual) feasible*, otherwise the problem is *(dual) infeasible*.

### A Primal-dual Feasible Solution¶

A solution

is denoted a *primal-dual feasible solution*, if \((x)\) is a solution to the primal problem (1) and \((y,s_l^c,s_u^c,s_l^x,s_u^x)\) is a solution to the corresponding dual problem (2).

### The Duality Gap¶

Let

be a primal-dual feasible solution, and let

For a primal-dual feasible solution we define the *duality gap* as the difference between the primal and the dual objective value,

where the first relation can be obtained by transposing and multiplying the dual constraints (2) by \(x^*\) and \((x^c)^*\) respectively, and the second relation comes from the fact that each term in each sum is nonnegative. It follows that the primal objective will always be greater than or equal to the dual objective.

### An Optimal Solution¶

It is well-known that a linear optimization problem has an optimal solution if and only if there exist feasible primal and dual solutions so that the duality gap is zero, or, equivalently, that the *complementarity conditions*

are satisfied.

If (1) has an optimal solution and **MOSEK** solves the problem successfully, both the primal and dual solution are reported, including a status indicating the exact state of the solution.

## 11.1.2 Infeasibility for Linear Optimization¶

### Primal Infeasible Problems¶

If the problem (1) is infeasible (has no feasible solution), **MOSEK** will report a certificate of primal infeasibility: The dual solution reported is the certificate of infeasibility, and the primal solution is undefined.

A certificate of primal infeasibility is a feasible solution to the modified dual problem

such that the objective value is strictly positive, i.e. a solution

to (4) so that

Such a solution implies that (4) is unbounded, and that its dual is infeasible. As the constraints to the dual of (4) are identical to the constraints of problem (1), we thus have that problem (1) is also infeasible.

### Dual Infeasible Problems¶

If the problem (2) is infeasible (has no feasible solution), **MOSEK** will report a certificate of dual infeasibility: The primal solution reported is the certificate of infeasibility, and the dual solution is undefined.

A certificate of dual infeasibility is a feasible solution to the modified primal problem

where

and

such that

Such a solution implies that (5) is unbounded, and that its dual is infeasible. As the constraints to the dual of (5) are identical to the constraints of problem (2), we thus have that problem (2) is also infeasible.

### Primal and Dual Infeasible Case¶

In case that both the primal problem (1) and the dual problem (2) are infeasible, **MOSEK** will report only one of the two possible certificates — which one is not defined (**MOSEK** returns the first certificate found).

### Minimalization vs. Maximalization¶

When the objective sense of problem (1) is maximization, i.e.

the objective sense of the dual problem changes to minimization, and the domain of all dual variables changes sign in comparison to (2). The dual problem thus takes the form

This means that the duality gap, defined in (3) as the primal minus the dual objective value, becomes nonpositive. It follows that the dual objective will always be greater than or equal to the primal objective. The primal infeasibility certificate will be reported by **MOSEK** as a solution to the system

such that the objective value is strictly negative

Similarly, the certificate of dual infeasibility is an \(x\) satisfying the requirements of (5) such that \(c^Tx>0\).