# Section 11.8.4: Network rate optimization

Jump to: Source code Text output Plots Library index

    % Boyd & Vandenberghe "Convex Optimization"
    % Argyrios Zymnis - 05/03/08
    %
    % We consider a network with n flows and L links. Each flow i,
    % moves along a fixed predetermined path (i.e. a subset of the links)
    % and has an associated rate x_i. Each link j has an associated capacity
    % c_j. The total rate of all flows travelling along a link cannot exceed
    % the link capacity. We can describe these link capacity limits using the
    % flow-link incidence matrix A \in \reals^{L \times n}, where
    % A_{ij} = 1, if flow j passes through link i and 0 otherwise.
    % The link capacity constraints can be expressed as A*x <= c
    % In the network rate problem the variables are the flow rates x. The
    % objective is to choose the flow rates to maximize a separate utility
    % function U, given by
    %           U(x) = U_1(x_1)+U_2(x_2)+...+U_n(x_n)
    % The network rate optimization problem is then
    %           maximize    U(x)
    %           subject to  A*x <= c
    % Here we use U_i(x_i) = log x_i for all i

    % Input data
    rand('state',1)
    L = 20;
    n = 10;
    k = 7; %average links per flow
    A = double(rand(L,n) <= k/L);
    c = 0.9*rand(L,1)+0.1;

    % Solve network rate problem
    cvx_begin
        variable x(n);
        maximize(sum(log(x)))
        subject to
            A*x <= c
    cvx_end
    primal_obj = cvx_optval;

    % Solve dual problem to obtain link prices
    cvx_begin
        variable lambda(L);
        minimize(c'*lambda-sum(log(A'*lambda))-n)
        subject to
            lambda >= 0
    cvx_end
    dual_obj = cvx_optval;

    Successive approximation method to be employed.
       For improved efficiency, SDPT3 is solving the dual problem.
       SDPT3 will be called several times to refine the solution.
       Original size: 50 variables, 20 equality constraints
       10 exponentials add 80 variables, 50 equality constraints
    -----------------------------------------------------------------
     Cones  |             Errors              |
    Mov/Act | Centering  Exp cone   Poly cone | Status
    --------+---------------------------------+---------
     10/ 10 | 6.939e+00  2.563e+00  1.722e-09 | Solved
     10/ 10 | 2.082e+00  2.863e-01  0.000e+00 | Solved
     10/ 10 | 1.575e-01  1.558e-03  0.000e+00 | Solved
     10/ 10 | 2.021e-02  2.577e-05  0.000e+00 | Solved
     10/ 10 | 2.787e-03  4.880e-07  0.000e+00 | Solved
      0/ 10 | 3.880e-04  7.421e-09  0.000e+00 | Solved
    -----------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): -31.5685

    Successive approximation method to be employed.
       SDPT3 will be called several times to refine the solution.
       Original size: 50 variables, 20 equality constraints
       10 exponentials add 80 variables, 50 equality constraints
    -----------------------------------------------------------------
     Cones  |             Errors              |
    Mov/Act | Centering  Exp cone   Poly cone | Status
    --------+---------------------------------+---------
     10/ 10 | 5.283e+00  1.547e+00  1.451e-09 | Solved
     10/ 10 | 1.412e+00  1.312e-01  2.742e-09 | Solved
     10/ 10 | 1.306e-01  1.080e-03  2.910e-09 | Solved
     10/ 10 | 1.689e-02  1.815e-05  2.610e-09 | Solved
     10/ 10 | 2.271e-03  3.237e-07  2.635e-09 | Solved
      0/  7 | 3.067e-04  4.651e-09  2.659e-09 | Solved
    -----------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): -31.5685