Global Optimization

Nina Dokeva, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

This talk will discuss the numerical global optimization functionality in the Wolfram Language. 

It builds upon the convex and convertible to convex optimization functionality developed previously and extends to functionality for solving non-linear non-convex problems with real valued and mixed-integer variables. 

Available methods and library solvers will be discussed and illustrated by examples.

Overview of the talk

This talk will discuss

global numerical optimization function(s) in the Wolfram Language

problem classification and processing

method framework and solvers

examples

Global Numerical Optimization Function

(RefLink[NMinimize, paclet:ref/NMinimize]) —  minimize {(Subscript[f, 0])(x)|(Subscript[f, i])(x)≤0} 
Aims to find a global minimum for the objective function (Subscript[f, 0])(x) subject to constraints ((Subscript[f, i])(x)≤0).
Numerically solves constrained or unconstrained, linear or non-linear, convex or non-convex, real-valued or mixed-integer optimization problems.

helper functions:  (RefLink[NMaximize, paclet:ref/NMaximize])  ▪  (RefLink[NMinValue, paclet:ref/NMinValue])  ▪  (RefLink[NMaxValue, paclet:ref/NMaxValue])  ▪  (RefLink[NArgMin, paclet:ref/NArgMin])  ▪  (RefLink[NArgMax, paclet:ref/NArgMax])

Example :

(RefLink[NMinimize, paclet:ref/NMinimize])[{objective,constraints},{x,y,…}]

NMinimize[{(x^2)-(((y-1))^2),(x^2)+(y^2)≤4},{x,y}]

Now (V13.2+) one can also use:
(RefLink[NMinimize, paclet:ref/NMinimize])[objective,constraints,{x,y,…}]

NMinimize[(x^2)-(((y-1))^2),(x^2)+(y^2)≤4,{x,y}]

constraints can take different forms:

NMinimize[{(x^2)-(((y-1))^2),Norm[{x,y}]≤2},{x,y}]

VectorGreaterEqual[{{x,y,2},0},{"NormCone",3}]

NMinimize[{(x^2)-(((y-1))^2),{x,y,2}(Underscript[\[VectorGreaterEqual], (NormConeList[3])])0},{x,y}]

(RefLink[NMinimize, paclet:ref/NMinimize])[…,x∈rdom]

NMinimize[(x^2)-(((y-1))^2),{x,y}∈Disk[{0,0},2]]

NMinimize[(x^2)-(((y-1))^2),{x,y}∈Disk[{0,0},2],{x,y∈Integers}]

Show[Plot3D[(x^2)-(((y-1))^2),{x,y}∈Disk[{0,0},2]],Graphics3D[{PointSize[0.03],Blue,Point[{0,-2,-9}]}]]

Convex? Let’s check:

NMinimize[(x^2)-(((y-1))^2),(x^2)+(y^2)≤4,{x,y}, Method->"Convex"]

The objective is not convex, but it is a difference of convex

NMinimize[(x^2)-(((y-1))^2),(x^2)+(y^2)≤4,{x,y}, Method->"DifferenceOfConvex"]

Wolfram Language Optimization Functions

General Convex & Nonconvex Optimization

(RefLink[FindMinimum, paclet:ref/FindMinimum]) — numerical local constrained optimization

(RefLink[FindMaximum, paclet:ref/FindMaximum])  ▪  (RefLink[FindMinValue, paclet:ref/FindMinValue])  ▪  (RefLink[FindMaxValue, paclet:ref/FindMaxValue])  ▪  (RefLink[FindArgMin, paclet:ref/FindArgMin])  ▪  (RefLink[FindArgMax, paclet:ref/FindArgMax])

(RefLink[NMinimize, paclet:ref/NMinimize]) — numerical global constrained optimization

(RefLink[NMaximize, paclet:ref/NMaximize])  ▪  (RefLink[NMinValue, paclet:ref/NMinValue])  ▪  (RefLink[NMaxValue, paclet:ref/NMaxValue])  ▪  (RefLink[NArgMin, paclet:ref/NArgMin])  ▪  (RefLink[NArgMax, paclet:ref/NArgMax])

(RefLink[Minimize, paclet:ref/Minimize]) — symbolic global constrained optimization

(RefLink[Maximize, paclet:ref/Maximize])  ▪  (RefLink[MinValue, paclet:ref/MinValue])  ▪  (RefLink[MaxValue, paclet:ref/MaxValue])  ▪  (RefLink[ArgMin, paclet:ref/ArgMin])  ▪  (RefLink[ArgMax, paclet:ref/ArgMax])

New in 12.2

(RefLink[ConvexOptimization, paclet:ref/ConvexOptimization]) — minimize {(Subscript[f, 0])(x)|(Subscript[f, i])(x)≤0}with (Subscript[f, i])convex}

(RefLink[ParametricConvexOptimization, paclet:ref/ParametricConvexOptimization]) — minimize {(Subscript[f, 0])(x,θ)|(Subscript[f, i])(x,θ)≤0} with parameters θ

(RefLink[RobustConvexOptimization, paclet:ref/RobustConvexOptimization]) — minimize {(Subscript[f, 0])(x)|(Subscript[∀, θ,(Subscript[g, j])(θ)≤0])(Subscript[f, i])(x,θ)≤0} with uncertainties θ

Convex Optimization Classes — new in 12.0 and 12.1

(RefLink[LinearOptimization, paclet:ref/LinearOptimization]) — minimize {c.x|a.x+b \[VectorGreaterEqual]0}}

(RefLink[LinearFractionalOptimization, paclet:ref/LinearFractionalOptimization]) — minimize {(α.x+β)/(γ.x+δ)|a.x+b\[VectorGreaterEqual]0}

