Skip to content

[docs] improve the docstring for DUAL_INFEASIBLE #2701

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Mar 27, 2025
Merged

Conversation

odow
Copy link
Member

@odow odow commented Mar 27, 2025

@WalterMadelim
Copy link

I think the first statement is aggressive. It asserts more information than what it really proves.
The following example you proposed is a nice one to reflect this point.

import JuMP, MosekTools
model = JuMP.Model(MosekTools.Optimizer) # the primal problem
# `model` admits of a `DUAL_INFEASIBLE` dual problem
# The odds are that Mosek reports `DUAL_INFEASIBLE` before reporting `OPTIMAL`
# In this case, the 1st statement is not accurate, because actually a dual bound exists, see the end line
JuMP.@variable(model, X[1:2, 1:2], PSD)
JuMP.@constraint(model, X[1, 1] == 0)
JuMP.optimize!(model)
JuMP.assert_is_solved_and_feasible(model; allow_local = false)
JuMP.objective_bound(model) # 0.0, indicating that a dual bound (being 0.0) does exist for the problem

@WalterMadelim
Copy link

I find something weird, why does Mosek reports slow_progress to this

julia> import JuMP, MosekTools

julia> model = JuMP.Model(MosekTools.Optimizer) # the primal problem
A JuMP Model
├ solver: Mosek
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> JuMP.set_silent(model)

julia> JuMP.@variable(model, X[1:2, 1:2], PSD)
2×2 LinearAlgebra.Symmetric{JuMP.VariableRef, Matrix{JuMP.VariableRef}}:
 X[1,1]  X[1,2]
 X[1,2]  X[2,2]

julia> JuMP.@constraint(model, X[1, 1] == 0)
X[1,1] == 0

julia> JuMP.@objective(model, Min, 2 * X[1, 2])
2 X[1,2]

julia> JuMP.optimize!(model)

julia> JuMP.assert_is_solved_and_feasible(model; allow_local = false)
ERROR: The model was not solved correctly. Here is a summary of the solution to help debug why this happened:

* Solver : Mosek

* Status
  Result count       : 1
  Termination status : SLOW_PROGRESS
  Message from the solver:
  "Mosek.MSK_RES_TRM_STALL"

