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)

x = analyticCenter(f, opts, x) compute the analytic center for the domain {Ax=b} intersect the domain of f

Input

• f - a ConvexProgram

• x - a feasible initial point (optional)

• opts - a structure for options with the following properties (optional) – MaxIter - maximum number of iterations Output - maximum number of iterations CentralityTol, FeasibilityTol - stop the following are satisfied

  ||(A’ * lambda - grad f(x)) / sqrt(hess)||_inf < CentralityTol ||A x - b||_inf < FeasibilityTol

  CollapseDistanceTol -

  if x_i is CollapseDistanceTol close to some boundary, we assume the block i is tight.

  SolverIter - the number of iteration in solving linear systems VectorType - the class we use for x (@double, @ddouble, @qdouble)

Output

• x - It outputs the analytic center of f

• info - a structure containing centrality, feasibility and iter.

• f - the problem f will be modified as we discover collapsed subspace

demo

it outputs NaN if the problem is infeasible.

lewisCenter(f, x, opts)

x = LewisCenter(f, opts, x) compute the analytic center for the domain {Ax=b} intersect the domain of f

Input

• f - a ConvexProgram

• x - a feasible initial point

• opts - a structure for options with the following properties (optional) – MaxIter - maximum number of iterations Output - maximum number of iterations CentralityTol, FeasibilityTol - stop the following are satisfied

  ||(A’ * lambda - grad f(x)) / sqrt(hess)||_inf < CentralityTol ||A x - b||_inf < FeasibilityTol

  p - the parameter for lp Lewis weight JLDim - the number of dimensions used in estimating leverage score

Output

• x - It outputs the analytic center of f

• info - a structure containing centrality, feasibility and iter.