Convex Optimization

Rob Knapp, Wolfram Research

Join the Conversation #WolframTechConf

Initialization

Needs["Notation`"]

Notation[(NotationTemplateTag[a_≺b_]) ⟺ (NotationTemplateTag[ConeLess[a_,b_]])];
Notation[(NotationTemplateTag[a_⪯b_]) ⟺ (NotationTemplateTag[ConeLessEqual[a_,b_]])];
Notation[(NotationTemplateTag[a_⋚b_]) ⟺ (NotationTemplateTag[ConeEqual[a_,b_]])];
Notation[(NotationTemplateTag[a_≻b_]) ⟺ (NotationTemplateTag[ConeGreater[a_,b_]])];
Notation[(NotationTemplateTag[a_⪰b_]) ⟺ (NotationTemplateTag[ConeGreaterEqual[a_,b_]])];

Notation[(NotationTemplateTag[a_(Subscript[≺, k_])b_]) ⟺ (NotationTemplateTag[ConeLess[a_,b_,k_]])];
Notation[(NotationTemplateTag[a_(Subscript[⪯, k_])b_]) ⟺ (NotationTemplateTag[ConeLessEqual[a_,b_,k_]])];
Notation[(NotationTemplateTag[a_(Subscript[⋚, k_])b_]) ⟺ (NotationTemplateTag[ConeEqual[a_,b_,k_]])];
Notation[(NotationTemplateTag[a_(Subscript[≻, k_])b_]) ⟺ (NotationTemplateTag[ConeGreater[a_,b_,k_]])];
Notation[(NotationTemplateTag[a_(Subscript[⪰, k_])b_]) ⟺ (NotationTemplateTag[ConeGreaterEqual[a_,b_,k_]])];

$ContextPath = Prepend[$ContextPath, "Optimization`"];

Convex sets and functions

A set C is affine if for x,y in C then θ x+(1-θ) y is also in C

A set C is convex if the above holds with θ≥0.

A function f is convex if f(θ x + (1-θ)y) ≤ θ f(x) + (1-θ)f(y) for θ≥0 and all x,y in the domain of f.

The epigraph of a function is the set {x,t} such that x is in the domain of f and f(x)≤ t

A big thing

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 convex optimization problem if (Subscript[f, i])(x) are convex and (Subscript[h, j])(x) are affine ((Subscript[h, j])(x) = (Subscript[a, j]).x+(Subscript[b, j]))

For a convex optimization problem, a local minimum is also a global minimum!

Note the problem has the equivalent expression:

minimize       t

subject to   (Subscript[f, 0])(x)-t≤ 0
(Subscript[f, i])(x)≤ 0, i = 1,...m
(Subscript[a, j]).x+(Subscript[b, j])=0, j=1,...p

So both the objective function and any equality constraints are linear.

It’s all about cones!

Import["C:\\Users\\rknapp\\Workspace\\RD_HTML_RKnapp\\Talks\\TechConference2017\\Coneheads.jpg"]

Convex Proper Cones

A cone is a set κ such that if x∈κ, θ x∈κ θ≥ 0.

A convex cone is a cone that also satisfies (Subscript[θ, 1])(Subscript[x, 1])+(Subscript[θ, 2])(Subscript[x, 2])∈κ  for (Subscript[θ, 1])≥ 0,(Subscript[θ, 2])≥ 0.

A proper cone has nonempty interior and is pointed (x∈κ and -x∈k ⟺x=0)

RegionPlot3D[Sqrt[x^2+y^2]≤ z,{x,-1,1},{y,-1,1},{z,0,1}, Mesh->None,PlotPoints->50]

RegionPlot3D[Sqrt[x^2]≤ z,{x,-1,1},{y,-1,1},{z,0,1}, Mesh->None,PlotPoints->50]

Some common cones

({{      , NonNegativeCone[n], ,  x∈(ℝ^n) such that (Subscript[x, i])≥0}, {      , NormCone[n], , {t,x}∈ℝ×(ℝ^n) such that Norm[x]≤t }, {      , SemidefiniteCone[n], , symmetric positive definite n×n matrices}, {      , ExponentialCone[], , {x,y,z}∈(ℝ^3) such that y (e^((x/y)))≤z}, {      , PowerCone[α], , {x,y,z}∈(ℝ^3) such that (x^α)(y^(1-α))≥z,x≥0,y≥0}})

Generalized Inequalities

Let κ be a proper cone.  Then one can define a partial order based on κ:

x(Subscript[⪯, k])y ⟺y-x∈κ

x(Subscript[⪰, k])y ⟺x-y∈κ

FullForm[{x(Subscript[⪯, k])y, x(Subscript[⪰, k])y }]

Two really frequent and distinguishable cases can be given without the cone:

Vectors of length n: NonNegativeCone[n]
n×n matrices: SemidefiniteCone[n]

These evaluate if x and y are numerical:

