6.9 Solution Analysis

The main purpose of MOSEK is to solve optimization problems and therefore the most fundamental question to be asked is whether the solution reported by MOSEK is a solution to the desired optimization problem.

There can be several reasons why it might be not case. The most prominent reasons are:

  • A wrong problem. The problem inputted to MOSEK is simply not the right problem, i.e. some of the data may have been corrupted or the model has been incorrectly built.
  • Numerical issues. The problem is badly scaled or otherwise badly posed.
  • Other reasons. E.g. not enough memory or an explicit user request to stop.

The first step in verifying that MOSEK reports the expected solution is to inspect the solution summary generated by MOSEK (see Sec. 6.9.1 (The Solution Summary)). The solution summary provides information about

  • the problem and solution statuses,
  • objective value and infeasibility measures for the primal solution, and
  • objective value and infeasibility measures for the dual solution, where applicable.

By inspecting the solution summary it can be verified that MOSEK produces a feasible solution, and, in the continuous case, the optimality can be checked using the dual solution. Furthermore, the problem itself ca be inspected using the problem analyzer discussed in Sec. 13 (Problem Analyzer).

If the summary reports conflicting information (e.g. a solution status that does not match the actual solution), or the cause for terminating the solver before a solution was found cannot be traced back to the reasons stated above, it may be caused by a bug in the solver; in this case, please contact MOSEK support (see Sec. 2 (Contact Information)).

If it has been verified that MOSEK solves the problem correctly but the solution is still not as expected, next step is to verify that the primal solution satisfies all the constraints. Hence, using the original problem it must be determined whether the solution satisfies all the required constraints in the model. For instance assume that the problem has the constraints

\[\begin{split}\begin{array}{rcl} x_1 + 2 x_2 + x_3 & \leq & 1, \\ x_1, x_2, x_3 \geq 0 & & \end{array}\end{split}\]

and MOSEK reports the optimal solution

\[x_1=x_2=x_3=1.\]

Then clearly the solution violates the constraints. The most likely explanation is that the model does not match the problem entered into MOSEK, for instance

\[x_1 - 2 x_2 + x_3 \leq 1\]

may have been inputted instead of

\[x_1 + 2 x_2 + x_3 \leq 1.\]

A good way to debug such an issue is to dump the problem to OPF file and check whether the violated constraint has been specified correctly.

Verifying that a feasible solution is optimal can be harder. However, for continuous problems, i.e. problems without any integer constraints, optimality can verified using a dual solution. Normally, MOSEK will report a dual solution; if that is feasible and has the same objective value as the primal solution, then the primal solution must be optimal.

An alternative method is to find another primal solution that has better objective value than the one reported to MOSEK. If that is possible then either the problem is badly posed or there is bug in MOSEK.

6.9.1 The Solution Summary

Due to MOSEK employs finite precision floating point numbers then reported solution is an approximate optimal solution. Therefore after solving an optimization problem it is relevant to investigate how good an approximation the solution is. For a convex optimization problem that is an easy task because the optimality conditions are:

  • The primal solution must satisfy all the primal constraints.
  • The dual solution much satisfy all the dual constraints.
  • The primal and dual objective values must be identical.

Therefore, the MOSEK solution summary displays that information that makes it possible to verify the optimality conditions. Indeed the solution summary reports how much primal and dual solutions violate the primal and constraints respectively. In addition the objective values assoctaied with each solution repoted.

In case of a linear optimization problem the solution summary may look like

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -4.6475314286e+002  nrm: 5e+002   Viol.  con: 1e-014   var: 1e-014
  Dual.    obj: -4.6475314543e+002  nrm: 1e+001   Viol.  con: 4e-009   var: 4e-016

The interpreation of the solution summary is as follows:

  • Information for the basic solution is reported.
  • The problem status is primal and dual feasible which means the problem has an optimal solution.
  • The solution status is optimal.
  • Next information about the primal solution is reported. The information consists of the objective value, the infinity norm of the primal solution and violation meassures. The violation for the constraints (con:) is the maximal violation in any of the constraints. Whereas the violations for the variables (var:) is the maximal bound violation for any of the variables. In this case the primal violations for the constraints and variables are small meaning the solution is an almost feasible solution. Observe due to the rounding errors it can be expected that the violations are proportional to the size (nrm:) of the solution.
  • Similarly for the dual solution the violations are small and hence the dual solution is almost feasible.
  • Finally, it can be seen that the primal and dual objective values are almost identical.

To summarize in this case a primal and a dual solution only violate the primal and dual constraints slightly. Moreover, the primal and dual objective values are almost identical and hence it can be concluded that the reported solution is a good approximation to the optimal solution.

The reason the size (=norms) of the solution are shown is that it shows some about conditioning of the problem because if the primal and/or dual solution has very large norm then the violations and objective values are sensitive to small pertubations in the problem data. Therefore, the problem is unstable and care should be taken before using the solution.

Now what happens if the problem does not have an optimal solution e.g. is primal infeasible. In such a case the solution summary may look like

