Skip to main content
added 3801 characters in body
Source Link
Mark L. Stone
  • 1.5k
  • 1
  • 10
  • 17

Here is a test problem without integer restriction:

>> n=6; C=7.4 ;c = 5*rand(n,1); d = 2*rand(n,1);
>> disp(c)
   2.107028387658593
   0.400055793339331
   0.396769045866593
   0.361881245993311
   4.501705030405445
   4.846541494332056

>> disp(d)
   0.782613917623122
   0.627170209734511
   1.106627159874890
   1.584096124994781
   1.596628166160420
   1.726517081119803

and here is the output from running the above program:

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

 num. of constraints = 12
 dim. of sdp    var  = 12,   num. of sdp  blk  =  6
 dim. of linear var  =  6
 dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
   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|1.7e+01|3.4e+00|1.9e+03| 1.261398e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|1.000|0.598|3.9e-06|1.4e+00|5.6e+02| 1.429249e+02 -3.878636e+01| 0:0:00| chol  1  1 
 2|1.000|0.966|1.0e-06|4.9e-02|7.2e+01| 5.719567e+01 -6.592350e+00| 0:0:00| chol  1  1 
 3|1.000|0.540|2.8e-08|2.3e-02|1.0e+01| 3.460381e+00 -5.835158e+00| 0:0:00| chol  1  1 
 4|1.000|0.442|1.6e-07|1.3e-02|4.8e+00|-2.227469e-01 -4.589011e+00| 0:0:00| chol  1  1 
 5|0.921|0.925|1.7e-08|9.6e-04|4.7e-01|-1.759148e+00 -2.201532e+00| 0:0:00| chol  1  1 
 6|1.000|0.575|1.1e-09|4.1e-04|1.7e-01|-1.906104e+00 -2.063560e+00| 0:0:00| chol  1  1 
 7|0.981|0.919|3.2e-09|3.3e-05|1.3e-02|-1.939996e+00 -1.951918e+00| 0:0:00| chol  1  1 
 8|0.961|0.971|2.6e-10|9.6e-07|3.9e-04|-1.941595e+00 -1.941964e+00| 0:0:00| chol  1  1 
 9|0.956|0.918|7.3e-11|9.8e-07|3.3e-05|-1.941656e+00 -1.941686e+00| 0:0:00| chol  1  1 
10|0.980|0.964|1.7e-11|8.4e-08|1.6e-06|-1.941660e+00 -1.941661e+00| 0:0:00| chol  1  1 
11|1.000|0.966|3.2e-13|3.9e-09|1.3e-07|-1.941660e+00 -1.941660e+00| 0:0:00| chol  1  1 
12|1.000|0.984|4.6e-14|3.2e-10|5.5e-09|-1.941660e+00 -1.941660e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value = -1.94166032e+00
 dual   objective value = -1.94166032e+00
 gap := trace(XZ)       = 5.46e-09
 relative gap           = 1.12e-09
 actual relative gap    = 1.02e-09
 rel. primal infeas (scaled problem)   = 4.58e-14
 rel. dual     "        "       "      = 3.23e-10
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 2.7e+00, 4.2e+00, 1.0e+01
 norm(A), norm(b), norm(C) = 6.9e+00, 3.4e+00, 1.4e+01
 Total CPU time (secs)  = 0.20  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 7.9e-14  0.0e+00  5.4e-10  0.0e+00  1.0e-09  1.1e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +1.94166
 
>> disp(x) % this is the optimal value of x
   0.399054349910791
   2.815385122487830
   2.241149560765849
   1.944410952569123
   0.000000007535945
   0.000000006728979

The last 2 elements of x would be exactly zero if the optimization problem were solved exactly. The slight difference from zero is due to solver optimality tolerance.

Here is a test problem without integer restriction:

>> n=6; C=7.4 ;c = 5*rand(n,1); d = 2*rand(n,1);
>> disp(c)
   2.107028387658593
   0.400055793339331
   0.396769045866593
   0.361881245993311
   4.501705030405445
   4.846541494332056

>> disp(d)
   0.782613917623122
   0.627170209734511
   1.106627159874890
   1.584096124994781
   1.596628166160420
   1.726517081119803

