Why CVX completely ignores the constraints and only solves the unconstrained problem?


#1

Hello,
I’m solving the following multi-product pricing optimization problem:
maximize sum((1/beta1(i,j))*(beta0(i,j)*q(i,j) + entr(q(i,j))+ entr(1-sum(q(i,:))) + log(1-sum(q(i,:))))) \for all i & j
S.t.
for i=1:22
for j = 1:4
(q(i,j))^(1.1) <= q(i,j) <= (q(i,j))^(0.9);
end
(1-sum(q(i,:)))^1.1 <= (1-sum(q(i,:))) <= (1-sum(q(i,:)))^0.9;
end
0 <= q(i,j) <= 1; \for all i & j

The objective function is jointly concave in all q(i,j)'s. and the constraints are convex set. However, CVX completely ignores the constraints as if they don’t exist and produces the same opt_val as the if the problem were unconstrained. Also, worth mentioning there are warnings next to the scroller of the editor that states:" ‘<=’ produces a value that might be unused.".
I wonder what went wrong.
All feedback are highly welcome.


Why the cvx optimization problem solved status showed failed?
(Mark L. Stone) #2

The MATLAB editor doesn’t “understand” CVX, so I wouldn’t worry about editor warnings on CVX code lines if it looks correct to you.

Are the constraints satisfied at the reported optimal solution? You haven’t provided your CVX code or a reproducible problem. But it is certainly possible that the addition of constraints to an unconstrained problem does not change the argmax and optimal objective value. If x = argmax of unconstrained problem, then adding constraints which x satisfies will result in a constrained problem having the same argmax and optimal objective value. I’m not saying that’s what’s going on in your case, or whether you have made some error in your CVX code.


#3

Thanks Mark for the timely reply.
No, the optimal solution resulted from the constrained problem actually violates some of the constraints.
The CVX code for a reproducible problem is provided below:

beta01' = [-2.2816, -1.9523, -2.2536, -1.4745, 16.8188, -2.0293, -2.8915, -3.4460, -3.8473, -1.2261, -0.0496, -1.3876, -1.2293, 0.1692, 0.3026, -1.9599, -3.6613, 0.3603, -1.8326, -3.5659, -2.9907, -0.7342];
beta11' = [0.0947, 0.0901, 0.0957, 0.1562, 1.0000, 0.1138, 0.0532, 0.0140, 0.0221, 0.1324, 0.2267, 0.1872, 0.1352, 0.2170, 0.2044,  0.1324, 0.0065,  0.3689, 0.1112, 0.0676, 0.1423, 0.0772];
beta02' = [-1.1420, 16.4253,   0,  -0.9851, 16.0479, 1.7383,  23.3782, -1.6339,  -2.1849, 12.0077,  10.7784, 162.8688, 6.1002,  5.9763, 1.5315 , 3.0993,  2.0173, 60.1841, 4.9041, 0.5668,  0,  0];
beta12' = [0.1189, 1.0000, 0.3640,  0.1353, 1.0000, 0.2253, 1.0000, 0.1084, 0.0958, 1.0000,   1.1269, 1.0000, 0.7523, 0.7162,  0.1901, 0.5993,  0.5033, 1.0000,  0.7023, 0.4109, 1.0000, 1.0000];
beta03' = [29.2410,  5.8540, 16.0073, 26.1357,   0,   24.1386,   0,   15.0002, 10.4427,  -1.7956,   0,   0,   0,     0,    0,    0,    0,    0,    0,    0,    0,   0];
beta13' = [1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  0.7366,  1.0000,  0.1058,  1.0000,  1.0000, 1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000];
beta04' = [0,  -0.9792,  29.5871,    0,    0,    0,    0,  11.5197,    0,   0.2600,    0,    0,    0,    0,     0,     0,    0,      0,    0,    0,    0,    0];
beta14' = [1.0000,  0.1191,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  0.1426,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000,  1.0000];

cvx_begin quiet
variables q(22,4)

