sparseLP

computeMutualCoherence(A)[source]

Computes mutual coherence

Usage

result = computeMutualCoherence(A)

Input

  • A – input matrix

Output

  • result – mutual coherence
evalObj(x, theta, pNeg, pPos, epsilonP, alpha, approximation)[source]

Computes the value of the sparseLP objective function

obj = evalObj(x,theta,pNeg,pPos,epsilonP,alpha,approximation);

Inputs

  • x – current solution vector

  • theta, pNeg, pPos, epsilonP, alpha –

    parameters of the approximations

  • approximation – appoximation type of zero-norm. Available approximations:

    • ‘cappedL1’ : Capped-L1 norm
    • ‘exp’ : Exponential function
    • ‘log’ : Logarithmic function
    • ‘SCAD’ : SCAD function
    • ‘lp-‘ : L_p norm with p < 0
    • ‘lp+’ : L_p norm with 0 < p < 1
    • ‘l1’ : L1 norm

Output

  • obj – Current value of the objective function
% .. Author: - Hoai Minh Le, 20/10/2015
Ronan Fleming, 2017
optimizeCardinality(problem, param)[source]

DC programming for solving the cardinality optimization problem The l0 norm is approximated by a capped-l1 function. :math:`min c’(x, y, z) + lambda_0*||k.*x||_0 - delta_0*||d.*y||_0

  • lambda_1*||x||_1 + delta_1*||y||_1`

s.t. \(A*(x, y, z) <= b\) \(l <= (x,y,z) <= u\) \(x in R^p, y in R^q, z in R^r\)

Usage

solution = optimizeCardinality(problem, param)

Input

  • problem – Structure containing the following fields describing the problem:
    • .p - size of vector x OR a size(A,2) x 1 boolean indicating columns of A corresponding to x.
    • .q - size of vector y OR a size(A,2) x 1 boolean indicating columns of A corresponding to y.
    • .r - size of vector z OR a `size(A,2) x 1`boolean indicating columns of A corresponding to z.
    • .A - s x size(A,2) LHS matrix
    • .b - s x 1 RHS vector
    • .csense - s x 1 Constraint senses, a string containing the constraint sense for each row in A (‘E’, equality, ‘G’ greater than, ‘L’ less than).
    • .lb - size(A,2) x 1 Lower bound vector
    • .ub - size(A,2) x 1 Upper bound vector
    • .c - size(A,2) x 1 linear objective function vector

Optional inputs

  • problem – Structure containing the following fields describing the problem: * .osense - Objective sense for problem.c only (1 means minimise (default), -1 means maximise) * .k - p x 1 IR size(A,2) x 1 strictly positive weight vector on minimise ||x||_0 * .d - q x 1 OR size(A,2) x 1 strictly positive weight vector on maximise ||y||_0 * .lambda0 - trade-off parameter on minimise ||x||_0 * .lambda1 - trade-off parameter on minimise ||x||_1 * .delta0 - trade-off parameter on maximise ||y||_0 * .delta1 - trade-off parameter on maximise `||y||_1

  • param – Parameters structure: * .printLevel - greater than zero to recieve more output * .nbMaxIteration - stopping criteria - number maximal of iteration (Default value = 100) * .epsilon - stopping criteria - (Defautl value = 10e-6) * .theta - parameter of the approximation (Default value = 2)

    For a sufficiently large parameter , the Capped-L1 approximate problem and the original cardinality optimisation problem are have the same set of optimal solutions

Output

  • solution – Structure containing the following fields:
    • .x - p x 1 solution vector
    • .y - q x 1 solution vector
    • .z - r x 1 solution vector
    • .stat - status
      • 1 = Solution found
      • 2 = Unbounded
      • 0 = Infeasible
      • -1= Invalid input

Optional output

  • solution – Structure may also contain the following field: * .xyz - ‘size(A,2) x 1` solution vector, where model.p,q,r are ‘size(A,2) x 1` boolean vectors and

    x=solution.xyz(problem.p); y=solution.xyz(problem.q); z=solution.xyz(problem.r);

sparseLP(model, approximation, params)[source]

DC programming for solving the sparse LP \(min ||x||_0\) subject to linear constraints See Le Thi et al., DC approximation approaches for sparse optimization, European Journal of Operational Research, 2014; http://dx.doi.org/10.1016/j.ejor.2014.11.031

Usage

[solution, nIterations, bestApprox] = sparseLP(model, approximation, params);

Input

  • model – Structure containing the following fields describing the linear constraints:
    • .A - m x n LHS matrix
    • .b - m x 1 RHS vector
    • .lb - n x 1 Lower bound vector
    • .ub - n x 1 Upper bound vector
    • .csense - m x 1 Constraint senses, a string containting the model sense for each row in A (‘E’, equality, ‘G’ greater than, ‘L’ less than).

Optional input

  • approximation – appoximation type of zero-norm. Available approximations:
    • ‘cappedL1’ : Capped-L1 norm
    • ‘exp’ : Exponential function
    • ‘log’ : Logarithmic function
    • ‘SCAD’ : SCAD function
    • ‘lp-‘ : L_p norm with p < 0
    • ‘lp+’ : L_p norm with 0 < p < 1
    • ‘l1’ : L1 norm
    • ‘all’ : try all approximations and return the best result

Optional input

  • params – Parameters structure:
    • .nbMaxIteration - stopping criteria - number maximal of iteration (Defaut value = 1000)
    • .epsilon - stopping criteria - (Defaut value = 10e-6)
    • .theta - parameter of the approximation (Defaut value = 0.5)

Output

  • solution – Structure containing the following fields:
    • .x - n x 1 solution vector
    • .stat - status:
      • 1 = Solution found
      • 2 = Unbounded
      • 0 = Infeasible
      • -1= Invalid input

nIterations: Number of iterations bestApprox: Best approximation

updateObj(x, theta, pNeg, pPos, epsilonP, alpha, approximation)[source]

Update the linear objective - variables (x,t)

c = updateObj(x,theta,pNeg,pPos,epsilonP,alpha,approximation);

Inputs

  • x – current solution vector

  • theta, pNeg, pPos, epsilonP, alpha –

    parameters of the approximations

  • approximation – appoximation type of zero-norm. Available approximations:

    • ‘cappedL1’ : Capped-L1 norm
    • ‘exp’ : Exponential function
    • ‘log’ : Logarithmic function
    • ‘SCAD’ : SCAD function
    • ‘lp-‘ : L_p norm with p < 0
    • ‘lp+’ : L_p norm with 0 < p < 1
    • ‘l1’ : L1 norm

Output

  • c – New objective function
% .. Author: - Hoai Minh Le, 20/10/2015
Ronan Fleming, 2017