# Cubic programming and beyond?

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.

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.

• It might be worth noting that $x^3 \leq 1$ can be replaced with $x \leq 1$, and it might also be worth substituting "SOCP" for "quadratic", since non-convex quadratic problems can be tough to model (they are NP-hard, since the constraint $x_i^2=x_i$ models a binary variable). Assuming that you meant to say SOCP, I agree with your point, since $l_p$ norms are SOCP representable, as proven here. – Ryan Cory-Wright Jul 12 '19 at 3:02
• @Ryan Cory-Wright I changed my example to be less trivial and added a footnote on introducing binary variables. I also made the distinction between convex and non-convex problems more clear. I am not referring to $l_p$ norms, but to the product on page 201. – Kevin Dalmeijer Jul 12 '19 at 5:27
• I would also take a look at the power cone discussed in the Mosek modelling cook docs.mosek.com/modeling-cookbook/index.html. It allows to model many polynomial sets easily while the resulting model can be solved efficiently. – ErlingMOSEK Jul 12 '19 at 6:13

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?

• Thanks for the references Marco. If you have time, it would be great if you could also add some of the main points in the papers for easier future reference. – TheSimpliFire Jul 11 '19 at 19:38

+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.

• About "Polynomial Progamming", the NEOS server has a brand new interface to RAPOSa, Global Solver for Polynomial Programming Problems, available online at neos-server.org/neos/solvers/go:RAPOSa/AMPL.html – Stefano Gualandi Jul 12 '19 at 17:01
• @Stefano Gualandi Wow, you just beat me by a minute. I just saw the tweet announcing its availability on NEOS, and perused the RAPOSa site itmati.com/RAPOSa/index.html#features and was going to add mention of it. – Mark L. Stone Jul 12 '19 at 17:04
• ah ah, just coincidence,they were the last two checks before going back to home for the week end: checking twitter and propagating the last tweet on or.stackexchange. Ciao! – Stefano Gualandi Jul 12 '19 at 18:28
• Found a paper by Luo and Zhang (2009) that goes into "quartic optimization" using semidefinite relaxation. – TheSimpliFire Jul 13 '19 at 13:00

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.

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."