maximize sum((1/beta11(1))*(beta01(1)*q(1,1) + entr(q(1,1))+ entr(1-sum(q(1,1)+q(1,2)+q(1,3))) + log(1-sum(q(1,1)+q(1,2)+q(1,3)))) + (1/beta12(1))*(beta02(1)*q(1,2) + entr(q(1,2))+ entr(1-sum(q(1,1)+q(1,2)+q(1,3))) + log(1-sum(q(1,1)+q(1,2)+q(1,3)))) + (1/beta13(1))*(beta03(1)*q(1,3) + entr(q(1,3))+ entr(1-sum(q(1,1)+q(1,2)+q(1,3))) + log(1-sum(q(1,1)+q(1,2)+q(1,3)))) + (1/beta11(2))*(beta01(2)*q(2,1) + entr(q(2,1))+ entr(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4))) + log(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4)))) + (1/beta12(2))*(beta02(2)*q(2,2) + entr(q(2,2))+ entr(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4))) + log(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4)))) + (1/beta13(2))*(beta03(2)*q(2,3) + entr(q(2,3))+ entr(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4))) + log(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4)))) + (1/beta14(2))*(beta04(2)*q(2,4) + entr(q(2,4))+ entr(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4))) + log(1-sum(q(2,1)+q(2,2)+q(2,3)+q(2,4)))) + (1/beta11(3))*(beta01(3)*q(3,1) + entr(q(3,1))+ entr(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4))) + log(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4)))) + (1/beta12(3))*(beta02(3)*q(3,2) + entr(q(3,2))+ entr(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4))) + log(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4)))) + (1/beta13(3))*(beta03(3)*q(3,3) + entr(q(3,3))+ entr(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4))) + log(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4)))) + (1/beta14(3))*(beta04(3)*q(3,4) + entr(q(3,4))+ entr(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4))) + log(1-sum(q(3,1)+q(3,2)+q(3,3)+q(3,4)))) + (1/beta11(4))*(beta01(4)*q(4,1) + entr(q(4,1))+ entr(1-sum(q(4,1)+q(4,2)+q(4,3))) + log(1-sum(q(4,1)+q(4,2)+q(4,3)))) + (1/beta12(4))*(beta02(4)*q(4,2) + entr(q(4,2))+ entr(1-sum(q(4,1)+q(4,2)+q(4,3))) + log(1-sum(q(4,1)+q(4,2)+q(4,3)))) + (1/beta13(4))*(beta03(4)*q(4,3) + entr(q(4,3))+ entr(1-sum(q(4,1)+q(4,2)+q(4,3))) + log(1-sum(q(4,1)+q(4,2)+q(4,3)))) + (1/beta11(5))*(beta01(5)*q(5,1) + entr(q(5,1))+ entr(1-sum(q(5,1)+q(5,2))) + log(1-sum(q(5,1)+q(5,2)))) + (1/beta12(5))*(beta02(5)*q(5,2) + entr(q(5,2))+ entr(1-sum(q(5,1)+q(5,2))) + log(1-sum(q(5,1)+q(5,2)))) + (1/beta11(6))*(beta01(6)*q(6,1) + entr(q(6,1))+ entr(1-sum(q(6,1)+q(6,2)+q(6,3))) + log(1-sum(q(6,1)+q(6,2)+q(6,3)))) + (1/beta12(6))*(beta02(6)*q(6,2) + entr(q(6,2))+ entr(1-sum(q(6,1)+q(6,2)+q(6,3))) + log(1-sum(q(6,1)+q(6,2)+q(6,3)))) + (1/beta13(6))*(beta03(6)*q(6,3) + entr(q(6,3))+ entr(1-sum(q(6,1)+q(6,2)+q(6,3))) + log(1-sum(q(6,1)+q(6,2)+q(6,3)))) + (1/beta11(7))*(beta01(7)*q(7,1) + entr(q(7,1))+ entr(1-sum(q(7,1)+q(7,2))) + log(1-sum(q(7,1)+q(7,2)))) + (1/beta12(7))*(beta02(7)*q(7,2) + entr(q(7,2))+ entr(1-sum(q(7,1)+q(7,2))) + log(1-sum(q(7,1)+q(7,2)))) + (1/beta11(8))*(beta01(8)*q(8,1) + entr(q(8,1))+ entr(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4))) + log(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4)))) + (1/beta12(8))*(beta02(8)*q(8,2) + entr(q(8,2))+ entr(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4))) + log(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4)))) + (1/beta13(8))*(beta03(8)*q(8,3) + entr(q(8,3))+ entr(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4))) + log(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4)))) + (1/beta14(8))*(beta04(8)*q(8,4) + entr(q(8,4))+ entr(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4))) + log(1-sum(q(8,1)+q(8,2)+q(8,3)+q(8,4)))) + (1/beta11(9))*(beta01(9)*q(9,1) + entr(q(9,1))+ entr(1-sum(q(9,1)+q(9,2)+q(9,3))) + log(1-sum(q(9,1)+q(9,2)+q(9,3)))) + (1/beta12(9))*(beta02(9)*q(9,2) + entr(q(9,2))+ entr(1-sum(q(9,1)+q(9,2)+q(9,3))) + log(1-sum(q(9,1)+q(9,2)+q(9,3)))) + (1/beta13(9))*(beta03(9)*q(9,3) + entr(q(9,3))+ entr(1-sum(q(9,1)+q(9,2)+q(9,3))) + log(1-sum(q(9,1)+q(9,2)+q(9,3)))) + (1/beta11(10))*(beta01(10)*q(10,1) + entr(q(10,1))+ entr(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4))) + log(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4)))) + (1/beta12(10))*(beta02(10)*q(10,2) + entr(q(10,2))+ entr(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4))) + log(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4)))) + (1/beta13(10))*(beta03(10)*q(10,3) + entr(q(10,3))+ entr(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4))) + log(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4)))) + (1/beta14(10))*(beta04(10)*q(10,4) + entr(q(10,4))+ entr(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4))) + log(1-sum(q(10,1)+q(10,2)+q(10,3)+q(10,4)))) + (1/beta11(11))*(beta01(11)*q(11,1) + entr(q(11,1))+ entr(1-sum(q(11,1)+q(11,2))) + log(1-sum(q(11,1)+q(11,2)))) + (1/beta12(11))*(beta02(11)*q(11,2) + entr(q(11,2))+ entr(1-sum(q(11,1)+q(11,2))) + log(1-sum(q(11,1)+q(11,2)))) +  (1/beta11(12))*(beta01(12)*q(12,1) + entr(q(12,1))+ entr(1-sum(q(12,1)+q(12,2))) + log(1-sum(q(12,1)+q(12,2)))) + (1/beta12(12))*(beta02(12)*q(12,2) + entr(q(12,2))+ entr(1-sum(q(12,1)+q(12,2))) + log(1-sum(q(12,1)+q(12,2)))) +   (1/beta11(13))*(beta01(13)*q(13,1) + entr(q(13,1))+ entr(1-sum(q(13,1)+q(13,2))) + log(1-sum(q(13,1)+q(13,2)))) + (1/beta12(13))*(beta02(13)*q(13,2) + entr(q(13,2))+ entr(1-sum(q(13,1)+q(13,2))) + log(1-sum(q(13,1)+q(13,2)))) +  (1/beta11(14))*(beta01(14)*q(14,1) + entr(q(14,1))+ entr(1-sum(q(14,1)+q(14,2))) + log(1-sum(q(14,1)+q(14,2)))) + (1/beta12(14))*(beta02(14)*q(14,2) + entr(q(14,2))+ entr(1-sum(q(14,1)+q(14,2))) + log(1-sum(q(14,1)+q(14,2)))) +  (1/beta11(15))*(beta01(15)*q(15,1) + entr(q(15,1))+ entr(1-sum(q(15,1)+q(15,2))) + log(1-sum(q(15,1)+q(15,2)))) + (1/beta12(15))*(beta02(15)*q(15,2) + entr(q(15,2))+ entr(1-sum(q(15,1)+q(15,2))) + log(1-sum(q(15,1)+q(15,2)))) +  (1/beta11(16))*(beta01(16)*q(16,1) + entr(q(16,1))+ entr(1-sum(q(16,1)+q(16,2))) + log(1-sum(q(16,1)+q(16,2)))) + (1/beta12(16))*(beta02(16)*q(16,2) + entr(q(16,2))+ entr(1-sum(q(16,1)+q(16,2))) + log(1-sum(q(16,1)+q(16,2)))) +  (1/beta11(17))*(beta01(17)*q(17,1) + entr(q(17,1))+ entr(1-sum(q(17,1)+q(17,2))) + log(1-sum(q(17,1)+q(17,2)))) + (1/beta12(17))*(beta02(17)*q(17,2) + entr(q(17,2))+ entr(1-sum(q(17,1)+q(17,2))) + log(1-sum(q(17,1)+q(17,2)))) +  (1/beta11(18))*(beta01(18)*q(18,1) + entr(q(18,1))+ entr(1-sum(q(18,1)+q(18,2))) + log(1-sum(q(18,1)+q(18,2)))) + (1/beta12(18))*(beta02(18)*q(18,2) + entr(q(18,2))+ entr(1-sum(q(18,1)+q(18,2))) + log(1-sum(q(18,1)+q(18,2)))) +  (1/beta11(19))*(beta01(19)*q(19,1) + entr(q(19,1))+ entr(1-sum(q(19,1)+q(19,2))) + log(1-sum(q(19,1)+q(19,2)))) + (1/beta12(19))*(beta02(19)*q(19,2) + entr(q(19,2))+ entr(1-sum(q(19,1)+q(19,2))) + log(1-sum(q(19,1)+q(19,2)))) +  (1/beta11(20))*(beta01(20)*q(20,1) + entr(q(20,1))+ entr(1-sum(q(20,1)+q(20,2))) + log(1-sum(q(20,1)+q(20,2)))) + (1/beta12(20))*(beta02(20)*q(20,2) + entr(q(20,2))+ entr(1-sum(q(20,1)+q(20,2))) + log(1-sum(q(20,1)+q(20,2)))) + (1/beta11(21))*(beta01(21)*q(21,1) + entr(q(21,1))+ entr(1-sum(q(21,1))) + log(1-sum(q(21,1)))) + (1/beta11(22))*(beta01(22)*q(22,1) + entr(q(22,1))+ entr(1-sum(q(22,1))) + log(1-sum(q(22,1)))) )

