22
$\begingroup$

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.

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Ryan Cory-Wright Jul 12 at 3:02
  • 2
    $\begingroup$ @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. $\endgroup$ – Kevin Dalmeijer Jul 12 at 5:27
  • 6
    $\begingroup$ 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. $\endgroup$ – ErlingMOSEK Jul 12 at 6:13
15
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – TheSimpliFire Jul 11 at 19:38
12
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Stefano Gualandi Jul 12 at 17:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Mark L. Stone Jul 12 at 17:04
  • 2
    $\begingroup$ 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! $\endgroup$ – Stefano Gualandi Jul 12 at 18:28
  • $\begingroup$ Found a paper by Luo and Zhang (2009) that goes into "quartic optimization" using semidefinite relaxation. $\endgroup$ – TheSimpliFire Jul 13 at 13:00
9
$\begingroup$

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.

$\endgroup$

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.