(RefLink[QuadraticOptimization, paclet:ref/QuadraticOptimization]) — minimize {(1/2)x.q.x+c.x|a.x+b\[VectorGreaterEqual]0}

(RefLink[SecondOrderConeOptimization, paclet:ref/SecondOrderConeOptimization]) — minimize {c.x|‖(Subscript[a, j]).x+(Subscript[b, j])‖≤(Subscript[α, j])+(Subscript[β, j]),j=1… k}

(RefLink[SemidefiniteOptimization, paclet:ref/SemidefiniteOptimization]) — minimize {c.x|(Subscript[a, 0])+(Subscript[x, 1])(Subscript[a, 1])+…+(Subscript[x, k])(Subscript[a, k])(Subscript[\[VectorGreaterEqual], (Subscript[𝒮, +]^n)])0}

(RefLink[ConicOptimization, paclet:ref/ConicOptimization]) — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1… k}

The following is generally non-convex but can be transformed and solved as convex:

(RefLink[GeometricOptimization, paclet:ref/GeometricOptimization]) — minimize {(∑_(j=1)^(Subscript[k, 0]))(Subscript[c, j0])(∏_(l=1)^n)(Subscript[x, l]^(Subscript[α, jl0]))|(∑_(j=1)^(Subscript[k, i]))(Subscript[c, ji])(∏_(l=1)^n)(Subscript[x, l]^(Subscript[α, jli]))≤ 1,i=1,…,s}

Additional optimization functions

(RefLink[FindFit, paclet:ref/FindFit]) — optimal nonlinear constrained or unconstrained fit to data

(RefLink[LeastSquares, paclet:ref/LeastSquares]) — least-squares problem in matrix form

and other specialized optimization functions at https://reference.wolfram.com/language/guide/Optimization.html

Automatic processing and classification

What problem are we solving?

Linear

Convex (Conic: Linear, Quadratic, SecondOrderCone, Semidefinite, with Power and Exponential cones)

Transformable to convex (Geometric Optimization, Quasi-convex, Differences of Convex)

Non-linear non-convex

Definitions

Conic Optimization

(RefLink[ConicOptimization, paclet:ref/ConicOptimization]) — minimize {c.x|(Subscript[a, 0]).x+(Subscript[b, 0])=0,(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1,… ,k}

Problem formulation

A conic optimization problem consists of minimizing a convex function over the intersection of an affine subspace and a proper cone.

Often the objective function f is linear, in which case the standard form of a conic linear optimization problem is

minimize {f =c.x|x(Subscript[\[VectorGreaterEqual], 𝒦])0, A x=b}

Alternatively, the constraints can also be combined and formulated as A x + b (Subscript[⪰, 𝒦])0.

The above reduces to a linear optimization problem if the cone K is (Subscript[ℝ, ≥0]^n), a second order cone optimization problem in the case  𝒦=(𝒬^n) and a semidefinite optimization problem when 𝒦=(Subscript[𝒮, +]^n) respectively.

ConicOptimization — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1,… ,k}

Cone definitions

A cone is a region 𝒦⊂(ℝ^n) with all rays from the origin included, i.e. x ∈𝒦 ⟹α x ∈ 𝒦 for all α ≥0.

A cone 𝒦 is convex if x,y ∈ 𝒦 ⟹α x + β y ∈ 𝒦 for all α, β ≥0.

A pointed cone is a convex cone K that does not contain a full subspace: 𝒦 ⋂ (-𝒦) = {0}. 

Finally, a proper cone is a pointed cone that is closed and full-dimensional.

Let 𝒦 be a proper cone, then we can introduce a partial ordering (Subscript[⪯, 𝒦]) by: x(Subscript[⪯, 𝒦])y if and only if y-x∈𝒦 and  x(Subscript[≺, 𝒦])yifandonlyify-x∈(𝒦^◦)(the interior of 𝒦)

Available cones

({{, {"NonNegativeCone", n}, (Subscript[ℝ, ≥0]^n),  x∈(ℝ^n) such that (Subscript[x, i])≥0}, {, {"NormCone", n}, (𝒬^n),  x∈(ℝ^n)  such that (Norm[{(Subscript[x, 1]),…,(Subscript[x, n-1])}])≤(Subscript[x, n])}, {, {"SemidefiniteCone", n}, (Subscript[𝒮, +]^n), symmetric positive semidefinite matrices x∈(ℝ^(n×n))}, {, "ExponentialCone", (Subscript[𝒦, exp]),  x∈(ℝ^3) such that (Subscript[x, 2])(e^(((Subscript[x, 1])/(Subscript[x, 2]))))≤(Subscript[x, 3])∧(Subscript[x, 2])≥ 0}, {, "DualExponentialCone", (Subscript[𝒦, exp]^( * )),  x∈(ℝ^3) such that -(Subscript[x, 1])(e^(((Subscript[x, 2])/(Subscript[x, 1])-1)))≤(Subscript[x, 3])∧(Subscript[x, 1])<0 or (Subscript[x, 1])==0∧(Subscript[x, 2])==0∧(Subscript[x, 3])==0}, {, {"PowerCone",α}, (Subscript[𝒦, α]),  x∈(ℝ^3) such that (Subscript[x, 1]^α)(Subscript[x, 2]^(1-α))≥|(Subscript[x, 3])|∧(Subscript[x, 1])≥0 ∧(Subscript[x, 2])≥0}, {, {"DualPowerCone",α}, (Subscript[𝒦, α]^( * )),  x∈(ℝ^3) such that ((((Subscript[x, 1])/α))^α)((((Subscript[x, 2])/(1-α)))^(1-α))≥|(Subscript[x, 3])|∧(Subscript[x, 1])≥0 ∧(Subscript[x, 2])≥0}})

“NonNegativeCone”