subject to
        
for i=1:22
    if i == (1 || 4 || 6 || 9)

        (1-sum(q(i,1)+q(i,2)+q(i,3)))^1.1 <= (1-sum(q(i,1)+q(i,2)+q(i,3))) <= (1-sum(q(i,1)+q(i,2)+q(i,3)))^0.9;
        (q(i,1))^(1.1) <= q(i,1) <= (q(i,1))^(0.9);
        (q(i,2))^(1.1) <= q(i,2) <= (q(i,2))^(0.9);
        (q(i,3))^(1.1) <= q(i,3) <= (q(i,3))^(0.9);

    end
    if i == (2 || 3 || 8 || 10)

        (1-sum(q(i,1)+q(i,2)+q(i,3)+q(i,4)))^1.1 <= (1-sum(q(i,1)+q(i,2)+q(i,3)+q(i,4))) <= (1-sum(q(i,1)+q(i,2)+q(i,3)+q(i,4)))^0.9;
        (q(i,1))^(1.1) <= q(i,1) <= (q(i,1))^(0.9);
        (q(i,2))^(1.1) <= q(i,2) <= (q(i,2))^(0.9);
        (q(i,3))^(1.1) <= q(i,3) <= (q(i,3))^(0.9);
        (q(i,4))^1.1 <= q(i,4) <= (q(i,4))^0.9;
    end
    if i == (5 || 7 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20)

        (1-sum(q(i,1)+q(i,2)))^1.1 <= (1-sum(q(i,1)+q(i,2))) <= (1-sum(q(i,1)+q(i,2)))^0.9;
        (q(i,1))^(1.1) <= q(i,1) <= (q(i,1))^(0.9);
        (q(i,2))^(1.1) <= q(i,2) <= (q(i,2))^(0.9);
        
    end
    
    if i == (21 || 22)

        (1-sum(q(i,1)))^1.1 <= (1-sum(q(i,1))) <= (1-sum(q(i,1)))^0.9;
        (q(i,1))^1.1 <= q(i,1);
        q(i,1) <= (q(i,1))^0.9;
    end
    
