Polytopesimplifier

• Coverage

class ConvexProgram(Aeq, beq, c, df, ddf, barrier)

Convex Program is given by min <c,x> + sum f_i(x_i) subject Ax = b, x_i in K_i given that such block K_i is a strictly convex set

A

constraint matrix A

ConvexProgram(Aeq, beq, c, df, ddf, barrier)

o = ConvexProgram(Aeq, beq, c, df, ddf, barrier) Output a ConvexProgram representing the linear program min <c,x> + sum f_i(x_i) subject Aeq x = beq, barrier(x) < inf

static LinearProgram(Aeq, beq, c, lb, ub)

o = LinearProgram(Aeq, beq, c, lb, ub) Output a ConvexProgram representing the linear program min <c,x> subject Aeq x = beq, lb <= x <= ub

b

constraint vector b

barrier

barrier for prod K_i

c

cost vector c

collapse(x, blocks)

Collapse the domain on the blocks to boundaries closest to x Return okay = 1 if the collapse is successful Return okay = 0 if the rows are not inconsistenc (infeasible).

ddf

second derivative of cost function

df

first derivative of cost function

distance(o, x, v)

t = o.distance(x) Output the distance of x with its closest boundary for each block Any negative entries implies infeasible

t = o.distance(x, v) Output the maximum step from x with direction v for each coordinate (The maximum step may not reach the boundary.)

export(o, x)

z = o.export(x) Output x in the original coordinate system

feasible

indicate if the domain is empty, [] means not determined

findInterior(o)

x = o.findInterior() Find an interior point of the convex set using analytic center return NaN if the set is empty

idx

original coordinates that x supported on

interior

some interior point we found

normalize(o)

x = o.normalize()

removeRedundantRows()

Remove redundant rows from Ax=b Return 1 if the removal is successful Return 0 if the rows are not inconsistenc (infeasible).

rescale()

Rescale rows to improve numerical stability

rowReorder()

Reorder rows to speed up sparse cholesky

scale

scale of x.

scale2

scale.^2

solver

Linear system solver used to solve (A W A’)^-1

x0

We represent any z in the domain implicitly by x as follows: z = x0; z(idx) += scale.*x;

class TwoSidedBarrier(lb, ub, vdim)

The log barrier for the domain {lu <= x <= ub}: phi(x) = - sum log(x - lb) - sum log(ub - x).

TwoSidedBarrier(lb, ub, vdim)

o.update(lb, ub) Update the bounds lb and ub.

boundary(o, x)

[A, b] = o.boundary(x) Output the normal at the boundary around x for each barrier. Assume: only 1 vector is given

boundary_distance(o, x)

v = o.boundary_distance(x) Output the distance of x with its closest boundary for each coordinate

center

Some feasible point x

extraHessian

Extra factor added when computing Hessian. Used to handle free constraints.

feasible(o, x)

r = o.feasible(x) Output if x is feasible.

freeIdx

Indices that ub == Inf and lb == -Inf

gradient(o, x)

g = o.gradient(x) Output gradient phi(x).

hessian(o, x)

g = o.hessian(x) Output Hessian phi(x).

hessian_norm(o, x, d)

v = o.hessian_norm(x, d) Output d_i (hess phi(x))_ii d_i for each i

lb

lb

logdet_gradient(o, x)

v = o.logdet_gradient(x) Output the gradient of log det (hess phi(x)) which is (hess phi(x))^-1 (grad hess phi (x))

lowerIdx

Indices that ub == Inf

n

Number of variables

quadratic_form_gradient(o, x, u)

v = o.quadratic_form_gradient(x, u) Output the -grad of u’ (hess phi(x)) u.

set_bound(lb, ub)

Update the bounds lb and ub.

set_vdim(o, vdim)

o.set_bound(lb, ub) Update the dimension dim.

step_size(o, x, v)

t = o.stepsize(x, v) Output the maximum step size from x with direction v.

tensor(o, x)

g = o.tensor(x) Output the third derivative of phi(x).

ub

ub

upperIdx

Indices that lb == -Inf

vdim

Each point is stored along the dimension vdim

