$Is there general theory for solving optimization problem of the following kind

\begin{align} &\max _{x_1,x_2,...,x_N} N \\ \text{ s.t.}& \sum_{i=1}^N f(x_i) \le a\\ &\sum_{i=1}^N g(x_i) \le b\\ & \sum_{i=1}^N x_i \le c \end{align}

where $f()$ and $g()$ are given convex, non-negative functions. The 'weird' property of this problem is that we have to optimize over the argument of the summation. At this stage I am looking at reference and examples.

Thank you in advance.

  • $\begingroup$ Are the functions $f$ and $g$ convex? If not, please remove the "convex-optimization" tag. And is there any other information about $f$, $g$, and $x$ you can share? It matters. $\endgroup$ – Michael Grant Aug 9 '15 at 21:32
  • $\begingroup$ Yes, they are. I will add. But even then is it still a convex optimization problem? $\endgroup$ – Boby Aug 9 '15 at 21:44
  • $\begingroup$ Oh no, it's definitely not convex. But it might be quasiconvex. Again, is there anything else you can say about $f$, $g$, and $x$? For instance, are they nonnegative? Monotonic? $\endgroup$ – Michael Grant Aug 9 '15 at 21:51
  • $\begingroup$ I guess I can add non-negativity. Have you seen a problem like that in some context before? Also, for simplicity we can just look at the case when there is no $g$. $\endgroup$ – Boby Aug 9 '15 at 22:15
  • 1
    $\begingroup$ No, I haven't. But Boby, come on, details like convexity and non-negativity matter. They can spell the difference between being able to solve the problem efficiently and not being able to solve it at all. When you ask a question here you need to supply all the information about the problem you have. $\endgroup$ – Michael Grant Aug 9 '15 at 22:17

The obvious guess is going to be that the optimal solution will take the form $x_1=x_2=\dots=x_N$ for some $N$. Thus, this suggests solving the following optimization problem:

$$\begin{align*} \text{maximize } \; &N\\ \text{subject to } \; &N f(x) \le a, N g(x) \le b, Nx \le c \end{align*}$$

where $x$ ranges over $\mathbb{R}$ and $N$ ranges over $\mathbb{N}$. Now you have only a two-dimensional optimization problem.

For instance, you could iterate over $N=1,2,3,\dots$ and for each fixed $N$, search for $x \in [-\infty,c/N]$ such that $f(x) \le a/N$ and $g(x) \le b/N$. Depending on the form of $f,g$, this might be feasible to solve.

If this is possible, you could speed it up by using bisection search to find the largest such $N$ (i.e., start by iterating over $N=1,2,4,8,16,\dots$; then when you find $N_0,N_1$ such that $N_0$ is feasible and $N_1$ isn't feasible, use binary search to find the largest $N$ such that $N_0 \le N < N_1$ and $N$ is feasible).

Better yet, define

$$h(x) = \max(f(x)/a, g(x)/b, x/c).$$

You can verify that $N,x$ is a feasible solution if and only if $h(x) \le 1/N$. Thus, to maximize $N$, it suffices to find $x^*$ that minimizes $h(x)$, and take $N=\lfloor 1/h(x^*) \rfloor$. Since $h:\mathbb{R} \to \mathbb{R}$ is a unidimensional function, minimizing $h(x)$ might be feasible via a number of methods, depending on the specific properties of of $f,g$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.