5
$\begingroup$

Essentially, I am trying to solve a simple orthogonal least-squares (OLS) problem with some constraints — the coefficients must sum to $1$, no coefficient can be less than $0$, and no coefficient can be greater than $1$. I am using CVXPY for this and I get solutions for only the SCS solver.

def get_w(A, b):
    # Define the decision variables
    x = cp.Variable(
        A.shape[1], 
        nonneg=True
    )

    # Define the objective function and the constraints
    objective = cp.Minimize(cp.sum_squares(A @ x - b))
    # Define the constraints
    constraints = [cp.sum(x) == 1]  # weights must sum to 1
    other_constraints = [x <= 1, x>= 0]  # weights must not be greater than 1 and should not be nonnegative

    # Define the problem instance and solve it
    problem = cp.Problem(
        objective, 
        constraints + other_constraints
    )
    problem.solve(solver=cp.SCS, verbose=True) # using SCS solver
    # problem.solve(solver=cp.MOSEK, verbose=True) # using SCS solver
    # problem.solve(solver=cp.CVXOPT, verbose=True) # using CVXOPT solver
    # problem.solve(solver=cp.ECOS, verbose=True) # using ECOS solver
    # problem.solve(solver=cp.OSQP, verbose=True) # using OSQP solver
    print("Optimal value: ", problem.value)
    print("Optimal x: ", x.value)
    return x.value

Using SCS:

status:  solved
timings: total: 7.71e-01s = setup: 5.46e-04s + solve: 7.71e-01s
     lin-sys: 3.94e-01s, cones: 7.45e-02s, accel: 6.40e-02s
------------------------------------------------------------------
objective = 2990249263.651514
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary                                    
-------------------------------------------------------------------------------
(CVXPY) Feb 16 11:49:08 AM: Problem status: optimal
(CVXPY) Feb 16 11:49:08 AM: Optimal value: 2.983e+09
(CVXPY) Feb 16 11:49:08 AM: Compilation took 1.653e-02 seconds
(CVXPY) Feb 16 11:49:08 AM: Solver (including time spent in interface) took 7.721e-01 seconds
Optimal value:  2982885159.9210763
Optimal x:  [0.01442644 0.80144737 0.00357662 0.         0.19490373 0.
 0.00103442 0.         0.0013799  0.00129703]

However, using MOSEK:

===============================================================================
                                     CVXPY                                     
                                     v1.3.0                                    
===============================================================================
(CVXPY) Feb 16 11:50:00 AM: Your problem has 10 variables, 3 constraints, and 0 parameters.
(CVXPY) Feb 16 11:50:00 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Feb 16 11:50:00 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Feb 16 11:50:00 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation                                  
-------------------------------------------------------------------------------
(CVXPY) Feb 16 11:50:00 AM: Compiling problem (target solver=MOSEK).
(CVXPY) Feb 16 11:50:00 AM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> MOSEK
(CVXPY) Feb 16 11:50:00 AM: Applying reduction Dcp2Cone
(CVXPY) Feb 16 11:50:00 AM: Applying reduction CvxAttr2Constr
(CVXPY) Feb 16 11:50:00 AM: Applying reduction ConeMatrixStuffing
(CVXPY) Feb 16 11:50:00 AM: Applying reduction MOSEK
(CVXPY) Feb 16 11:50:00 AM: Finished problem compilation (took 1.420e-02 seconds).
-------------------------------------------------------------------------------
                                Numerical solver                               
-------------------------------------------------------------------------------
(CVXPY) Feb 16 11:50:00 AM: Invoking solver MOSEK  to obtain a solution.