Conic inequality: x (Subscript[\[VectorGreaterEqual], 𝒦]) 0 ⧦ x ∈ 𝒦 for a proper cone 𝒦

Let v={x,y} ∈ (((Reals))^2) . Then  v\[VectorGreaterEqual]0  ⟺ {x≥ 0,y≥0}  ⟺ v ∈ (NonNegativeConeList[2])

VectorGreaterEqual[{v,0}]

VectorGreaterEqual[{{x,y}, 0}]

VectorGreaterEqual[{{x,y},0}, {"NonNegativeCone",2}]

Graphics[{LightBlue,Rectangle[]}, Axes->True, Epilog->{Disk[{.4,.43},.01],Inset[Style["{x,y}",15],{Center, Center},{Center,Center}]}]

“NormCone”

First define the n-dimensional NormCone  (𝒬^n) as x∈(ℝ^n) such that ||{(Subscript[x, 1]),..., (Subscript[x, n-1])}||≤(Subscript[x, n])

When n=2, (Q^2) is the set of all {x,y} such that (Abs[x])≤y.

v={x,y}(Subscript[\[VectorGreaterEqual], (NormConeList[2])])0⧦ v={x,y} ∈ (NormConeList[2])⧦|x|≤ y

Plot[Abs[x],{x,-1,1},Filling->Top]

VectorGreaterEqual[{{x,y},0},{"NormCone",2}]

When n=3,  (𝒬^3) is the set of all {x,y,z} such that ||{x,y}||≤z⧦(Sqrt[(x^2)+(y^2)])≤z.

v={x,y,z}(Subscript[\[VectorGreaterEqual], (NormConeList[3])])0⧦ v={x,y,z} ∈ (NormConeList[3])⧦(Sqrt[(x^2)+(y^2)])≤z

RegionPlot3D[x^2+y^2≤z^2,{x, -1,1},{y,-1,1},{z,0,1}, PlotPoints->100]

VectorGreaterEqual[{{x,y,z},0},{"NormCone",3}]

Example: represent the nonlinear inequality (x^2)+(y^2)≤4  in conic form:

  (x^2)+(y^2)≤4 ⧦||{x,y}||≤2 ⧦{x,y,2}∈(Q^3)⧦{x,y,2}(Underscript[\[VectorGreaterEqual], (NormConeList[3])])0

VectorGreaterEqual[{{x,y,2} ,0}, {"NormCone",3}]

ConicOptimization transforms the problem internally and we can ask for the canonical form of the conic constraints.

ConicOptimization[0, (x^2)+(y^2)≤4, {x,y},"ConicConstraints"]

“SemidefiniteCone”

Define the SemidefiniteCone (Subscript[𝒮, +]^n) as the set of symmetric positive semidefinite matrices S∈(ℝ^n)×(ℝ^n)
 (Subscript[𝒮, +]^n) = { S ∈ (ℝ^(n ×n)):Sᵀ=S, xᵀ·S ·x ≥0  for  any  x ∈(ℝ^n) }

for n = 2 : S=(({{x, y}, {y, z}}))∈(SemidefiniteConeList[2]) ⧦S=(({{x, y}, {y, z}}))(Underscript[\[VectorGreaterEqual], (SemidefiniteConeList[2])])0⟺{x ≥ 0, z ≥ 0, x z -(y^2)≥0}

RegionPlot3D[x≥0&&z≥0&&x z≥y^2, {x,0,1},{y,-1,1}, {z,0,1}, PlotPoints->100, AxesLabel->{"x","y","z"}]

VectorGreaterEqual[{{{x,y},{y,z}} ,0}, {"SemidefiniteCone",2}]

“PowerCone”

The power cone (Subscript[𝒦, α]), 0<α<1, is defined as  x∈(ℝ^3) such that (Subscript[x, 1]^α)(Subscript[x, 2]^(1-α))≥|(Subscript[x, 3])|,(Subscript[x, 1])≥0 ,(Subscript[x, 2])≥0.

RegionPlot3D[α=0.3;(Subscript[x, 1]^α) (Subscript[x, 2]^(1-α))≥Abs[(Subscript[x, 3])],{(Subscript[x, 1]),0,1},{(Subscript[x, 2]),0,1},{(Subscript[x, 3]),-1,1},PlotPoints->100,AxesLabel->{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}]

“ExponentialCone”

The exponential cone (Subscript[𝒦, exp]) is defined as x∈(ℝ^3) such that  (Subscript[x, 2])(e^(((Subscript[x, 1])/(Subscript[x, 2]))))≤(Subscript[x, 3]), (Subscript[x, 2])≥ 0.

RegionPlot3D[(Subscript[x, 2])(E^((Subscript[x, 1])/(Subscript[x, 2])))≤(Subscript[x, 3]),{(Subscript[x, 1]),-2,1},{(Subscript[x, 2]),0.01,1},{(Subscript[x, 3]),0,2},PlotPoints->100,AxesLabel->{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}]

Convex Optimization

(RefLink[ConvexOptimization, paclet:ref/ConvexOptimization]) — 
minimize {(Subscript[f, 0])(x)|(Subscript[f, i])(x)≤0, (Subscript[h, j])(x)=0}with (Subscript[f, i])convex,(Subscript[h, j]) affine((Subscript[a, j]).x+(Subscript[b, j]))}

Convex minimization studies the problem of minimizing convex functions over convex sets .


Definition. A set C ⊂ (ℝ^n) is called convex if for any x, y ∈ C and 0≤t≤1 then t x + (1-t )y ∈C.

Definition. A function f : ((ℝ )^n)->ℝ is called convex if its domain C is a convex set and f(t x+ (1-t) y) ≤t f(x)+(1-t)f(y) for all x,(Subscript[y,  ])∈C and all 0≤t≤1.