analyticCenter(f, x, opts)

Compute the analytic center of the domain {Ax = b} intersected with the domain of f

USAGE:

[x, info] = analyticCenter (f, x, opts)

INPUTS:

f – a ConvexProgram object describing the feasible domain, with fields:

• .feasible - logical flag, false if the problem is infeasible

• .solver - linear-system solver object (factorize/solve)

• .A - constraint matrix of the equality system A x = b

• .b - right-hand side of the equality system A x = b

• .barrier - self-concordant barrier for the domain

• .c - linear objective coefficient vector (may be empty)

• .df - handle to the gradient of the nonlinear objective (may be empty)

• .scale - scaling applied to the exported gradient of the objective

• .idx - index mapping into the exported (original) space

• .scale2 - scaling applied to the exported Hessian of the objective

OPTIONAL INPUTS:

• x – feasible initial point; a heuristic point is used if omitted or infeasible

• opts – structure of options with fields:

  • .MaxIter - maximum number of iterations

  • .Output - handle used to print progress (e.g. @disp)

  • .CentralityTol - centrality stopping tolerance on the scaled residual

  • .FeasibilityTol - feasibility stopping tolerance on ||A x - b||_inf

  • .CollapseDistanceTol - distance below which a block is assumed tight

  • .SolverIter - number of iterations used to solve the linear systems

  • .VectorType - numeric class for x (@double, @ddouble, @qdouble)

OUTPUTS:

• x – the analytic center of f, or empty if the problem is infeasible

• info – structure with fields centrality, feasibility, iter and hess

Note

f is a handle object and is modified in place as collapsed subspaces are discovered.

configPolytopeSimplifier()

Configure the MATLAB path for the PolytopeSimplifier and load its CMatrix modules

USAGE:

configPolytopeSimplifier()

demo

Demo script showing how to find an interior point and normalize a linear program with the PolytopeSimplifier ConvexProgram interface

lewisCenter(f, x, opts)

Compute the Lewis-weight center of the domain {Ax = b} intersected with the domain of f

USAGE:

[x, info] = lewisCenter (f, x, opts)

INPUTS:

• f – a ConvexProgram object describing the feasible domain, with fields:

  • .A - constraint matrix of the equality system A x = b

  • .b - right-hand side of the equality system A x = b

  • .solver - linear-system solver object (factorize/solve/leverageScore)

  • .feasible - logical flag, set false on numerical failure

  • .barrier - self-concordant barrier for the domain

  • .c - linear objective coefficient vector (may be empty)

  • .df - handle to the gradient of the nonlinear objective (may be empty)

  • .scale - scaling applied to the exported gradient of the objective

  • .idx - index mapping into the exported (original) space

  • .scale2 - scaling applied to the exported Hessian of the objective

• x – a feasible initial point (required)

OPTIONAL INPUTS:

opts – structure of options with fields:

• .MaxIter - maximum number of iterations

• .Output - handle used to print progress (e.g. @disp)

• .CentralityTol - centrality stopping tolerance on the scaled residual

• .FeasibilityTol - feasibility stopping tolerance on ||A x - b||_inf

• .JLDim - number of dimensions used to estimate the leverage score

• .p - exponent parameter for the lp Lewis weight

OUTPUTS:

• x – the Lewis-weight center of f, or empty on numerical failure

• info – structure with fields centrality, feasibility, iter and hess

standardize_problem(P)

Validate a polytope problem structure and fill in its missing standard fields

USAGE:

P = standardize_problem (P)

INPUTS:

P – polytope problem structure. Fields read or completed:

• .Aeq - equality constraint matrix (Aeq x = beq)

• .beq - equality constraint right-hand side

• .Aineq - inequality constraint matrix (Aineq x <= bineq)

• .bineq - inequality constraint right-hand side

• .lb - lower bounds on the variables

• .ub - upper bounds on the variables

• .center - initial interior point (required if unconstrained)

• .f - handle to the objective function (optional)

• .df - gradient of the objective, vector or function handle (optional)

• .ddf - Hessian of the objective, vector or function handle (optional)

OUTPUTS:

P – the standardized problem structure with all fields populated