Methods for Constrained Local and Global Optimization

Nina Dokeva, Wolfram Research

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

ABSTRACT

Constrained optimization algorithms have been under active development in recent years with many open source and commercial library solvers emerging for convex, non-convex, local and global optimization.

This talk will cover the Wolfram Language numerical optimization functions for constrained local and global optimization, how they classify and process the inputs into the form required by different solvers and the available solvers that can be called through the method option.

Overview of the talk

This talk will discuss

constrained numerical optimization in the Wolfram Language

new features

problem classification and processing

method framework and solvers

examples

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

New in 12.3 and 13

New features in (RefLink[NMinimize, paclet:ref/NMinimize]), (RefLink[FindMinimum, paclet:ref/FindMinimum]) and (RefLink[ConvexOptimization, paclet:ref/ConvexOptimization])

Methods for problem classes that are non-convex,
but can be transformed to use convex solvers

Quasiconvex optimization — new in 12.3

Difference of Convex optimization — new in 13

More library solvers

XpressLink (for convex up to second order cone)

In progress: working on adding non-linear, non-convex library solvers for constrained local and global optimization

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}]

What problem are we solving?

Processing and classification

Linear

Convex (Conic)

Transformable to convex

Non-linear (non-convex)

Function to use

Convex problem — use any of (RefLink[ConvexOptimization, paclet:ref/ConvexOptimization]), (RefLink[FindMinimum, paclet:ref/FindMinimum]), (RefLink[NMinimize, paclet:ref/NMinimize]), or a specific convex optimization function

Transformable to convex — use (RefLink[FindMinimum, paclet:ref/FindMinimum]) | (RefLink[NMinimize, paclet:ref/NMinimize])

Non-linear, non-convex — use (RefLink[FindMinimum, paclet:ref/FindMinimum]) | (RefLink[NMinimize, paclet:ref/NMinimize])
Big, Smooth, Need only local solution: Try (RefLink[FindMinimum, paclet:ref/FindMinimum])  first 
Small, Non-smooth, Need global solution: Try (RefLink[NMinimize, paclet:ref/NMinimize]) first

Examples

Example 1 — Convex

All 3 functions perform similarly for convex problems

n=100000;
ConvexOptimization[Total[x],Norm[x]<=1,x∈Vectors[n],"PrimalMinimumValue"]//AbsoluteTiming

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

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

Example 2 — Transformable to convex

FindMinimum[{(x^2)+(y^2),x+2y==2,(x^2)-(y^2)<1},{x,y}]

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

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

ConvexOptimization[(x^2)+(y^2),{x+2y==2,(x^2)-(y^2)<1},{x,y}]

Method "Convex" in (RefLink[NMinimize, paclet:ref/NMinimize]) includes “transformable to convex” methods.

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

Example 3 — Small vs big non-convex

For non-convex problems (RefLink[FindMinimum, paclet:ref/FindMinimum]) is generally faster than  (RefLink[NMinimize, paclet:ref/NMinimize])

Plot[x Sin[x]+x,{x,-10,10}]

Small problem:

FindMinimum[{x Sin[x]+x,x>-10},x]//AbsoluteTiming

NMinimize[{x Sin[x]+x,x>-10},x]//AbsoluteTiming

Bigger problem:

FindMinimum[{x Sin[x]+x,Table[x>-i,{i,10000}]},x]//AbsoluteTiming

NMinimize[{x Sin[x]+x,Table[x>-i, {i,10000}]},x]//AbsoluteTiming

Example 4 — Non-convex & non-smooth

Sometimes (RefLink[NMinimize, paclet:ref/NMinimize]) is the best (or only) option

Small, non-convex, non-smooth problem:

Plot[Abs[x^2-3],{x,-1,4}]

Not convex:

ConvexOptimization[Abs[(x^2)-3],-1≤x≤4,{x}]

Could not be converted to convex:

FindMinimum[{Abs[(x^2)-3],-1≤x≤4},{x}, Method->Convex]

Not smooth:

FindMinimum[{Abs[(x^2)-3],-1≤x≤4},{x}]

(RefLink[NMinimize, paclet:ref/NMinimize]) is happy to solve it:

NMinimize[{Abs[(x^2)-3],0≤x≤4},{x}]

Methods for Convex Optimization

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 methods

LinearOptimization: Simplex, RevisedSimplex, InteriorPoint

QuadraticOptimization: EqualityConstrainedQuadratic, ActiveSetQuadratic and ADMM (for arbitrary precision)

SecondOrderConeOptimization: PolyhedralApproximation

SemidefiniteOptimization: PolyhedralApproximation

ConicOptimization: IPOPT(customized for conic)

Mixed-integer Conic: Outer Approximation, ConvexMixedIntegerBranchAndBound

Examples with Convex solvers

Total dominating set -- linear mixed-integer problem with Xpress and Gurobi

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]]]]]