(CVXPY) Feb 16 11:50:00 AM: Problem
(CVXPY) Feb 16 11:50:00 AM:   Name                   :                 
(CVXPY) Feb 16 11:50:00 AM:   Objective sense        : maximize        
(CVXPY) Feb 16 11:50:00 AM:   Type                   : CONIC (conic optimization problem)
(CVXPY) Feb 16 11:50:00 AM:   Constraints            : 11              
(CVXPY) Feb 16 11:50:00 AM:   Affine conic cons.     : 0               
(CVXPY) Feb 16 11:50:00 AM:   Disjunctive cons.      : 0               
(CVXPY) Feb 16 11:50:00 AM:   Cones                  : 1               
(CVXPY) Feb 16 11:50:00 AM:   Scalar variables       : 83              
(CVXPY) Feb 16 11:50:00 AM:   Matrix variables       : 0               
(CVXPY) Feb 16 11:50:00 AM:   Integer variables      : 0               
(CVXPY) Feb 16 11:50:00 AM: 
(CVXPY) Feb 16 11:50:00 AM: Optimizer started.
(CVXPY) Feb 16 11:50:00 AM: Presolve started.
(CVXPY) Feb 16 11:50:00 AM: Linear dependency checker started.
(CVXPY) Feb 16 11:50:00 AM: Linear dependency checker terminated.
(CVXPY) Feb 16 11:50:00 AM: Eliminator started.
(CVXPY) Feb 16 11:50:00 AM: Freed constraints in eliminator : 0
(CVXPY) Feb 16 11:50:00 AM: Eliminator terminated.
(CVXPY) Feb 16 11:50:00 AM: Eliminator started.
(CVXPY) Feb 16 11:50:00 AM: Freed constraints in eliminator : 0
(CVXPY) Feb 16 11:50:00 AM: Eliminator terminated.
(CVXPY) Feb 16 11:50:00 AM: Eliminator - tries                  : 2                 time                   : 0.00            
(CVXPY) Feb 16 11:50:00 AM: Lin. dep.  - tries                  : 1                 time                   : 0.00            
(CVXPY) Feb 16 11:50:00 AM: Lin. dep.  - number                 : 0               
(CVXPY) Feb 16 11:50:00 AM: Presolve terminated. Time: 0.01    
(CVXPY) Feb 16 11:50:00 AM: Problem
(CVXPY) Feb 16 11:50:00 AM:   Name                   :                 
(CVXPY) Feb 16 11:50:00 AM:   Objective sense        : maximize        
(CVXPY) Feb 16 11:50:00 AM:   Type                   : CONIC (conic optimization problem)
(CVXPY) Feb 16 11:50:00 AM:   Constraints            : 11              
(CVXPY) Feb 16 11:50:00 AM:   Affine conic cons.     : 0               
(CVXPY) Feb 16 11:50:00 AM:   Disjunctive cons.      : 0               
(CVXPY) Feb 16 11:50:00 AM:   Cones                  : 1               
(CVXPY) Feb 16 11:50:00 AM:   Scalar variables       : 83              
(CVXPY) Feb 16 11:50:00 AM:   Matrix variables       : 0               
(CVXPY) Feb 16 11:50:00 AM:   Integer variables      : 0               
(CVXPY) Feb 16 11:50:00 AM: 
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - threads                : 1               
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - solved problem         : the primal      
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - Constraints            : 11
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - Cones                  : 2
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - Scalar variables       : 74                conic                  : 54              
(CVXPY) Feb 16 11:50:00 AM: Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
(CVXPY) Feb 16 11:50:00 AM: Factor     - setup time             : 0.00              dense det. time        : 0.00            
(CVXPY) Feb 16 11:50:00 AM: Factor     - ML order time          : 0.00              GP order time          : 0.00            
(CVXPY) Feb 16 11:50:00 AM: Factor     - nonzeros before factor : 66                after factor           : 66              
(CVXPY) Feb 16 11:50:00 AM: Factor     - dense dim.             : 0                 flops                  : 6.40e+03        
(CVXPY) Feb 16 11:50:00 AM: ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
(CVXPY) Feb 16 11:50:00 AM: 0   1.0e+00  5.2e+05  2.0e+00  0.00e+00   -1.000000000e+00  0.000000000e+00   1.0e+00  0.01  
(CVXPY) Feb 16 11:50:00 AM: 1   2.4e-01  1.3e+05  9.9e-01  -1.00e+00  4.629821529e+00   2.539548706e+00   2.4e-01  0.02  
(CVXPY) Feb 16 11:50:00 AM: 2   1.1e-01  5.9e+04  6.7e-01  -1.00e+00  2.306848035e+01   1.611939361e+01   1.1e-01  0.02  
(CVXPY) Feb 16 11:50:00 AM: 3   3.9e-02  2.1e+04  4.0e-01  -1.00e+00  1.253251144e+02   1.019919163e+02   3.9e-02  0.02  
(CVXPY) Feb 16 11:50:00 AM: 4   1.2e-02  6.5e+03  2.2e-01  -1.00e+00  5.898058156e+02   5.109155876e+02   1.2e-02  0.02  
(CVXPY) Feb 16 11:50:00 AM: 5   4.0e-03  2.1e+03  1.3e-01  -1.00e+00  2.173195893e+03   1.923642037e+03   4.0e-03  0.02  
(CVXPY) Feb 16 11:50:00 AM: 6   1.7e-03  8.8e+02  8.2e-02  -9.99e-01  7.054617802e+03   6.460043795e+03   1.7e-03  0.02  
(CVXPY) Feb 16 11:50:00 AM: 7   6.3e-04  3.3e+02  5.0e-02  -9.99e-01  9.455825778e+03   7.884169511e+03   6.3e-04  0.03  
(CVXPY) Feb 16 11:50:00 AM: 8   1.7e-04  9.0e+01  2.6e-02  -9.99e-01  9.155019130e+04   8.576035475e+04   1.7e-04  0.03  
(CVXPY) Feb 16 11:50:00 AM: 9   1.0e-05  5.4e+00  6.4e-03  -9.97e-01  1.068711546e+06   9.733775073e+05   1.0e-05  0.03  
(CVXPY) Feb 16 11:50:00 AM: 10  5.0e-06  2.6e+00  4.4e-03  -9.95e-01  1.449409320e+06   1.252647855e+06   5.0e-06  0.03  
(CVXPY) Feb 16 11:50:00 AM: 11  1.7e-06  9.1e-01  2.6e-03  -9.85e-01  1.001732425e+07   9.472633405e+06   1.7e-06  0.03  
(CVXPY) Feb 16 11:50:00 AM: 12  4.2e-07  2.2e-01  1.3e-03  -9.71e-01  1.708644327e+07   1.478156036e+07   4.2e-07  0.03  
(CVXPY) Feb 16 11:50:00 AM: 13  4.4e-08  2.3e-02  4.0e-04  -9.91e-01  1.898620289e+08   1.692426877e+08   4.4e-08  0.03  
(CVXPY) Feb 16 11:50:00 AM: 14  9.7e-09  5.1e-03  1.7e-04  -9.24e-01  1.029521407e+09   9.549496746e+08   9.7e-09  0.03  
(CVXPY) Feb 16 11:50:00 AM: 15  3.9e-09  2.0e-03  6.0e-05  -4.64e-01  1.686150459e+09   1.625936468e+09   3.9e-09  0.03  
(CVXPY) Feb 16 11:50:00 AM: 16  2.3e-09  1.2e-03  3.4e-05  3.33e-02   2.003056288e+09   1.952261974e+09   2.3e-09  0.03  
(CVXPY) Feb 16 11:50:00 AM: 17  5.2e-10  2.7e-04  5.4e-06  3.26e-01   2.685683118e+09   2.664326403e+09   5.2e-10  0.03  
(CVXPY) Feb 16 11:50:00 AM: 18  2.6e-10  4.2e-05  3.7e-07  7.74e-01   2.931858881e+09   2.927835254e+09   8.0e-11  0.03  
(CVXPY) Feb 16 11:50:00 AM: 19  2.5e-10  4.0e-05  3.2e-07  9.45e-01   2.935162425e+09   2.931366043e+09   7.5e-11  0.03  
(CVXPY) Feb 16 11:50:00 AM: 20  1.5e-11  2.4e-06  1.8e-08  9.48e-01   2.986698162e+09   2.986446910e+09   4.5e-12  0.03  
(CVXPY) Feb 16 11:50:00 AM: 21  1.5e-11  2.4e-06  1.8e-08  9.48e-01   2.986698162e+09   2.986446910e+09   4.5e-12  0.04  
(CVXPY) Feb 16 11:50:00 AM: 22  1.5e-11  2.4e-06  1.8e-08  9.48e-01   2.986698162e+09   2.986446910e+09   4.5e-12  0.04  
(CVXPY) Feb 16 11:50:00 AM: Optimizer terminated. Time: 0.04    
(CVXPY) Feb 16 11:50:00 AM: 
(CVXPY) Feb 16 11:50:00 AM: 
(CVXPY) Feb 16 11:50:00 AM: Interior-point solution summary
(CVXPY) Feb 16 11:50:00 AM:   Problem status  : DUAL_INFEASIBLE
(CVXPY) Feb 16 11:50:00 AM:   Solution status : DUAL_INFEASIBLE_CER
(CVXPY) Feb 16 11:50:00 AM:   Primal.  obj: 1.2725221277e+01    nrm: 6e+00    Viol.  con: 9e-07    var: 0e+00    cones: 0e+00  
-------------------------------------------------------------------------------
                                    Summary                                    
