Cubic programming and beyond?

Question

It is almost inevitable in Operations Research to come across linear or quadratic programming problems. The overall structures of these problems are below: \begin{align}\begin{array}{ll} \sf{Linear}\\ \max & \bf c^\top x\\ \text{s.t.} & A\bf x\le b \\ \text{and} & \bf x \ge 0 \end{array}\quad\quad\quad\quad\begin{array}{ll}\sf{Quadratic}\\\min &\frac12{\bf{x^\top}}Q\bf x+c^\top x\\\text{s.t.} & A\bf x\preceq b\\{}\end{array}\end{align} Both types of programming have their own (if not overlapping) applications; see, for example McCarl et al. (1977).

However, I have rarely heard of specific names for higher-order programming problems other than the generic "non-linear programming" term.

How much work has gone into the study of cubic/quartic etc. programming? What do the structures of these problems look like, and are there any specific examples of where they can be useful?

---

_Reference

_{[1] McCarl, B. A., Moskowitz, H., Furtan, H. (1977). Quadratic programming applications. Omega. 5(1):43-55.}

Answer 1

In addition to the excellent answers that are already posted, I want to add that for the pragmatic optimizer, quadratic may already be sufficient.

For example, the cubic constraint $x^3 \le x$ may be replaced by $xy \le x$ and $y=x^2$, which are both quadratic constraints. Note that these constraints are non-convex, which may not be desirable.*

Sometimes non-convexity can be avoided. This paper is full of examples of non-linear models that can be reformulated as second order cone programs, which are convex quadratic problems. Maximizing a product of non-negative affine functions is one of the examples.

_{*In this simple example, you may also overcome the non-linearity by introducing a binary variable. In general, this will not work.}

Answer 2

I am not sure whether you are looking for polynomial optimization like Introduction to concepts and advances in polynomial optimization by Martin Mevissen, or polynomial optimization by Hoang Tuy?

Answer 3

+1 for @MarcoLübbecke

But in addition, this is also known as "Polynomial Programming". Also look at algebraic geometry and semialgebraic sets, and sum of squares optimization: Wikipedia and Lall, 2011. This leads to such cool things as Sum of Squares Programming (optimization), for which Semidefinite Programming relaxation comes into play.

Answer 4

Thanks to everyone who answered this question for introducing the concept of polynomial programming.

From there I have found two papers that link cubic programming to convex programming, and provide some applications of cubic programming problem.

Bector (1968)

In this paper, indefinite cubic programming is considered. The general structure of the problem is given as \begin{array}{ll} \sf{Cubic}\\ \max & \left({\bf c^\top x}-{\bf x^\top} P{\bf x}-({\bf x^\top} Q{\bf x})^{\frac12}+\alpha\right)({\bf d^\top x}+\beta)\\ \text{s.t.} & A\bf x\preceq b \\ \text{and} & \bf x \ge 0 \end{array} where the expression to be optimised is a product of a quadratic term and a linear term. The change of variable ${\bf y}=t{\bf x}$ is introduced, and it is proven that the problem can be reduced to a convex programming one: \begin{array}{ll} \sf{Cubic}\\ \min & \dfrac{t^2}{{\bf c^\top y}-\frac{{\bf y^\top}P{\bf y}}t-({\bf y^\top}Q{\bf y})^{\frac12}+\alpha t}\\ \text{s.t.} & A{\bf y}-{\bf b}t\le\bf0 \\ \text{and} & {\bf{d^\top y}}+\beta t=1\\ \text{and}&t,\bf x \ge 0 \end{array} Finally, the problem is also considered with both terms being quadratic and a similar form is derived.

Henin and Doutriaux (1980)

In this paper, the convex simplex method is applied to cubic objective functions. Applications of cubic objective functions are provided below.

• Portfolio selection: maximising the expected utility of an investor; that is, finding $\max(AX+BX^2+CX^3)$ subject to $X=\sum\limits_{i=1}^n\alpha_iR_i$ and $\sum\limits_{i=1}^n\alpha_i=1$.

• Agricultural research: maximising crop yield when fertiliser amount or type changes; that is, finding $\max(a_1x+a_2y+a_3z+a_4xy+a_5xz+a_6yz+a_7xyz)$ subject to $$\begin{cases}C_xx+C_yy+C_zz\le C\\x_0\le x\le x_1\\y_0\le y\le y_1\\z_0\le z\le z_1\end{cases}$$ for fertiliser amounts $x,y,z$ and their respective costs $C_x,C_y,C_z$.

---

_References

_{[1] Bector, C. R. (1968). Indefinite cubic programming with standard errors in objective function. Unternehmensforschung. 12(1):113-120.}

_{[2] Henin, C., Doutriaux, J. (1980). A specialization of the convex simplex method to cubic programming. Rivista di matematica per le scienze economiche e sociali. 3(2):61-72.}

Answer 5

I think this question is very related to a different question I asked here: Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

Quadratization is the process of turning a cubic or higher-order problem into a quadratic one, so just like you, I was asking for specific super-quadratic problems.

There are many super-quadratic problems (for example in computer vision) but rather than doing "cubic programming" it is common to quadratize these problems and then do quadratic programming. Super-quadratic problems are sometimes called "higher-order MRFs" where MRF=Markov Random Field, and here is an example from the computer vision literature where quadratization is not performed (i.e. they actually try to solve the higher-order problem itself, as in your question). The abstract says their algorithm:

"is very general; we thus use it to derive a generic optimizer that can be applied to almost any higher-order MRF and that provably optimizes a dual relaxation related to the input MRF problem."