* Candidate solution (result #1)
  Primal status      : UNKNOWN_RESULT_STATUS
  Dual status        : UNKNOWN_RESULT_STATUS
  Objective value    : -1.09732e+01
  Objective bound    : -1.09732e+01
  Relative gap       : 0.00000e+00
  Dual objective value : 0.00000e+00

* Work counters
  Solve time (sec)   : 0.00000e+00
  Simplex iterations : 0
  Barrier iterations : 24
  Node count         : 0

Stacktrace:
 [1] error(s::String)
   @ Base .\error.jl:35
 [2] assert_is_solved_and_feasible(model::JuMP.Model; result::Int64, kwargs::@Kwargs{allow_local::Bool})    
   @ JuMP K:\judepot1114\packages\JuMP\xlp0s\src\optimizer_interface.jl:950
 [3] top-level scope
   @ REPL[15]:1

@WalterMadelim
Copy link

Regradless, the theoretical behavior for this SDP problem

@variable(model, X[1:2, 1:2], PSD)
@constraint(model, X[1, 1] == 0)
@objective(model, Min, 2 * X[1, 2])

should be: Its objective_bound = objective_value = 0.
Therefore this SDP essentially has a dual bound (which is not derived from the dual side).
The odds are that a solver reports DUAL_INFEASIBLE to this SDP firstly, which is not incorrect.

@odow
Copy link
Member Author

odow commented Mar 27, 2025

Your first example did not include the objective.

Here's what I get with the latest JuMP and MosekTools. The important part is objective_bound : NaN. The problem does not have a dual bound.

julia> using JuMP, MosekTools

julia> model = Model(MosekTools.Optimizer)
A JuMP Model
├ solver: Mosek
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> set_attribute(model, "fallback", "mosek://solve.mosek.com:30080")

julia> @variable(model, X[1:2, 1:2], PSD)
2×2 LinearAlgebra.Symmetric{VariableRef, Matrix{VariableRef}}:
 X[1,1]  X[1,2]
 X[1,2]  X[2,2]

julia> @constraint(model, X[1, 1] == 0)
X[1,1] = 0

julia> @objective(model, Min, 2 * X[1, 2])
2 X[1,2]

julia> optimize!(model)
Problem
  Name                   :                 
  Objective sense        : minimize        
  Type                   : CONIC (conic optimization problem)
  Constraints            : 1               
  Affine conic cons.     : 0               
  Disjunctive cons.      : 0               
  Cones                  : 0               
  Scalar variables       : 0               
  Matrix variables       : 1 (scalarized: 3)
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 2                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - primal attempts        : 1                 successes              : 1               
Lin. dep.  - dual attempts          : 0                 successes              : 0               
Lin. dep.  - primal deps.           : 0                 dual deps.             : 0               
Presolve terminated. Time: 0.00    
Optimizer  - threads                : 1               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 1               
Optimizer  - Cones                  : 1               
Optimizer  - Scalar variables       : 3                 conic                  : 3               
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00            
Factor     - dense det. time        : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 1                 after factor           : 1               
Factor     - dense dim.             : 0                 flops                  : 7.00e+00        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   7.1e-01  1.4e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.00  
1   9.7e-02  1.9e-01  1.7e-01  -3.33e-01  -1.238467732e+00  0.000000000e+00   1.4e-01  0.00  
2   2.1e-02  4.1e-02  3.9e-02  -1.05e-01  -1.656080850e+00  0.000000000e+00   2.9e-02  0.00  
3   4.5e-03  8.9e-03  8.7e-03  -4.49e-02  -1.837436144e+00  0.000000000e+00   6.3e-03  0.00  
4   9.6e-04  1.9e-03  1.9e-03  -2.07e-02  -1.923827145e+00  0.000000000e+00   1.4e-03  0.00  
5   2.1e-04  4.1e-04  4.1e-04  -9.61e-03  -1.964762106e+00  0.000000000e+00   2.9e-04  0.00  
6   4.3e-05  8.6e-05  8.6e-05  -4.42e-03  -1.983870012e+00  0.000000000e+00   6.1e-05  0.00  
7   8.9e-06  1.8e-05  1.8e-05  -2.02e-03  -1.992697438e+00  0.000000000e+00   1.3e-05  0.00  
8   1.8e-06  3.6e-06  3.6e-06  -9.14e-04  -1.996740886e+00  0.000000000e+00   2.5e-06  0.00  
9   3.4e-07  6.8e-07  6.8e-07  -4.08e-04  -1.998579228e+00  0.000000000e+00   4.8e-07  0.00  
10  6.0e-08  1.2e-07  1.2e-07  -1.77e-04  -1.999411898e+00  0.000000000e+00   8.5e-08  0.00  
11  1.2e-08  2.4e-08  2.4e-08  -8.73e-05  -1.999827434e+00  0.000000000e+00   1.7e-08  0.00  
12  2.6e-09  5.2e-09  5.2e-09  8.54e-05   -1.999173194e+00  0.000000000e+00   3.7e-09  0.00  
13  5.6e-10  1.1e-09  1.1e-09  -8.99e-04  -2.005449121e+00  0.000000000e+00   8.0e-10  0.00  
14  1.3e-10  2.5e-10  2.5e-10  7.49e-03   -1.954650036e+00  0.000000000e+00   1.8e-10  0.00  
15  3.2e-11  6.4e-11  6.9e-11  -5.51e-02  -2.328648409e+00  0.000000000e+00   4.5e-11  0.00  
16  9.9e-12  2.0e-11  1.5e-11  2.25e-01   -1.198281673e+00  0.000000000e+00   1.4e-11  0.01  
17  2.4e-12  2.3e-11  8.6e-12  -3.02e-01  -6.668106594e+00  0.000000000e+00   3.3e-12  0.01  
18  3.0e-13  7.5e-10  2.3e-13  1.86e-01   -2.845957952e-01  0.000000000e+00   4.3e-13  0.01  
19  2.4e-14  1.3e-09  2.7e-14  3.67e-03   -5.915090097e-01  0.000000000e+00   3.5e-14  0.01  
20  1.6e-15  9.8e-10  2.6e-15  -2.41e-01  -2.572824537e+00  0.000000000e+00   1.7e-15  0.01  
21  3.1e-16  7.9e-09  9.6e-16  -4.30e-01  -1.097317669e+01  0.000000000e+00   2.0e-16  0.01  
22  3.1e-16  7.9e-09  9.6e-16  -4.30e-01  -1.097317669e+01  0.000000000e+00   2.0e-16  0.01  
23  3.1e-16  7.9e-09  9.6e-16  -4.30e-01  -1.097317669e+01  0.000000000e+00   2.0e-16  0.01  
Optimizer terminated. Time: 0.01    


Interior-point solution summary
  Problem status  : UNKNOWN
  Solution status : UNKNOWN
  Primal.  obj: -1.0973176689e+01   nrm: 7e+08    Viol.  con: 7e-08    barvar: 1e-07  
  Dual.    obj: 0.0000000000e+00    nrm: 1e+08    Viol.  con: 0e+00    barvar: 2e+00  

julia> solution_summary(model)
solution_summary(; result = 1, verbose = false)
├ solver_name          : Mosek
├ Termination
│ ├ termination_status : SLOW_PROGRESS
│ ├ result_count       : 1
│ ├ raw_status         : Mosek.MSK_RES_TRM_STALL
│ └ objective_bound    : NaN
├ Solution (result = 1)
│ ├ primal_status        : UNKNOWN_RESULT_STATUS
│ ├ dual_status          : UNKNOWN_RESULT_STATUS
│ ├ objective_value      : -1.09732e+01
│ ├ dual_objective_value : 0.00000e+00
│ └ relative_gap         : NaN
└ Work counters
  ├ solve_time (sec)   : 9.68066e-03
  ├ simplex_iterations : 0
  ├ barrier_iterations : 24
  └ node_count         : 0

@WalterMadelim
Copy link

WalterMadelim commented Mar 27, 2025

Your first example did not include the objective.

Yes, I was careless. But the meaning is already conveyed.

Additionally, according to my experience, Mosek very frequently give slow_progress.
And SDP is indeed harder to handle. The numerical issues are often severe.
No wonder Gurobi do not support solving SDP problems.

@odow
Copy link
Member Author

odow commented Mar 27, 2025

I tweaked the wording to be more direct. I don't think we're going to be able to please everyone without a massive amount of detail, but this hopefully suffices for nearly everyone.

@WalterMadelim
Copy link

The updated one (c75f852) is good.

@odow odow merged commit 415409c into master Mar 27, 2025
31 checks passed
@odow odow deleted the od/dual-infeasible branch March 27, 2025 19:30
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

2 participants