cutnorm package¶
Subpackages¶
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