end
0 <= q <= 1;
cvx_end

I tested this problem and it have the same behavior too (it completely ignores the constraints).

Thanks,


(Mark L. Stone) #4

Don’t use quiet option when you are trying to figure out what’s going on. I moved the ’ from the end of the beta 's to after the ] .

There seem to be some numerical difficulties, but the problem was reported as solved using sedum, sdpt3, both using the CVX successive approximation method. I also solved it using scs and ecos, which allow the problem to be solved under CVX 3.0beta without using the successive approximation method. All but ecos reported optimal objective value of about 263.774. Ecos resulted in optimal objective value of 634.568. I didn’t check whether any constraints are violated. Here are optimal q from sedumi and ecos. Optimal q from sdpt3 and scs are close to sedumi. I leave the checking to you.

Please remove the quiet option, and show us the solver output, optimal q, and tell us which constraints are violated (by more than solver tolerance).

>> q_sedumi
q_sedumi =
   0.002392869856400   0.003711522250495   0.451230585781482   0.268681170791739
   0.011552942045241   0.267798711214686   0.000009329302037   0.018812086841683
   0.002358898123310   0.000008805419524   0.000002806682749   0.533549346914259
   0.001491091392390   0.004173585291454   0.502955171894806   0.500000009012279
   0.588753809816936   0.272359860098857   0.500000009012279   0.500000009012279
   0.003198799189455   0.009676083300623   0.484499028588143   0.500000009012279
   0.005907393263824   0.394077431838779   0.500000009012279   0.500000009012279
   0.008609904363871   0.006569946835253   0.105449460173302   0.000011799572845
   0.006023071682747   0.013127588520691   0.078693682942410   0.500000009012279
   0.018816814523657   0.112305432564791   0.015123012236655   0.072694236388855
   0.042054428442363   0.469572444004021   0.500000009012279   0.500000009012279
   0.000000006899459   0.957226352594983   0.500000009012279   0.500000009012279
   0.034889862012982   0.311370284146732   0.500000009012279   0.500000009012279
   0.071532896266191   0.372691032179696   0.500000009012279   0.500000009012279
   0.069911439257293   0.274091569218333   0.500000009012279   0.500000009012279
   0.023633365836575   0.233424223433776   0.500000009012279   0.500000009012279
   0.008878838970183   0.021405731740284   0.500000009012279   0.500000009012279
   0.000000146491048   0.930108631213285   0.500000009012279   0.500000009012279
   0.025555099249546   0.255317859157633   0.500000009012279   0.500000009012279
   0.007742367678177   0.107820571915063   0.500000009012279   0.500000009012279
   0.017830820843114   0.500001784043039   0.500000009012279   0.500000009012279
   0.131714208156186   0.500000009012279   0.500000009012279   0.500000009012279