and here is the output from running the above program:

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

 num. of constraints = 12
 dim. of sdp    var  = 12,   num. of sdp  blk  =  6
 dim. of linear var  =  6
 dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
   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|1.7e+01|3.4e+00|1.9e+03| 1.261398e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|1.000|0.598|3.9e-06|1.4e+00|5.6e+02| 1.429249e+02 -3.878636e+01| 0:0:00| chol  1  1 
 2|1.000|0.966|1.0e-06|4.9e-02|7.2e+01| 5.719567e+01 -6.592350e+00| 0:0:00| chol  1  1 
 3|1.000|0.540|2.8e-08|2.3e-02|1.0e+01| 3.460381e+00 -5.835158e+00| 0:0:00| chol  1  1 
 4|1.000|0.442|1.6e-07|1.3e-02|4.8e+00|-2.227469e-01 -4.589011e+00| 0:0:00| chol  1  1 
 5|0.921|0.925|1.7e-08|9.6e-04|4.7e-01|-1.759148e+00 -2.201532e+00| 0:0:00| chol  1  1 
 6|1.000|0.575|1.1e-09|4.1e-04|1.7e-01|-1.906104e+00 -2.063560e+00| 0:0:00| chol  1  1 
 7|0.981|0.919|3.2e-09|3.3e-05|1.3e-02|-1.939996e+00 -1.951918e+00| 0:0:00| chol  1  1 
 8|0.961|0.971|2.6e-10|9.6e-07|3.9e-04|-1.941595e+00 -1.941964e+00| 0:0:00| chol  1  1 
 9|0.956|0.918|7.3e-11|9.8e-07|3.3e-05|-1.941656e+00 -1.941686e+00| 0:0:00| chol  1  1 
10|0.980|0.964|1.7e-11|8.4e-08|1.6e-06|-1.941660e+00 -1.941661e+00| 0:0:00| chol  1  1 
11|1.000|0.966|3.2e-13|3.9e-09|1.3e-07|-1.941660e+00 -1.941660e+00| 0:0:00| chol  1  1 
12|1.000|0.984|4.6e-14|3.2e-10|5.5e-09|-1.941660e+00 -1.941660e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value = -1.94166032e+00
 dual   objective value = -1.94166032e+00
 gap := trace(XZ)       = 5.46e-09
 relative gap           = 1.12e-09
 actual relative gap    = 1.02e-09
 rel. primal infeas (scaled problem)   = 4.58e-14
 rel. dual     "        "       "      = 3.23e-10
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 2.7e+00, 4.2e+00, 1.0e+01
 norm(A), norm(b), norm(C) = 6.9e+00, 3.4e+00, 1.4e+01
 Total CPU time (secs)  = 0.20  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 7.9e-14  0.0e+00  5.4e-10  0.0e+00  1.0e-09  1.1e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +1.94166
 
>> disp(x) % this is the optimal value of x
   0.399054349910791
   2.815385122487830
   2.241149560765849
   1.944410952569123
   0.000000007535945
   0.000000006728979

The last 2 elements of x would be exactly zero if the optimization problem were solved exactly. The slight difference from zero is due to solver optimality tolerance.

added 148 characters in body
Source Link
Mark L. Stone
  • 1.5k
  • 1
  • 10
  • 17

Because the denominator must be positive, the objective function, and hence the optimization problem is convex, and can be readily formulated and solved using CVX or a similar convex optimization tool.

cvx_begin
variable x(n)
minimize(sum(inv_pos(c + d.* x)))
x >= 0
sum(x) == C
cvx_end

You change x >= 0 to x >= small_number if you prefer. Strict inequalities are treated by the solvers as if they are non-strict inequalities.

It does not help to restrict x to integer values. That would make the problem more computationally difficult to solve. Nevertheless, to do so, merely change variable x(n) to variable x(n) integer .

Because the denominator must be positive, the objective function, and hence the optimization problem is convex, and can be readily formulated and solved using CVX or a similar convex optimization tool.

cvx_begin
variable x(n)
minimize(sum(inv_pos(c + d.* x)))
x >= 0
sum(x) == C
cvx_end

Because the denominator must be positive, the objective function, and hence the optimization problem is convex, and can be readily formulated and solved using CVX or a similar convex optimization tool.

cvx_begin
variable x(n)
minimize(sum(inv_pos(c + d.* x)))
x >= 0
sum(x) == C
cvx_end

You change x >= 0 to x >= small_number if you prefer. Strict inequalities are treated by the solvers as if they are non-strict inequalities.

It does not help to restrict x to integer values. That would make the problem more computationally difficult to solve. Nevertheless, to do so, merely change variable x(n) to variable x(n) integer .

Source Link
Mark L. Stone
  • 1.5k
  • 1
  • 10
  • 17

Because the denominator must be positive, the objective function, and hence the optimization problem is convex, and can be readily formulated and solved using CVX or a similar convex optimization tool.

cvx_begin
variable x(n)
minimize(sum(inv_pos(c + d.* x)))
x >= 0
sum(x) == C
cvx_end