# 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

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

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. 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. 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. 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. 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 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. 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! Jul 12 '19 at 18:28

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

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

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