-------------------------------------------------------------------------------
(CVXPY) Feb 16 11:50:00 AM: Problem status: infeasible
(CVXPY) Feb 16 11:50:00 AM: Optimal value: inf
(CVXPY) Feb 16 11:50:00 AM: Compilation took 1.420e-02 seconds
(CVXPY) Feb 16 11:50:00 AM: Solver (including time spent in interface) took 5.786e-02 seconds
Optimal value:  inf
Optimal x:  None

What does it mean for the dual to be infeasible, and why can it be solved in SCS where MOSEK fails?

Improve this question
$\endgroup$
2
  • $\begingroup$ "Simple OLS" -- just a guess, Lasso regression if the number of parameters is smaller than N, you often should include an intercept term (that is not subject to the constraints). Or mean-center Y before fitting. $\endgroup$
    – Andy W
    Commented Feb 16, 2023 at 12:36
  • $\begingroup$ Can you show the data? $\endgroup$
    – Erwin Kalvelagen
    Commented Feb 17, 2023 at 9:12

2 Answers 2

Reset to default
6
$\begingroup$

Mosek does not fail. Mosek says the problem is dual infeasible which means if the problem has solution, then it is unbounded. In fact Mosek has a quite good certificate for that.

Since your problem should not be dual infeasible my guess is your problem is ill conditioned. It seems the optimal objective value is very large.