Theorem. If (SuperStar[x])is a locally optimal point (a local minimum or a local maximum) for the convex function f over a convex set C, then (SuperStar[x]) is globally optimal.

QuasiConvex Optimization

Quasiconvex minimization studies the problem of minimizing quasiconvex functions over convex sets. More specifically, the optimization problem

minimize    (Subscript[f, 0])(x)
subject to   (Subscript[f, i])(x)≤ 0, i = 1,...m
(Subscript[h, j])(x)=0, j=1,...p

is a quasiconvex optimization problem if (Subscript[f, 0])(x) is quasiconvex, (Subscript[f, i])(x),i≥1 are convex and (Subscript[h, j])(x) are affine ((Subscript[h, j])(x) = (Subscript[a, j]).x+(Subscript[b, j]))

Definition. A function f : ((ℝ )^n)->ℝ is called convex if its domain C is convex, and f(t x+ (1-t) y) ≤t f(x)+(1-t)f(y) for all x,(Subscript[y,  ])∈C and all 0≤t≤1

Definition. A function f : ((ℝ )^n)->ℝ is called quasiconvex if its domain C is convex, and f(t x+ (1-t) y) ≤max(f(x),f(y)) for all x,(Subscript[y,  ])∈C and all 0≤t≤1

GraphicsRow[{Plot[x^2, {x,-1,1},Axes->False, Epilog->{PointSize[0.04], Point[{{-.75,.75^2},{-.25,.25^2}}], Line[{{-.75,.75^2},{-.25,.25^2}}],Text[Style[{x, f[x]},Large],{-.4,0.6}],Text[Style[{y, f[y]},Large],{-0.05,0.25}],Text[Style["Convex",Large, Orange],{0,.95}]}],Plot[Sqrt[Abs[x]], {x,-1,1},Axes->False, Epilog->{PointSize[0.04], Point[{{-.5,Sqrt[.5]},{-.05,Sqrt[.05]}}],Line[{{-.5,Sqrt[.5]},{-.05,Sqrt[.5]}}],Text[Style[{x, f[x]},Large],{-.75,0.6}],Text[Style[{y, f[y]},Large],{-0.45,0.25}],Text[Style["Quasionvex",Large, Orange],{0,.95}]}]}]

GraphicsRow[{Plot[x^2, {x,-1,1},Axes->False, Epilog->{PointSize[0.04], Point[{-.75,.75^2}],Point[{.25,.25^2}], Line[{{-.75,.75^2},{.25,.25^2}}],Text[Style[{x, f[x]},Large],{-.6,0.75}],Text[Style[{y, f[y]},Large],{0.5,0.25}],Text[Style["Convex",Large, Orange],{0,.95}]}],Plot[Sqrt[Abs[x]], {x,-1,1},Axes->False, Epilog->{PointSize[0.04], Point[{-.5,Sqrt[.5]}],Point[{.1,Sqrt[.1]}],Line[{{-.5,Sqrt[.5]},{.1,Sqrt[.5]}}],Text[Style[{x, f[x]},Large],{-.6,0.55}],Text[Style[{y, f[y]},Large],{0.5,0.25}],Text[Style["Quasionvex",Large, Orange],{0,.95}]}]}]

Definition (alternative). A function f : ((ℝ )^n)->ℝ is called quasiconvex if its domain C is convex and for any α ∈ ℝ, its α-sublevel sets {x ∈ C | f (x) ≤ α} are convex.

Differences of Convex Optimization

minimize    (Subscript[f, 0])(x)-(Subscript[g, 0])(x)
subject to   (Subscript[f, i])(x)-(Subscript[g, i])(x)≤ 0, i = 1,..., m
(Subscript[h, j])(x)=0, j=1,..., p
is a quasiconvex optimization problem if (Subscript[f, i])(x),(Subscript[g, i])(x) are convex and (Subscript[h, j])(x) are affine ((Subscript[h, j])(x) = (Subscript[a, j]).x+(Subscript[b, j]))

Geometric Optimization

(RefLink[GeometricOptimization, paclet:ref/GeometricOptimization]) — minimize {(∑_(j=1)^(Subscript[k, 0]))(Subscript[c, j0])(∏_(l=1)^n)(Subscript[x, l]^(Subscript[α, jl0]))|(∑_(j=1)^(Subscript[k, i]))(Subscript[c, ji])(∏_(l=1)^n)(Subscript[x, l]^(Subscript[α, jli]))≤ 1,i=1,…,s}

Definitions

(RefLink[GeometricOptimization, paclet:ref/GeometricOptimization])[f,cons,vars]    finds positive values of variables vars that minimize the posynomial objective subject to posynomial constraints cons.

Geometric optimization is often used when minimizing quantities like area, volume or power.

Geometric optimization finds x\[VectorGreater]0 that solves the primal problem:

({{      , minimize, (Subscript[g, 0])(x)}, {      , subject to constraints, (Subscript[g, i])(x)≤ 1,i=1,…,s,
(Subscript[c, (Subscript[i, eq])])(Subscript[m, (Subscript[i, eq])])(x)==1}, {      , where, (Subscript[g, i])(x), i=0,…,s, are generalized posynomials
(Subscript[c, (Subscript[i, eq])])>0,(Subscript[m, (Subscript[i, eq])])(x) are monomials, (Subscript[i, eq])=0,…,(Subscript[s, eq])}})

A monomial is a product of powers, m(x)= (Subscript[x, 1]^(Subscript[α, 1]))(Subscript[x, 2]^(Subscript[α, 2]))(Subscript[…x, k]^(Subscript[α, k])) with (Subscript[α, i])∈ℝ. 
A posynomial is a positive sum of monomials p(x)=(Subscript[Σ, j]) (Subscript[c, j])(Subscript[m, j])(x) with (Subscript[c, j])≥0.

