Status Failed Help

Zhe_Yu · February 25, 2019, 5:21pm

Hello,

I am trying to solve an optimization problem using CVX. I have following formulations:
…
a1 * (x1 + 1/y1)^2 + b1*x1 + c1/y1 <= z
a2 * (x2 + 1/w)^2 + b2*x2 + c2/w <= z
a3 - b3 * ((x3-d1)^2 + (y3-e1)^2 + h1^2) >= w
a4 - b4 * ((x3-d2)^2 + (y3-e2)^2 + h2^2) >= v
…
minimize x1^2 + y1^2 + (x1-r1)^2 + (y1-s1)^2 + x2 + 1/y2 + (x2-r2)^2 + (y2-s2)^2 + 1/v + (v-r3)^2 + z

where variables are in boldface and non-negative. I used pow_pos(variable,2) and inv_pos(variable) to model them.

All constraints and objective function are convex expressions without compiling errors as I verified in CVX. However, failed status always show up.

Thanks for the help!

Mark_L_Stone · February 25, 2019, 6:43pm

Please show your code all solver and CVX output. It would be nice if you could include all input data so that the problem is reproducible.

Have you tried more than one solver?

Zhe_Yu · February 25, 2019, 7:21pm

Thank you for your prompt reply. I tried both sdpt3 and sedumi.
Output message:

Calling SDPT3 4.0: 975 variables, 385 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 385
 dim. of sdp    var  = 524,   num. of sdp  blk  = 262
 dim. of linear var  = 189
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|7.3e+02|9.0e+00|7.5e+19| 1.497592e+18  0.000000e+00| 0:0:00| chol  2 * 4 
 1|0.000|0.000|7.3e+02|9.0e+00|7.5e+19| 1.497592e+18 -9.059445e+08| 0:0:00| chol  2 * 4 
 2|0.000|0.000|7.3e+02|9.0e+00|7.5e+19| 1.497592e+18 -8.621661e+09| 0:0:00| chol  2 * 5 
 3|0.000|0.000|7.3e+02|9.0e+00|7.5e+19| 1.497593e+18 -4.257848e+10| 0:0:00| chol  3 * 6 
 4|0.000|0.000|7.3e+02|9.0e+00|7.5e+19| 1.497598e+18 -1.517990e+11| 0:0:00|
 *** Too many tiny steps:  restarting with the following iterate.
 *** [X,y,Z] = infeaspt(blk,At,C,b,2,1e5); chol  1  2 
 5|0.000|0.000|1.8e+01|1.0e+00|9.2e+12| 7.446943e+16 -2.274095e+06| 0:0:00|
 *** Too many tiny steps even after restarting
  stop: steps too short consecutively*
-------------------------------------------------------------------
 number of iterations   =  5
 primal objective value =  7.44694263e+16
 dual   objective value = -2.27409537e+06
 gap := trace(XZ)       = 9.17e+12
 relative gap           = 1.23e-04
 actual relative gap    = 1.00e+00
 rel. primal infeas (scaled problem)   = 1.82e+01
 rel. dual     "        "       "      = 1.00e+00
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 5.1e+06, 3.2e+05, 2.8e+06
 norm(A), norm(b), norm(C) = 9.7e+02, 5.3e+06, 2.2e+10
 Total CPU time (secs)  = 0.17  
 CPU time per iteration = 0.03  
 termination code       = -5
 DIMACS: 4.8e+01  0.0e+00  2.4e+00  0.0e+00  1.0e+00  1.2e-04
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Failed
Optimal value (cvx_optval): NaN

Code:

%% data
N = 10;
J = 1;
H = 100;
P_m = 0.1*ones(N,1);
P_RX = 0.1;
P_TX = 1;
alpha_0 = 1e-5;
sigma = 1e-13;
B_UL = 10*1e6;
B_DL = 1e6*ones(J,1);
F_u = 10e9;
F_e = 35*1e9;
L = [1, 5, 2, 3, 5, 1, 3, 5, 4, 5]'*1e6;
C = [166, 103, 185, 194, 168, 176, 175, 139, 166, 117]';
lambda = 0.5;
kappa = 1e-28;
x_e = 1000;
y_e = 0;
x_m = [267,671,375,562,779,459,617,655,460,593]';
y_m = [644,974,675,706,919,795,908,758,709,614]';

x_u_ini = 500;
y_u_ini = 500;
B_m_ini = B_UL/N*ones(N,1);
beta_u_ini = 0.2*ones(N,1);
beta_e_ini = 0.8*ones(N,J);
f_u_ini = F_u/N*ones(N,1);
f_e_ini = repmat(F_e/N,N,1);
phi_ini = 1e6*ones(J,1);
gamma_ini = 5*ones(N,1);