One way to get a better conditioned problem is to minimize the norm of

A @ x - b

instead of

cp.sum_squares(A @ x - b)

There is no benefit of the squaring unless your solver only can solve QPs.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It appears Mosek was provided the dual by CVXPY. So Mosek's declaration of dual infeasible corresponds to primal infeasible of original problem (as stated in Summary, apparently produced by CVXPY, which states infeasible). Perhaps huge objective, evidenced in SCS solution, coupled into constraints in presolve, or as part of CVXPY formulation, causing Mosek to think original problem is primal infeasible? Aside from not using squared objective, could redundant constraints have contributed to difficulty (x>= 0 and sum(x) == 1 imply x <= 1).. CVX tells you when it sends dual. Maybe CVXPY doesn't? $\endgroup$
    – Mark L. Stone
    Commented Feb 16, 2023 at 21:03
  • 1
    $\begingroup$ @Pipob Puthipiroj Perhaps input data is horribly scaled (huge magnitude numbers) to have such a large optimal objective value (per SCS). Or if not, the fit is horrible to have such large residuals. One way or another, that combination of model and data is a disaster. $\endgroup$
    – Mark L. Stone
    Commented Feb 16, 2023 at 23:51
1
$\begingroup$

Also don't think the other_constraint is required. If first constraint & variable declaration constrain the following
$x$ is non negative and $ \sum_i x_i = 1$. So all $X$s will be $\le$1 anyway.
Also have a look here. Seems scaling could be an issue.
Also even by SCS the minimization opt values seems pretty high. Hope you are minimizing norm of $ A@x - y$ or $A@x+b -y $

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.