A generalized posynomial g(x) is a posynomial or a combination (sum, product, maximum or a positive real power) of generalized posynomials.

Example

Minimize the length of the diagonal of a rectangle of area 4 such that the width plus three times the height is less than 7:

GeometricOptimization[(Sqrt[(h^2)+(w^2)]),{w h ==4, w + 3h ≤ 7},{w,h}]

NMinimize[{(Sqrt[(h^2)+(w^2)]),{w h ==4, w + 3h ≤ 7,h>0,w>0}},{w,h}]

Examples

Convex

Any local minimum is a global minimum.
We can solve large convex problems efficiently:

n=100000;NMinValue[{Total[x],Norm[x]<=1},x∈Vectors[n]]//AbsoluteTiming

Geometric Optimization

Minimize the perimeter of a rectangle such that the area is 1 and the height is at most half the width :

NMinimize[{2 w+2 h,h w==1,h<=1/2 w,h>=0,w>=0},{h,w}]

This problem is log-convex and is solved by making a transformation {h -> Exp[H], w -> Exp[W]} and taking logarithms to get the convex problem :

h w == 1 -> Exp[H] Exp[W] == Exp[0]
Take Log : H + W == 0

GeometricOptimization[2 w+2 h,{h w==1,h<=1/2 w},{h,w},{"PrimalMinimumValue", "PrimalMinimizerRules"}]

Another example :

Maximize the area of a rectangle such that the perimeter is at most 1:

NMinimize[{(1/(w h)),{2 w+2 h<=1, w>0, h>0}},{h,w}]

h w == 1 -> (1/(Exp[H] Exp[W])) == Exp[-W - H]
Take Log : -W - H

GeometricOptimization[(1/(w h)),2 w+2 h<=1,{h,w},{"PrimalMinimumValue", "PrimalMinimizerRules"}]

Quasiconvex

The objective f(x,y)=-x y is quasiconvex because the function is monotonic when x≥0, y≥0 .

res =NMinimize[{-x y,{Norm[{2x-1,y-1}]≤1,x≥0,y≥0}},{x,y}]