Interior-point solution summary
  Problem status  : PRIMAL_INFEASIBLE
  Solution status : PRIMAL_INFEASIBLE_CER
  Dual.    obj: 6.7319732555e+000   nrm: 8e+000   Viol.  con: 3e-010   var: 2e-009

i.e. MOSEK reports that the solution is a certificate of primal infeasibility but a certificate of primal infeasibility what does that mean? It means that the dual solution is a Farkas type certificate. Recall Farkas’ Lemma says

\[\begin{split}\begin{array}{ccc} Ax & = & b, \\ x & \geq & 0 \end{array}\end{split}\]

if and only if a \(y\) exists such that

(1)\[\begin{split}\begin{array}{ccc} A^T y & \leq & 0, \\ b^T y & > & 0. \end{array}\end{split}\]

Observe the infeasibility certificate has the same form as a regular dual solution and therefore the certificate is stored as a dual solution. In order to check quality of the primal infeasibility certificate it should be checked whether satisfies (1). Hence, the dual objective value is \(b^T y\) should be strictly positive and the maximal violation in \(A^T y \leq 0\) should be a small. In this case we conclude the certificate is of high quality because the dual objective is postive and large compared to the violations. Note the Farkas certificate is a ray so any postive multiple of that ray is also certificate. This implies the absolute of the value objective value and the violation is not relevant.

In the case a problem is dual infeasible then the solution summary may look like

Basic solution summary
Problem status  : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal.  obj: -2.0000000000e-002  nrm: 1e+000   Viol.  con: 0e+000   var: 0e+000

Observe when a solution is a certificate of dual infeasibility then the primal solution contains the certificate. Moreoever, given the problem is a minimization problem the objective value should be negative and large compared to the worst violation if the certificate is strong.

Listing 17 shows how to use these function to determine the quality of the solution.

Listing 17 An example of solution quality analysis. Click here to download.
function solutionquality(data)

    cmd      = sprintf('read(%s)',data)
    % Read the problem from file
    [r, res] = mosekopt(cmd)

    % Perform the optimization.
    [r, res] = mosekopt('minimize', res.prob); 

    solsta = strcat('MSK_SOL_STA_', res.sol.itr.solsta);
    
    if strcmp(solsta, 'MSK_SOL_STA_OPTIMAL') || strcmp(solsta, 'MSK_SOL_STA_NEAR_OPTIMAL')

      sol = res.sol.itr
      primalobj= sol.pobjval
      dualobj= sol.dobjval
      
      abs_obj_gap     = abs(dualobj - primalobj);
      rel_obj_gap     = abs_obj_gap/(1.0 + min( abs(primalobj), abs(dualobj)));

      
      % Assume the application needs the solution to be within
      % 1e-6 optimality in an absolute sense. Another approach
      % would be looking at the relative objective gap */
      
      fprintf('\n\n');
      fprintf('Customized solution information.\n');
      fprintf('  Absolute objective gap: %e\n',abs_obj_gap);
      fprintf('  Relative objective gap: %e\n',rel_obj_gap);
          
      accepted = 1;
      
      if ( rel_obj_gap>1e-6 )
          fprintf('Warning: The relative objective gap is LARGE.\n');
          accepted = 0;
      end            
        
      if ( accepted )
          res.sol.itr.xx
      else
          % Print detailed information about the solution 
          r = MSK_analyzesolution(task,MSK_STREAM_LOG,whichsol);
      end
   
    elseif strcmp(solsta, 'MSK_SOL_STA_DUAL_INFEAS_CER') || ...
          strcmp(solsta, 'MSK_SOL_STA_PRIM_INFEAS_CER') || ...
          strcmp(solsta, 'MSK_SOL_STA_NEAR_DUAL_INFEAS_CER') || ...
          strcmp(solsta, 'MSK_SOL_STA_NEAR_PRIM_INFEAS_CER')  
        fprintf('Primal or dual infeasibility certificate found.\n');
   
    elseif strcmp(solsta,  'MSK_SOL_STA_UNKNOWN')
        fprintf('The status of the solution is unknown.\n');

    else
        fprintf('Other solution status');
    end

end

6.9.2 The Solution Summary for Mixed-Integer Problems

The solution summary for a mixed-integer problem may look like

Listing 18 Example of solution summary for a mixed-integer problem.
Integer solution solution summary
Problem status  : PRIMAL_FEASIBLE
Solution status : INTEGER_OPTIMAL
Primal.  obj: 3.4016000000e+005   nrm: 1e+000   Viol.  con: 0e+000   var: 0e+000   itg: 3e-014

The main diffrence compared to thecontinous case covered previously is that no information about the dual solution is provided. Simply because there is no dual solution available for a mixed integer problem. In this case it can be seen that the solution is highly feasible because the violations are small. Moreoever, the solution is denoted integer optimal. Observe itg: 3e-014 implies that all the integer constrained variables are at most \(3e-014\) from being an exact integer.