rx = RandomReal[1,{100}];

rx⪰0

Zero is a special case -- normally requires consistent vector on both sides

rx⪰0.1

mx = KroneckerProduct[rx,rx];

mx⪰0

Min[Eigenvalues[mx]]

PositiveSemidefiniteMatrixQ[mx]

Conic Optimization

minimize c.x

subject to  (Subscript[a, 1]).x+(Subscript[b, 1])(Subscript[⪰, (Subscript[κ, 1])])0
...
(Subscript[a, n]).x + (Subscript[b, n])(Subscript[⪰, (Subscript[κ, n])])0
(Subscript[a, 0]).x+(Subscript[b, 0])=0

Where  (Subscript[κ, 1]),...,(Subscript[κ, n]) are proper cones, x is a vector of length n, (Subscript[a, i]) are (Subscript[m, i])×n matrices, and (Subscript[b, i]) are vectors of length (Subscript[m, i])

Linear optimization (programming) is a special case of this:

minimize c.x

subject to (Subscript[a, 1]).x+(Subscript[b, 1])⪰0
(Subscript[a, 0]).x+(Subscript[b, 0])=0

The cone is the non-negative cone.

Another way to express the conic problem is

minimize c.x

subject to (Subscript[a, 1]).x+(Subscript[b, 1])∈(Subscript[κ, 1])
...
(Subscript[a, n]).x+(Subscript[b, n])∈(Subscript[κ, n])
(Subscript[a, 0]).x+(Subscript[b, 0])=0

Cone Transformation

Consider the set of x∈(R^n) such that a.x+b∈κ (or a.x (Subscript[⪰, κ])-b) for some cone κ.

In our development framework (for lack of a better name) we are denoting a canonical form of this by ConeTransformation[κ, {a, b}]

({{      , NonNegativeCone[n], ,  x∈(ℝ^n) such that (Subscript[x, i])≥0}})

a = {{1,0},{0,1},{-1,-2}};b = {0,0,2};set = ConeTransformation[NonNegativeCone[3], {a, b}];

p1 = RegionPlot[{x,y}∈set,{x,0,2},{y,0,1},PlotStyle->Opacity[.5],AspectRatio->Automatic]

This is equivalent to

a.{x,y}+b⪰ 0

RegionPlot[a.{x,y}+b⪰0,{x,0,2},{y,0,1},AspectRatio->Automatic]

ConicOptimization function

ConicOptimization[c,{(Subscript[t, 1]),...,(Subscript[t, n])}] minimizes c.x over all x that satisfy x∈(Subscript[t, i]), i=1,...,n

c = -{1,1};

xmin = ConicOptimization[c,set]

Show[p1,Graphics[{Red,PointSize[.025],Point[xmin]}]]

Another ConeTransformation example

({{      , NormCone[n], , {t,x}∈ℝ×(ℝ^n) such that Norm[x]≤t }})

disk = ConeTransformation[NormCone[3],{{{0,0},{1,0},{0,1}}, {1,0,0}}];

p2 = RegionPlot[{x,y}∈disk,{x,-1,1},{y,-1,1},PlotStyle->Opacity[.5]]

ConicOptimization[c,disk]

The 2-norm cone can be used for a lot of different sets:

Grid[Table[rc = ConeTransformation[NormCone[3],{RandomReal[1,{3,3}], {1,0,0}}];
RegionPlot3D[{x,y,z}∈rc,{x,-10,10},{y,-10,10},{z,-10,10}],{4},{4}]]

A more thrilling ConicOptimization problem

xmin = ConicOptimization[c,{set,disk}]

Manipulate[xmin = ConicOptimization[-c,{set,disk}];Show[p1,p2,Graphics[{Red,PointSize[0.025],Point[xmin]}]],{{c,{1,1}},Locator}]

Convex Modeling

Constructing the right ConeTransformation (or cone inequalities) can be complicated and is quite error prone.  It is much more natural to expression problems using combinations of set inclusion and inequalities.

ConicOptimizationProblem[c,{set,disk},{x,y}]

InputForm[%]

ConvexMinimize

There is a prototype function, 
ConvexMinimize[f,constraints,vars] 
that tries to convert a convex optimization problem into a conic optimization problem to minimize f over the given constraints.

ConvexMinimize[-x-y,{x+2 y≤ 2,y≥ 0, x≥ 0, Norm[{x,y}]≤1},{x,y}]

ConvexMinimize[-x-y,{x+2 y≤ 2,y≥ 0, x≥ 0, Inactive[Norm][{x,y}]≤1},{x,y}]

Why are the results different?

omp = MinimizationProblem[-x-y,{x+2 y≤ 2,y≥ 0, x≥ 0, Norm[{x,y}]≤1},{x,y}]

top = TransformProblem[omp]

The quadratic constraint (x^2)+(y^2)-1≤ 0 is converted to the second order cone constraint using the observation that