TranspositionGraph[n_]:=Module[{cg=UndirectedGraph[CayleyGraph[PermutationGroup[Cycles[{#}]&/@Subsets[Range[n],{2}]]]]},Graph[Range[n!],EdgeList[cg]]]
GraphicsRow[{TranspositionGraph[4],TranspositionGraph[5]}]

{Length[set=TotalDominatingSet[TranspositionGraph[5]]],set}//Timing

{Length[set=TotalDominatingSet[TranspositionGraph[5],Method->Xpress]],set}//Timing

{Length[set=TotalDominatingSet[TranspositionGraph[5],Method->Gurobi]],set}//Timing

Power cones example with method MOSEK

A problem with a 1000 PowerCone constraints:

n=1000;{a,b}=BlockRandom[{RandomReal[{-1,1},{n,n}],Range[n]},RandomSeeding->123];

Method MOSEK is quite fast:

ConvexOptimization[Norm[ap.x-bp,1.5],{ap==a,bp==b},{x},"PrimalMinimumValue",Method->MOSEK]//AbsoluteTiming

Check the constraints after it was transformed to a conic problem:

constraints=ConvexOptimization[Norm[ap.x-bp,1.5],{ap==a,bp==b},{x},"Constraints",Method->MOSEK];

Length[constraints]

constraints[[2]]

Solve with the Automatic method, which in this case uses {SCS,Tolerance -> 10^-6}:

ConvexOptimization[Norm[ap.x-bp,1.5],{ap==a,bp==b},{x},"PrimalMinimumValue"]//AbsoluteTiming

ConvexOptimization[Norm[ap.x-bp,1.5],{ap==a,bp==b},{x},"PrimalMinimumValue", MaxIterations->10000]//AbsoluteTiming

Solve using the default tolerance for SCS, which is 10^-3:

ConvexOptimization[Norm[ap.x-bp,1.5],{ap==a,bp==b},{x},"PrimalMinimumValue", Method->{SCS, Tolerance->10^-3}]//AbsoluteTiming

Methods for Transformable to Convex

GeometricOptimization

QuasiconvexBisection, QuasiconvexSubgradient

DifferenceofConvex

Examples

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]]]}]]

Methods for Constrained Local Optimization

There are a number of methods for unconstrained local optimization (“Gradient”, “ConjugateGradient”, “QuasiNewton”, “Newton”,  “LevenbergMarquardt”) but only the following also work with constrained local optimization:

InteriorPoint

IPOPT (machine precision only) - new in version 11

Convex (or give a specific convex or transformable to convex method) - new in version 12

Example with FindMinimum

{FindMinimum[{(x^2) + (y^2),(((x-1))^2)+2(((y-1))^2) > 5},{x,y}, Method->#],#}&/@{Automatic, "IPOPT", "InteriorPoint", "Convex"}

ConvexOptimization[(x^2) + (y^2),(((x-1))^2)+2(((y-1))^2) > 5,{x,y}]

Plot3D[5-(((x-1))^2)-2(((y-1))^2),{x,-10,10},{y,-10,10}]

The constraint function is concave!

So what is the Automatic method here?

FindMinimum[{(x^2) + (y^2),(((x-1))^2)+2(((y-1))^2) > 5},{x,y}, Method->"DifferenceOfConvex"]

Methods for Constrained Global Optimization

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. At each iteration, a new point, (Subscript[x, new]), is generated in the neighborhood of the current search point, x.

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)

Convex (for convex problems)
Can also specify a specific convex (or transformable to convex) method depending on the problem.

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

Future plans: add general non-convex, non-linear global optimization solvers like Couenne (open-source) and possibly commercial solvers.

Example with NMinimize

f[x_,y_]:= x Sin[10x] y ^2Cos[5y]

Plot3D[f[x,y],{x,y}∈Disk[{-1,-1}], PlotRange->All]

{#, NMinValue[f[x,y], {x,y}∈Disk[{-1,-1}], Method->#]}&/@{Automatic,"NelderMead", "SimulatedAnnealing","DifferentialEvolution", "RandomSearch"}//TableForm

NMinValue[f[x,y],{x,y}∈Disk[{-1,-1}], Method->{"RandomSearch",  Method->"IPOPT"}]

NMinValue[f[x,y],{x,y}∈Disk[{-1,-1}], Method->{"RandomSearch",  Method->"IPOPT", "SearchPoints"->#}]&/@{5,10,20}

ipts=RandomPoint[Disk[{-1,-1}],20];

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

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

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:

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___]:=...

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

Conclusions

Wolfram Language optimization functions provide a

strong modeling language

easy to use function interface

automatic problem classification and processing

a plug-in method framework to add solvers

a large variety of solvers

Future improvements are in progress!

Thank you!

Next Talk: Paritosh Mokhasi - “Beyond Convex for Global Optimization”  (3pm CDT)
Office Hours for the Numerics group - Thursday (9-10am CDT)