>> q_ecos
q_ecos =
   0.073167328945758   0.062499394950039   0.083749863206296   0.078866574421503
  -0.094605262166300   0.113421669689059   0.000688694231904  -0.054659807312390
  -0.120716805459543  -0.072788836851630   0.022916615711447   0.204203076011355
  -0.079704496722009  -0.067596830264093   0.220047959823418   0.806125845543143
   0.113185111889624   0.102648915322754   0.806125845543143   0.806125845543143
  -0.100848903005517   0.001469054113780   0.177064160607734   0.806125845543143
  -0.139924613538999   0.239159916769657   0.806125845543143   0.806125845543143
  -0.180045657934601  -0.087889077778372   0.147034175869670   0.034724016375255
  -0.185161613748503  -0.071971736954673   0.161990821769124   0.806125845543143
  -0.054683534480763   0.077877058053651  -0.079203177943231   0.006900347272069
   0.014626443145947   0.101789251617468   0.806125845543143   0.806125845543143
  -0.196874569824234   0.732929351436368   0.806125845543143   0.806125845543143
  -0.023719436009005   0.103217922504634   0.806125845543143   0.806125845543143
   0.023900934888875   0.088475022882931   0.806125845543143   0.806125845543143
   0.021847771541808   0.085087814861867   0.806125845543143   0.806125845543143
  -0.042963488476813   0.092713411934060   0.806125845543143   0.806125845543143
  -0.206623438347529   0.042706453973956   0.806125845543143   0.806125845543143
  -0.119700502675087   0.494473362846612   0.806125845543143   0.806125845543143
  -0.049597057087071   0.104888879595558   0.806125845543143   0.806125845543143
  -0.125580306042257   0.096401931286770   0.806125845543143   0.806125845543143
   0.597960173022128   0.806125845543143   0.806125845543143   0.806125845543143
   0.668173333437652   0.806125845543143   0.806125845543143   0.806125845543143

Edit: I used ECOS 2.04. As can plainly be seen, the optimal q from ECOS has negative components which violate the constraint 0 <= q <= 1. So something is wrong with either CVX 3.0beta (which does have some bugs) or ECOS. The other solvers pretty much agree, so I leave it you to point out the constraint violation(s) by the returned optimal solution.


(Michael C. Grant) #5

Indeed, it’s looking like CVX 3.0 has some holes. I’m thinking I should pull down the language recommending people try it for now, because my support bandwidth is limited right now.