Expand[{x,y,(s-t)/2}.{x,y,(s-t)/2}-((s+t)/2)^2]

With s=t=1

d4 = ConeTransformation[NormCone[4],{{{0,0},{0,0},{1.`,0},{0,1.`}},{1.`,0.`,0.`,0.`}}];

It is equivalent to the unit disk

RegionPlot[{x,y}∈d4,{x,-1,1},{y,-1,1}]

Convex Modeling

Semidefinite Example

Find the vector x={(Subscript[x, 1]),(Subscript[x, 2])} that minimizes the maximum singular value of a(x)=(Subscript[a, 0]) + (Subscript[a, 1])(Subscript[x, 1])+(Subscript[a, 2])(Subscript[x, 2]) for given n×n matrices (Subscript[a, i]).  This can be expressed as a semidefinite problem as follows:The idea is to minimize t such that t I⪰a(x) and t I⪰-a(x)

minimize t

such that (t^2)I-(a^t).a⪰0 
(where I is the identity matrix)

The constraint can be expressed in the form (({{t I, a}, {a, t I}}))⪰0 
using Schur complements,
 (({{A, B}, {C, D}}))⪰0⟺A-B (D^(-1))C⪰0

Clear[a];
n = 2;
k = 2;
a[0] = IdentityMatrix[2];
a[1] = {{1,0},{0,-1}};
a[2] = {{2,5},{5,8}};
aX = a[0] + Sum[a[i] Indexed[x,i],{i,k}];
tI = t IdentityMatrix[n];

{σmin, rules} = ConvexMinimize[t,(({{tI, aX}, {(aX^\[Transpose]), tI}}))⪰0,{t,Element[x,Vectors[k]]}]

f[x_?NumberQ,y_?NumberQ] := Module[{v = SingularValueList[a[0]+x a[1] + y a[2]]},Max[v]];Show[Plot3D[f[x,y],{x,-1,1},{y,-.5,.25}],Graphics3D[{Red,PointSize[.047],Point[Flatten[{x,t} /. rules]]}]]

Bigger case

Clear[a];
n = 4;
k = 7;
a[0] = IdentityMatrix[n];
Do[a[i]=RandomReal[1,{n,n}],{i,k}];
aX = a[0] + Sum[a[i] Indexed[x,i],{i,k}];
tI = t IdentityMatrix[n];

{σmin, rules} = ConvexMinimize[t,
(({{tI, aX}, {(aX^\[Transpose]), tI}}))⪰0,
{t,Element[x,Vectors[k]]}]

Convex Modeling

Geometric Optimization Example

Find the dimensions of a box that maximizes the volume

op = MinimizationProblem[1/(d*h*w), {w/2 ≤ h≤ 2 w, w/2 ≤ d ≤ 2 w, h ≥ 0, w ≥ 0, d≥ 0, h*w+h*d≤ 1/2, w*d ≤ 1},{h,w,d}]

top = TransformProblem[op,"LinearConic"]

top["SolveProblem"]

Convex Modeling

A fitting example

Find a fit to data with constraints on the coefficients

Clear[x,y,z,s,t];
SeedRandom[1234];
basis = Table[ChebyshevT[k,s],{k,3}];
sc = Subdivide[-1.,1.,47];
tc = (basis.{1,1/2,1/3} /. s->xc) + RandomReal[1,Length[sc]];
lp=ListPlot[data = Transpose[{sc,tc}]]

a = DesignMatrix[data, basis,{s},IncludeConstantBasis->False];

l1 = ConvexMinimize[Inactive[Norm][a.{x,y,z}-tc,1],{},{x,y,z}∈]

l2 = ConvexMinimize[Norm[a.{x,y,z}-tc,2],{},{x,y,z}∈]

l∞ = ConvexMinimize[Norm[a.{x,y,z}-tc,∞],{},{x,y,z}∈]

Show[lp,Plot[Evaluate[{x,y,z}.basis /. Part[{l1,l2,l∞},All,2]],{s,-1,1}]]

Summary

Optimization over convex sets provides a framework that brings potentially difficult problems into reach.

There are other convex optimization frameworks existing today, e.g. YALMIP, CVX, but the Wolfram Language provides an ideal platform to do the symbolic operations needed to transform problems to be accessible by efficient solvers.

We are working on a multilevel approach that will allow knowledgeable people to specify input very efficiently and compactly while at the same time providing a set of transformations that makes more basic and intuitive specification of problems possible.

Some new functions coming your way

LinearFractionalOptimization (((α.x + β)/(γ.x + δ)) with linear constraints)

QuadraticOptimization ((1/2)x.q.x+c.x with linear constraints)

SecondOrderConeOptimization (linear objective with NormCone and linear constraints)

SemidefiniteOptimization (linear objective with semidefinite constraints)

ConicOptimization

Functions that will be modified to try to automatically use the convex framework:

NMinimize

FindMinimum

FindFit (convex constraints, regularized fitting)