cutnorm package

Submodules

cutnorm.OptManiMulitBallGBB module

The algorithm belongs to Zaiwen Wen and Wotao Yin who authored ‘A feasible method for optimizationwith orthogonality constraints’.

We have simply reinterpreted the algorithm from Matlab to Python.

cutnorm.OptManiMulitBallGBB.cutnorm_quad(V, C)

Cutnorm function to compute objective function value and gradient

Parameters:
  • V – ndarray, Low rank model X = V’ * V;
  • C – ndarray, Objective matrix to compute maxcut
Returns:

(f, g)

f: float, objective funciton value

g: ndarray, gradient
cutnorm.OptManiMulitBallGBB.maxcut_quad(V, C)

Maxcut function to compute objective function value and gradient

maxcut SDP: X is n by n matrix max Tr(C*X), s.t., X_ii = 1, X psd

Parameters:
  • V – ndarray, Low rank model X = V’ * V;
  • C – ndarray, Objective matrix to compute maxcut
Returns:

(f, g)

f: float, objective funciton value

g: ndarray, gradient
cutnorm.OptManiMulitBallGBB.opt_mani_mulit_ball_gbb(x, fun, args, xtol=1e-06, ftol=1e-12, gtol=1e-06, rho=0.0001, eta=0.1, gamma=0.85, tau=0.001, nt=5, mxitr=1000, record=0)

Line search algorithm for optimization on manifold Reinterpreted directly from Zaiwen Wen and Wotao Yin’s Matlab implementation of their paper on ‘A feasible method for optimizationwith orthogonality constraints’

Parameters:
  • x – Numpy array where each column lies on the unit sphere ||x_i||_2 = 1
  • fun – Function that returns the objective function value and its gradient. Params: [x, args] Returns: [f, g]
  • args – args to be used in fun
  • kwargs – Options record = 0, no print out mxitr max number of iterations xtol stop control for ||X_k - X_{k-1}|| gtol stop control for the projected gradient ftol stop control for abs(F_k - F_{k-1})/(1+|F_{k-1}|) usually, max{xtol, gtol} > ftol
Returns:

(x, g, out)

x: solution

g: gradient of x

Out: output information

cutnorm.compute module

cutnorm.compute.compute_cutnorm(A, B, w1=None, w2=None, max_round_iter=100, logn_lowrank=False, extra_info=False)

Computes the cutnorm of the differences between the two matrices

Parameters:
  • A – ndarray, (n, n) matrix
  • B – ndarray, (m, m) matrix
  • w1 – ndarray, (n, 1) array of weights for A
  • w2 – ndarray, (m, 1) array of weights for B
  • max_round_iter – int, number of iterations for gaussian rounding
  • logn_lowrank – boolean to toggle log2(n) low rank approximation
  • extra_info – boolean, generate extra computational information
Returns:

(cutnorm_round, cutnorm_sdp, info)

cutnorm_round: objective function value from gaussian rounding

cutnorm_sdp: objective function value from sdp solution

info: dictionary containing computational information
Computational information from OptManiMulitBallGBB:

sdp_augm_n: dimension of augmented matrix sdp_relax_rank_p: rank sdp_tsolve: computation time sdp_itr, sdp_nfe, sdp_feasi, sdp_nrmG: information from OptManiMulitBallGBB

Computational information from gaussian rounding:

round_tsolve: computation time for rounding round_approx_list: list of rounded objf values round_uis_list: list of uis round_vjs_list: list of vjs round_uis_opt: optimum uis round_vjs_opt: optimum vjs

Computational information from processing the difference:

weight_of_C: weight vector of C, the difference matrix

Cutnorm information:

cutnorm_sets (S,T): vectors of cutnorm
Raises:

ValueError – if A and B are of wrong dimension, or if weight vectors does not match the corresponding A and B matrices
cutnorm.compute.cutnorm_sets(uis, vjs)

Generates the cutnorm sets from the rounded SDP solutions

Parameters:
  • uis – ndarray, (n+1, ) shaped array of rounded +- 1 solution
  • vis – ndarray, (n+1, ) shaped array of rounded +- 1 solution
Returns:

(S, T) Reconstructed S and T sets that are {1, 0}^n

S: Cutnorm set axis = 0

T: Cutnorm set axis = 1
cutnorm.compute.gaussian_round(U, V, C, max_round_iter, logn_lowrank=False, extra_info=False)

Gaussian Rounding for Cutnorm

The algorithm picks a random standard multivariate gaussian vector w in R^p and computes the rounded solution based on sgn(w dot ui).

Adopted from David Koslicki’s cutnorm rounding code https://github.com/dkoslicki/CutNorm and Peter Diao’s modifications

Parameters:
  • U – ndarray, (p, n) shaped matrices of relaxed solutions
  • V – ndarray, (p, n) shaped matrices of relaxed solutions
  • C – ndarray, original (n, n) shaped matrix to compute cutnorm
  • max_round_iter – maximum number of rounding operations
  • logn_lowrank – boolean to toggle log2(n) low rank approximation
  • extra_info – boolean, generate extra computational information
Returns:

(approx_opt, uis_opt, vjs_opt, round_info)

approx_opt: approximated objective function value

uis_opt: rounded u vector

vis_opt: rounded v vector

round_info: information for rounding operation

Module contents