0
$\begingroup$

I am relatively new to convex optimization and am looking to solve a resource allocation problem. I understand, that if my utility function is concave the following problem constitutes "an optimization of a concave function over a convex set" and should therefore have a unique solution (as an example I am looking at proportional fairness, for which utility is the logarithmic function):

\begin{array}{rrclcl} \displaystyle \max_{x} & {\sum_{c \in C} U_c(x_c)} \\ \textrm{s.t.} & \mathbf{A} \mathbf{x} & \leq & \mathbf{r} \\ & x_c & \geq & 0 & & \forall c \in C \\\\ \end{array}

Now my problem is that in my system I have users who will get a linear combination of these resources assigned. Therefore their utility is based on the sum of resources they are assigned.

I have tried to incorporate this into the problem definition, but am not sure if this is a correct way to specify an optimization problem:

\begin{array}{rrclcl} \displaystyle \max_{y} & {\sum_{c \in C} U_c(y_c)} \\ \textrm{s.t.} & \mathbf{A} \mathbf{x} & \leq & \mathbf{r} \\ & \mathbf{B} \mathbf{x} & = & \mathbf{y} \\ & x_c & \geq & 0 & & \forall c \in C \\\\ \end{array}

I believe that the statement is mathematically correct, but would like to ask:

  1. Is this formulation "standard compliant"? Should it be formulated differently to be solvable e.g. by standard optimization tools?

  2. If yes, (how) can this be done?

  3. Does this problem allow for statements about solvability/ number of solutions?

I am also happy for any pointers to related problems or terminology describing my problem - I can currently not find anything online although I am convinced that this is not an unusual problem.

$\endgroup$
  • $\begingroup$ It's an absolutely standard problem. If you study almost any text on optimization, it will define the feasible set using a list of inequalities and equalities. However, the optimization is over $(x,y)$, so your notation is a bit off. $\endgroup$ – Johan Löfberg Dec 16 '14 at 7:39
  • $\begingroup$ Could you elaborate on the notation? The way I regard it, x and y are statically linked (see equality constraint). Therefore I should only be optimizing for one variable, right? After all, I want to optimize the utility for the aggregate resources assigned to each user, and which resources are demanded by what user is preliminarily known. $\endgroup$ – Karl Hardr Dec 16 '14 at 8:51
  • 1
    $\begingroup$ The optimization algorithm optimizes over $x$ and $y$, and those are thus the decision variables. The solver does not know (or care) if some variables are special to you, or artificially introduced by you. You have a bunch of variables, describing a feasible set through inequalities and equalities. $\endgroup$ – Johan Löfberg Dec 16 '14 at 10:04
  • 2
    $\begingroup$ That's a linear programming feasibility program. $\endgroup$ – Johan Löfberg Dec 16 '14 at 11:17
  • 1
    $\begingroup$ Many thanks for all the inputs. I need to implement this in java, so I guess I'll end up using something like jOptimizer. But thanks for the references anyway :) $\endgroup$ – Karl Hardr Dec 16 '14 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.