tau_beta_u = 2;
tau_beta_e = 2;
tau_B_m = 2;
tau_phi = 2;
tau_gamma = 2;
tau_f_u = 2;
tau_f_e = 2;
rho = 1;
%% optimization
cvx_begin
    variable x_u(1,1);
    variable y_u(1,1);
    variable B_m(N,1);
    variable beta_u(N,1);
    variable beta_e(N,J);
    variable f_u(N,1);
    variable f_e(N,J);
    variable phi(J,1);
    variable gamma_i(N,1);
    variable z(N,1);
    minimize ( lambda*sum(kappa*L.*C.*(beta_u.*f_u_ini.^2 + beta_u_ini.*f_u.^2) + tau_beta_u/2*(beta_u-beta_u_ini).^2 + tau_f_u/2*(f_u-f_u_ini).^2 ...
        + P_RX*L.*(inv_pos(B_m).*inv_pos(gamma_ini) + inv_pos(B_m_ini).*inv_pos(gamma_i)) + tau_B_m/2*(B_m - B_m_ini).^2 + tau_gamma/2*(gamma_i-gamma_ini).^2 ...
        + sum(P_TX*repmat(L,1,J).*(beta_e.*inv_pos(repmat(phi_ini',N,1)) + beta_e_ini.*inv_pos(repmat(phi',N,1))) + tau_beta_e/2*(beta_e-beta_e_ini).^2 + tau_phi/2*(repmat(phi',N,1)-repmat(phi_ini',N,1)).^2 ...
        + tau_f_e/2*(f_e-f_e_ini).^2,2)) + rho*sum(L.*(inv_pos(B_m).*inv_pos(gamma_ini) + inv_pos(B_m_ini).*inv_pos(gamma_i)) + tau_B_m/2*(B_m - B_m_ini).^2 + tau_gamma/2*(gamma_i-gamma_ini).^2 + z) )
    subject to
    sum(B_m)<=B_UL;
    sum([beta_u beta_e],2)==1;
    sum(f_u)<=F_u;
    sum(f_e)<=F_e;
    beta_u>=0; beta_u<=1; beta_e>=0; beta_e<=1; z>=0;
    f_u>=0; f_e>=0; B_m>=0; x_u>=0; x_u<=1000; y_u>=0; y_u<=1000;
    phi>=0; gamma_i>=0;
    L.*C.*(1/2*(pow_pos(beta_u + inv_pos(f_u),2) - beta_u_ini.^2 - inv_pos(f_u_ini).^2) - beta_u_ini.*(beta_u-beta_u_ini) + inv_pos(f_u_ini).^3.*(inv_pos(f_u)-inv_pos(f_u_ini)))<=z;
    
    repmat(L,1,J).*(1/2*(pow_pos((beta_e + inv_pos(repmat(phi',N,1))),2) - beta_e_ini.^2 - inv_pos(repmat(phi_ini',N,1)).^2)...
    - beta_e_ini.*(beta_e-beta_e_ini) + inv_pos(repmat(phi_ini',N,1)).^3.*(inv_pos(repmat(phi',N,1))-inv_pos(repmat(phi_ini',N,1))))...
    + repmat(L,1,J).*repmat(C,1,J).*(1/2*(pow_pos(beta_e+inv_pos(f_e),2)-beta_e_ini.^2-inv_pos(f_e_ini).^2)...
    - beta_e_ini.*(beta_e-beta_e_ini)+inv_pos(f_e_ini).^3.*(inv_pos(f_e)-inv_pos(f_e_ini)))<=repmat(z,1,J);
    
    B_DL.*log2(1+alpha_0*P_TX/sigma./(H^2+(repmat(x_u_ini,J,1)-x_e).^2+(repmat(y_u_ini,J,1)-y_e).^2)) - alpha_0*P_TX/sigma*B_DL.*((H^2+(repmat(x_u,J,1)-x_e).^2+(repmat(y_u,J,1)-y_e).^2) - (H^2+(repmat(x_u_ini,J,1)-x_e).^2+(repmat(y_u_ini,J,1)-y_e).^2))./...
    log(2)./(H^2+(repmat(x_u_ini,J,1)-x_e).^2+(repmat(y_u_ini,J,1)-y_e).^2)./(alpha_0*P_TX/sigma + (H^2+(repmat(x_u_ini,J,1)-x_e).^2+(repmat(y_u_ini,J,1)-y_e).^2))>=phi;
    
    log2(1+alpha_0.*P_m/sigma./(H^2+(repmat(x_u_ini,N,1)-x_m).^2+(repmat(y_u_ini,N,1)-y_m).^2)) - alpha_0.*P_m/sigma.*((H^2+(repmat(x_u,N,1)-x_m).^2+(repmat(y_u,N,1)-y_m).^2) - (H^2+(repmat(x_u_ini,N,1)-x_m).^2+(repmat(y_u_ini,N,1)-y_m).^2))./...
    log(2)./(H^2+(repmat(x_u_ini,N,1)-x_m).^2+(repmat(y_u_ini,N,1)-y_m).^2)./(alpha_0.*P_m/sigma + (H^2+(repmat(x_u_ini,N,1)-x_m).^2+(repmat(y_u_ini,N,1)-y_m).^2))>=gamma_i;
cvx_end

Thank you very much!

Mark_L_Stone · February 25, 2019, 7:31pm

Both solver experienced numerical difficulties and failed. I suspect the scaling of your problem is very bad, causing difficulties which sedumoi and SDPT3 are not able to overcome.

I haven’t checked to see what log is or is not applied to, which will affect the range of numbers. But the input data spans 38 1/2 orders of magnitude, which is gargantuan.Try to re-scale so that data and values appearing in your program will be closer to magnitude 1, not 1e-28 or 3.5e9.

Zhe_Yu · February 25, 2019, 8:56pm

This question may be silly. How could I re-scale those data without affecting the optimal solutions since they all have physical meanings? Thank you very much!

Mark_L_Stone · February 25, 2019, 9:10pm

Change the units. For example, km instead of mm.