Show[Plot3D[-x y,{x,-0.5,1.5},{y,0,2},MeshFunctions->{#3&},RegionFunction->Function[{x,y},Norm[{2x-1,y-1}]≤1&&x≥0&&y≥0]],Graphics3D[{PointSize[0.04],Point[{x,y,-x y}/.res[[2]]]}]]

res =NMinimize[{-x y, {Norm[{2x-1,y-1}]≤1,x>=0,y≥0}},{x,y}, Method->"QuasiconvexBisection"]

res =NMinimize[{-x y, {Norm[{2x-1,y-1}]≤1,x≥0,y≥0}},{x,y}, Method->"QuasiconvexSubgradient"]

Difference of Convex

The objective and one of the constraint functions are not convex but can be represented by a difference of convex functions f(x,y)-g(x,y) where f and g are convex functions:

res=NMinimize[{(x^2)-(y^2),2≤Norm[{x,y}],-3<y<1},{x,y}]

res=NMinimize[{(x^2)-(y^2),2≤Norm[{x,y}],-3<y<1},{x,y}, Method->"DifferenceOfConvex"]

Show[Plot3D[(x^2)-(y^2),{x,-3,3},{y,-3,2},MeshFunctions->{#3&},RegionFunction->Function[{x,y},-3<y<1&&2≤Norm[{x,y}]]],Graphics3D[{PointSize[0.04],Point[{x,y,(x^2)-(y^2)}/.res[[2]]]}]]

Global optimization methods

Convex

Can just specify Method->“Convex” in NMinimize (for convex problems)
Can also give a specific convex (or transformable to convex) method depending on the problem.

Method->Except[“Convex”] 
Will not use convex or transformable to convex methods.

External libraries:

Grid[{{"","LP","QP","SOCP","SDP","EXP","POW","MIP"},
{"CLP","✓","✓","","","","",""},
{"CBC","✓","","","","","","✓"},{"OSQP","✓","✓","","","","",""},{"Gurobi","✓","✓","✓","","","","✓"},{"Xpress","✓","✓","✓","","","","✓"},{"CSDP","✓","✓","✓","✓","","",""},{"DSDP","✓","✓","✓","✓","","",""},{"SCS","✓","✓","✓","✓","✓","✓",""},{"MOSEK","✓","✓","✓","✓","✓","✓","(SuperStar[✓])"}}, Frame->All]

(*) Except mixed-integer SDP.

Additional convex methods:

LinearOptimization: Simplex, RevisedSimplex, InteriorPoint

QuadraticOptimization: EqualityConstrainedQuadratic, ActiveSetQuadratic and ADMM (arbitrary precision)

SecondOrderConeOptimization: PolyhedralApproximation, FischerBrumeister

SemidefiniteOptimization: PolyhedralApproximation, FischerBrumeister

ConicOptimization: IPOPT(customized for conic)

Mixed-integer Conic: OuterApproximation, ConvexMixedIntegerBranchAndBound

Transformable to Convex

GeometricOptimization

QuasiconvexBisection, QuasiconvexSubgradient

DifferenceofConvex

Non-convex

Heuristic methods: aim to find a global minimum, but may end up returning a local minimum

Nelder-Mead: (cheap, not truly global) 
The Nelder–Mead method is a direct search method. For a function of n variables, the algorithm maintains a set of n+1 points forming the vertices of a polytope in n-dimensional space. At each iteration, a new point is then generated to replace the worst point.

Simulated Annealing: (medium difficulty, backup for Nelder-Mead)
Simulated annealing is a simple stochastic function minimizer. The default number of starting points, given by the option SearchPoints, is min(2 n,50), where n is the number of variables, and an optimum point is found starting from every search point.

Differential Evolution: (more expensive and more robust)
Differential evolution is a simple stochastic function minimizer. The algorithm maintains a population of m points, where typically m≫n, with n being the number of variables. During each iteration of the algorithm, a new population of m points is generated.

RandomSearch (more intuitive, do-it-yourself method)
The random search algorithm works by generating a population of random starting points and uses a local optimization method from each of the starting points. 
Set:  Method(FindMinimum, IPOPT), SearchPoints (# of initial points) or InitialPoints(the points)

Couenne (V13.2+) (Convex Over and Under ENvelopes for Nonlinear Estimation) is a branch&bound algorithm to solve Mixed-Integer Nonlinear Programming (MINLP) problems of the form:

      min (Subscript[f, 0])(x,y)
             (Subscript[f, i])(x,y)≤0,i=1,2..., m
             x ∈ (R^n), y ∈ (Z^p)

where all (Subscript[f, i])(x,y) are, in general, nonlinear functions.

Couenne aims at finding global optima of nonconvex MINLPs. It implements linearization, bound reduction, and branching methods within a branch-and-bound framework.

Examples

1D real-valued non-convex problem

NMinimize[{-x Sin[x]+3 Cos[x]+x,-5<x<5},x]

Plot[-x Sin[x]+3 Cos[x]+x,{x,-5,5},Epilog->{PointSize[0.03],Point[{-2.74732,-6.5725}]}]

Now make an unbounded example with infinite number of local minimums

NMinimize[-x Sin[x]+3 Cos[x]+x,x]

Plot[-x Sin[x]+3 Cos[x]+x,{x,-50,50}]

Specifying a starting interval can help in achieving a better local minimum:

NMinimize[-x Sin[x]+3 Cos[x]+x,{x,-20,20}]

{#,NMinValue[-x Sin[x]+3 Cos[x]+x,x, Method->#]}&/@{Automatic,"NelderMead", "SimulatedAnnealing","DifferentialEvolution", "RandomSearch", "Couenne"}//TableForm

Method “Couenne” works harder on looking for a global minimum 
and doesn’t need a starting interval:

NMinimize[-x Sin[x]+3 Cos[x]+x,x, Method->"Couenne"]

2D real-valued non-convex problem

f[x_,y_]:=Sin[10 (x+y)]-(E^(Sin[5 x]))-Sin[6(E^y)]-Sin[7 Sin[x]]-            
   -Sin[Sin[8 y]]-(1/4)((x^2)+(y^2))

Plot3D[f[x,y],{x,y}∈Disk[]]

NMinimize[f[x,y],(x^2)+(y^2)<=1,{x,y}]

NMinimize[f[x,y],(x^2)+(y^2)<=1,{x, y},Method->"Couenne"]

{#,NMinValue[f[x,y],(x^2)+(y^2)<=1,{x, y},Method->#]}&/@{Automatic,"NelderMead", "SimulatedAnnealing","DifferentialEvolution", "RandomSearch", "Couenne"}//TableForm

NMinimize[f[x,y],(x^2)+(y^2)<=1,{x, y},Method -> {"RandomSearch", Method->"IPOPT","SearchPoints"->50}]

ipts=RandomPoint[Disk[],50];Show[plot=Plot3D[f[x,y],{x,y}∈Disk[], PlotRange->All,Mesh->None],Graphics3D[Point[Map[Append[#,0.25+f@@#]&,ipts]]]]

NMinimize[f[x,y],{x,y}∈Disk[], Method->{"RandomSearch",Method->"IPOPT","InitialPoints"->ipts}]

Mixed-integer SOC problem

Consider a point with integer-valued coordinates lying inside a 10-dimensional ball with center at {1,1,...,1} and radius 1. Minimize the sum of coordinates.

Graphics[{Green, Ball[{1,1}], Red, PointSize[Large],Point[{{0,1},{1,0}}], Blue, Point[{{1,1},{2,1},{1,2}}]}, Axes->True]

NMinimize[Total[x],{center == ConstantArray[1,10],Norm[x-center]≤1},x∈Vectors[10,Integers]]//AbsoluteTiming

Use method ”Couenne” to get the result faster:

NMinimize[Total[x],{center == ConstantArray[1,10],Norm[x-center]≤1},x∈Vectors[10,Integers], Method->"Couenne"]//AbsoluteTiming

Use a commercial solver to get the result faster:

NMinimize[Total[x],{center == ConstantArray[1,10],Norm[x-center]≤1},x∈Vectors[10,Integers], Method->"GUROBI"]//AbsoluteTiming

NMinimize[Total[x],{center == ConstantArray[1,10],Norm[x-center]≤1},x∈Vectors[10,Integers], Method->"MOSEK"]//AbsoluteTiming

NMinimize[Total[x],{center == ConstantArray[1,10],Norm[x-center]≤1},x∈Vectors[10,Integers], Method->"XPRESS"]//AbsoluteTiming

Max-Cut of a graph with Couenne

The Max-Cut problem is to determine a subset S of the vertices V of a graph G, for which the sum of the weights (Subscript[w,  i j]) of the edges that cross from S to its complement V \ S is maximized.
Let (Subscript[x, k])=1 for k∈S and (Subscript[x, k])=-1 for k∈V \ S. Then we need to solve an integer programming problem of maximizing (Underoverscript[(1/4)∑, (i,j=1), n])(Subscript[w, i j ])(1-(Subscript[x, i])(Subscript[x, j]))=(1/( 4))xᵀ·(W·(1, 1, …,1) - W)·x=1/4x.L.x 
where (Subscript[x, k])∈{-1, 1}, k=1,…, n

laplacianMatrix[G_?GraphQ]:=(DiagonalMatrix[Total[#,{1}]]-#)&[WeightedAdjacencyMatrix[G]];
maxCutDirect[G_?GraphQ]:=Module[{A=laplacianMatrix[G],x,n,maxval, maxpt},
n=Length[First[A]];
{maxval, maxpt}=NMaximize[{1/4x.A.x,Table[Indexed[x,i]^2==1,{i,1,n}]},x∈Vectors[n, Integers],Method->"Couenne"];
{Round[maxval], HighlightGraph[G,Pick[Range[n],maxpt[[1,2]],1]]}
]

G=RandomGraph[{50,80}]

maxCutDirect[G]

FindMaximumCut[G]

For bigger graphs can use an algorithm with a relaxed semidefinite problem described in the link below, using method CSDP or DSDP:
https://www.wolfram.com/language/12/convex-optimization/max-cut-problem.html
and used in the WL function FindMaximumCut.

Linear mixed-integer problem with Gurobi and Xpress

A total dominating set S is a subset of vertices in a connected graph G such that every vertex in G is adjacent to at least one member of S, 
see https://mathworld.wolfram.com/TotalDominatingSet.html

TotalDominatingSet[g_Graph,opts_:{}]:=Module[{n=VertexCount[g],v=VertexList[g],x,obj,cons1,cons2,sol},
obj=Total[x];
cons1 = x\[VectorGreaterEqual]0;(* 0\[VectorLessEqual]x\[VectorLessEqual]1 *)
cons2=VectorGreaterEqual[{AdjacencyMatrix[g].x,1}];
sol=LinearOptimization[obj,{cons1,cons2},Element[x,Vectors[n,Integers]],"PrimalMinimizerVector",opts];
 v[[Flatten[Position[sol,1]]]]]

GraphicsRow[{(Subscript[G, t4])=GraphData[{"Transposition",4}],(Subscript[G, t5])=GraphData[{"Transposition",5}]}]

{Length[set=TotalDominatingSet[(Subscript[G, t5])]],set}//Timing

{Length[set=TotalDominatingSet[(Subscript[G, t5]),Method->"Gurobi"]],set}//Timing

{Length[set=TotalDominatingSet[(Subscript[G, t5]),Method->"Xpress"]],set}//Timing

GeometricOptimization example with MOSEK

(RefLink[GeometricOptimization, paclet:ref/GeometricOptimization]) calls (RefLink[ConicOptimization, paclet:ref/ConicOptimization]) with linear and exponential cones.

Given an n×n matrix A with non-negative real entries, find a diagonal matrix D with positive entries that minimizes the sum of squares (the Frobenius norm squared) of the similar matrix D.A.(D^(-1)):

n=10;
A=BlockRandom[10^RandomReal[{-5,5},{n,n}], RandomSeeding->1234];

Let d={(Subscript[d, 1]),…,(Subscript[d, n])} be the diagonal entries of D. Since (Subscript[d, i]) is positive, the entries of (D^(-1)) are {1/(Subscript[d, 1]),…,1/(Subscript[d, n])}, so the entries of the product are (Subscript[(D.A.(D^(-1))), i j])=(Subscript[A, i j])((Subscript[d, i])/(Subscript[d, j])):

AbsoluteTiming[GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]},"PrimalMinimumValue"]]

Compare with the commercial solver MOSEK:

AbsoluteTiming[GeometricOptimization[Sum[((IndexedDefault[A, i, j])^2)(((IndexedDefault[d, i])^2)/((IndexedDefault[d, j])^2)), {i,1,n},{j,1,n}],{},{d∈Vectors[n]},"PrimalMinimumValue", Method->"MOSEK"]]

Mixed-integer non-linear problems (from MINLPLib)

https://www.minlplib.org/st_e40.html

Three-Bar Truss Problem 
https://ntrs.nasa.gov/api/citations/19890015846/downloads/19890015846.pdf

sol = NMinimize[2*i1+i2+1.4142135*i3,{i1>=1,i1<=12,i2>=1,i2<=12,i3>=1,i3<=12,(-0.15*i1*i2)-0.14142135*i2*i3-0.1319*i1*i3+x4==0,1.7317*i2+1.03366*i3-x4<=0,0.634*i1+2.828*i3-x4<=0,0.5*i1-2*i2-x4<=0,-0.5*i1+2*i2-x4<=0,(-1+i1)*(-2+i1)*(-3+i1)*(-5+i1)*(-8+i1)*(-10+i1)*(-12+i1)==0,(-1+i2)*(-2+i2)*(-3+i2)*(-5+i2)*(-8+i2)*(-10+i2)*(-12+i2)==0,(-1+i3)*(-2+i3)*(-3+i3)*(-5+i3)*(-8+i3)*(-10+i3)*(-12+i3)==0},{i1∈Integers,i2∈Integers,i3∈Integers,x4}, Method->"Couenne"]

Plug-in method

for (convex and non-convex) optimization functions:

The solver name method should be a string.  Once a solver is registered, it can be used in the Wolfram Language optimization functions with Method->method.

The following keys are considered in the Association assoc:

Further details

"ObjectiveSupport"

The value associated with "ObjectiveSupport" should be one of the following:

For “Nonlinear” one can specify “Nonlinear”->”Expression” or “Nonlinear”->”NumericalFunction”

If "ObjectiveSupport" is not specified, the support is assumed to be linear.

"ConstraintSupport"

The value associated with "ConstraintSupport" should be an association of rules ctype->stype, where ctype describes the constraint type and stype describes the support type.

The constraint type ctype can be any of the following:

The support type stype can be one of the following:

(RefLink[ConicOptimization, paclet:ref/ConicOptimization]) — minimize {c.x|(Subscript[a, j]).x+(Subscript[b, j])(Subscript[\[VectorGreaterEqual], (Subscript[κ, j])])0, j=1… k} 
this is equivalent to:     minimize {c.x|(Subscript[y, j])==(Subscript[a, j]).x+(Subscript[b, j]),  (Subscript[y, j])(Subscript[\[VectorGreaterEqual], (Subscript[𝒦, j])])0, j=1… k}

“SolveFunction”

The value sfun associated with the "SolveFunction" key is the main interface to the Wolfram Language convex optimization functions. When an optimization function is used with Method->method, then sfun[problemData,opts] is evaluated.

Evaluation of sfun[problemData,opts] should return a list, {status,methodData}.

The problemData Association is constructed by the Wolfram Language convex optimization functions to correspond to the problem:

The problem is described using the following keys:

The status should be one of:

When the status has a Head of Success, there should be definitions for the following solution properties:

The options that will be given to the solver function in  sfun[problemData, opts] may be any options that the solver uses as method options in addition to the options given to the Wolfram Language optimization function:

More details at:

https://reference.wolfram.com/language/OptimizationMethodFramework/tutorial/OptimizationMethodFramework.html

Example with method Gurobi

at https://github.com/WolframResearch/GurobiLink

Needs["Optimization`MethodFramework`"]

RegisterOptimizationMethod["Gurobi",
Association["SolveFunction"->GurobiSolve,
"ObjectiveSupport"->"Quadratic",
"ConstraintSupport"->Association[{"EqualityConstraint"->"Affine","NonNegativeCone"->"Affine","NormCone"->"Membership","QuadraticConstraint"->"Affine"}],"MixedIntegerSupport"->True,...]];

GurobiSolve[problemData_,pmopts___]:=...

Use the method “Gurobi” with any applicable optimization function:

NMinimize[{(x^2)+2(y^2),{x+y==1}},{x,y}, Method->"Gurobi"]

ConvexOptimization[(x^2)+2(y^2),{x+y==1},{x,y}, Method->"Gurobi"]

QuadraticOptimization[(x^2)+2(y^2),{x+y==1},{x,y}, Method->"Gurobi"]

Library Solvers

External libraries

COIN: (HyperlinkTemplate[CLP, https://github.com/coin-or/ClpNone, https://github.com/coin-or/Clp, HyperlinkActionRecycled, HyperlinkActive, , ]) (linear programming) and (HyperlinkTemplate[CBC, https://github.com/coin-or/Cbc/None, https://github.com/coin-or/Cbc/, HyperlinkActionRecycled, HyperlinkActive, , ]) (branch and cut)

Part of the COIN-OR project, CLP is a linear and quadratic programming solver and CBC is a mixed integer linear programming solver

IPOPT (Interior point optimizer)

Part of the COIN-OR project, IPOPT is a software package for large-scale nonlinear optimization

CSDP: A C Library for Semidefinite Programming.

Part of the COIN-OR project, uses a predictor-corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz. Implemented in C, can use multithreading and take advantage of sparsity in the constraint matrices.

DSDP: Software for Semidefinite Programming by S. J. Benson and Y. Ye.

Uses dual-scaling interior-point method for semidefinite programming, has low memory requirements and efficient low-rank and sparse data structures.

SCS: Splitting Conic Solver by B. O'Donoghue, E. Chu, N. Parikh and S. Boyd.

Using the alternating direction method of multipliers to solve large scale convex cone problems including LP, SOCP, SDP, exponential and power cone problems.

(HyperlinkTemplate[OSQP, https://osqp.orgNone, https://osqp.org, HyperlinkActionRecycled, HyperlinkActive, , ]):  An operator splitting solver for quadratic problems by Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, Stephen Boyd.

(HyperlinkTemplate[CVXPY, https://www.cvxpy.orgNone, https://www.cvxpy.org, HyperlinkActionRecycled, HyperlinkActive, , ]): A Python-embedded modeling language for convex optimization problems by  Steven Diamond and Stephen Boyd. 

It is distributed with the open source solvers ECOS, OSQP, and SCS. Many other solvers can be called by CVXPY, such as CBC, GLPK, GLPK_MI, CPLEX, NAG, GUROBI, MOSEK, CVXOPT, SCIP, XPRESS.

MOSEK: Commercial solver for large-scale sparse linear, quadratic and conic optimization problems by Erling D. Andersen.

In addition to real-valued conic problems MOSEK allows mixed-integer variables in combination with the linear, quadratic, exponential and power cones.

(HyperlinkTemplate[Gurobi, http://gurobi.comNone, http://gurobi.com, HyperlinkActionRecycled, HyperlinkActive, , ]): Commercial optimization solver for linear, quadratic, quadratically constrained quadratic and second order cone problems with real and mixed-integer variables by Zonghao Gu, Edward Rothberg and Robert Bixby.

(HyperlinkTemplate[Xpress, https://www.fico.com/en/products/fico-xpress-optimizationNone, http://gurobi.com, HyperlinkActionRecycled, HyperlinkActive, , ]): Commercial optimization solver for linear, quadratic, quadratically constrained quadratic and second order cone problems with real and mixed-integer variables by the Fair Isaac Corporation (FICO).

(HyperlinkTemplate[Couenne, https://github.com/coin-or/CouenneNone, https://github.com/coin-or/Couenne, HyperlinkActionRecycled, HyperlinkActive, , ]): (Convex Over and Under ENvelopes for Nonlinear Estimation) is a branch&bound algorithm to solve Mixed-Integer Nonlinear Programming (MINLP) problem, a COIN-OR project.

Conclusions

Wolfram Language global optimization provides a

easy to use and flexible function interface

strong modeling language

automatic problem classification and processing

a plug-in method framework to add solvers

a variety of convex and non-convex solvers

improvements in the Automatic method selection are in progress

Thank you!

Office Hours for the Numerics group - Friday (1-2 pm CDT)