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 Section 6.9.1). 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 Section 13.
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 Section 2).
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
and MOSEK reports the optimal solution
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
may have been inputted instead of
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
if and only if a \(y\) exists such that
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 6.15 shows how to use these function to determine the quality of the solution.
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
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.