# What functions are easy to optimize?

Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$, a pair of intervals $x_i \subseteq [1, n]$, $y_i \subseteq [1, m]$. All quantities $\geq 0$.

I want to find the $w_i$ and $h_i$ to minimize $\sum f_i \Big(\sum _{j\in x_i} w_j, \sum _{j\in y_i} h_j \Big)$ with constraints $\sum w_i = W$ and $\sum h_i = H$. Approximations are perfectly fine.

Informally, this is a grid with column widths $w_i$ and row heights $h_i$ and cells that may span multiple rows and columns, that have costs $f_i$.

My question is, for what families $F$ does this problem have reasonably efficient solutions? The set of affine functions should work. What about step functions? Piecewise linear? Smooth monotonic? Smooth functions in general?

• Maybe this would be more suitable for Mathematics – dtech Jan 26 '14 at 18:37
• Also note the convexity of the functions. Convex functions are always easier to optimize. – Tolga Birdal Jan 26 '14 at 19:16
• @dtech, why? It's efficiency of algorithms I'm asking about. – Karolis Juodelė Jan 26 '14 at 19:34
• @KarolisJuodelė: Because you can often make the argument that optima are at vertices of polyhedra, or that you can alter the solution along a line and stay feasible etc. – einpoklum Dec 18 '16 at 17:09