Skip to content

min_l1_with_fixed

min_l1_with_fixed(G=None, Q=None, L=None, c=None, k=None, y=None, A=None, b=None, d=1, verbose=False, params=None, solver=None)

Solve a problem of the form argmin_u |Gu|{d,1} + 0.5 u.T Q u + c.T u s.t. u[k]= y A u = b where |x|{d,1} is the norm which takes the l2 norm of every d adjacent entries before summing them.

e.g. |x|{1,1} is the familiar l1 norm (the default for this function); |x|{n,1} is the (unsquared) l2 norm of x.

Parameters:

Name Type Description Default
G (m*d, n) sparse scipy csr_array

Matrix to be multiplied inside the norm. Defaults to sp.eye(n), where n is inferred from another input.

None
Q (n, n) sparse scipy csr_array

Quadratic form matrix. 0 if not specified.

None
L (?, n) sparse scipy csr_array

Prefactorization of Q; do not provide Q when providing L. May make the solve faster when using MOSEK, but slower when using SCS.
Q is factored if L is not specified (when using MOSEK).

None
c (n,) numpy array

Linear term in the objective. 0 if not specified.

None
k (f,) numpy array

Indices for fixed parts of u.

None
y (f,) numpy array

Values for fixed parts of u.

None
A (l, n) numpy array

Linear constraint matrix.

None
b (l, 1) numpy array

Linear constraint vector.

None
d int

Number of adjacent vector entries in Gu to take vector norm of before summing. 1 if not specified (corresponds to the standard l1 norm of Gu). Solver uses second-order conic constraints for the L1 term if d != 1.

1
verbose

Whether to print solver progress and solution status. False if not specified.

False
params

Other arguments provided to the solver, may be useful for e.g. setting tolerances.

For MOSEK, the input should be a list, where each entry should be a tuple of strings, e.g. ("MSK_DPAR_INTPNT_CO_TOL_REL_GAP", "1.0e-7"). See https://docs.mosek.com/latest/pythonapi/parameters.html for all of the parameter choices. Empty list by default.

For SCS, the input should be a dictionary containing parameter names (strings) and values (type may vary). See https://www.cvxgrp.org/scs/api/settings.html for all of the parameter choices.
The SCS defaults are mostly as in their documentation, except that we use defaults eps_abs = 1e-9, eps_rel = 1e-9, eps_infeas = 1e-9.

None
solver

Solver type to use; "mosek", "scs", or None (default).

MOSEK requires users to install the Python module and download a license file; licenses are generally free for academic use and paid for commercial use; see mosek.com for more details. SCS is free and exists under an MIT license.

Select "None" (the default) to first try MOSEK, and then fall back to SCS if the license is invalid in some way.

None

Returns:

Name Type Description
u (n,) numpy array

Solution to the optimization problem, if optimal.

See Also

min_quad_with_fixed for solving a quadratic optimization problem while restricting certain degrees of freedom. fixed_dof_solve for solving a linear system while restricting certain degrees of freedom.

Examples:

>>> import gpytoolbox as gpy
>>> import numpy as np
>>> import scipy as sp
>>> A = np.array([[1, 2]])
>>> b = np.array([[1]])
>>> u = gpy.min_l1_with_fixed(A=A, b=b)  # corresponds to argmin |u|_1 s.t. Au == b
>>> u
array([-0.        ,  0.5])
>>> A @ u[:, None]  # check that the linear constraint is satisfied
array([[1.]])
Source code in src/gpytoolbox/min_l1_with_fixed.py
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def min_l1_with_fixed(G=None, Q=None, L=None, c=None, k=None, y=None, A=None, b=None, d=1, verbose=False, params=None, solver=None):
    """
    Solve a problem of the form 
       argmin_u |Gu|_{d,1} + 0.5 u.T Q u + c.T u
           s.t. u[k]= y
                A u = b
    where |x|_{d,1} is the norm which takes the l2 norm of every d adjacent entries before summing them.

    e.g. |x|_{1,1} is the familiar l1 norm (the default for this function); |x|_{n,1} is the (unsquared) l2 norm of x.         


    Parameters
    ----------
    G : (m*d, n) sparse scipy csr_array, optional
        Matrix to be multiplied inside the norm.  Defaults to sp.eye(n), where n is inferred from another input.
    Q : (n, n) sparse scipy csr_array, optional
        Quadratic form matrix. 0 if not specified.
    L : (?, n) sparse scipy csr_array, optional
        Prefactorization of Q; do not provide Q when providing L.  May make the solve faster when using MOSEK, but slower when using SCS.  
        Q is factored if L is not specified (when using MOSEK).
    c : (n,) numpy array, optional
        Linear term in the objective.  0 if not specified.
    k : (f,) numpy array, optional
        Indices for fixed parts of u.
    y : (f,) numpy array, optional
        Values for fixed parts of u.
    A : (l, n) numpy array, optional
        Linear constraint matrix.
    b : (l, 1) numpy array, optional
        Linear constraint vector.
    d : int, optional
        Number of adjacent vector entries in Gu to take vector norm of before summing.  1 if not specified (corresponds to the standard l1 norm of Gu).
        Solver uses second-order conic constraints for the L1 term if d != 1.
    verbose: string, optional
        Whether to print solver progress and solution status.  False if not specified.
    params: list or dict, optional
        Other arguments provided to the solver, may be useful for e.g. setting tolerances.  

        For MOSEK, the input should be a list, where each entry should be a tuple of strings, e.g. ("MSK_DPAR_INTPNT_CO_TOL_REL_GAP", "1.0e-7").
        See https://docs.mosek.com/latest/pythonapi/parameters.html for all of the parameter choices.  Empty list by default.

        For SCS, the input should be a dictionary containing parameter names (strings) and values (type may vary).
        See https://www.cvxgrp.org/scs/api/settings.html for all of the parameter choices.  
        The SCS defaults are mostly as in their documentation, except that we use defaults `eps_abs = 1e-9`, `eps_rel = 1e-9`, `eps_infeas = 1e-9`.
    solver: None or string, optional
        Solver type to use; "mosek", "scs", or None (default).  

        MOSEK requires users to install the Python module and download a license file; licenses are generally free for academic use and paid for commercial use; see mosek.com for more details.
        SCS is free and exists under an MIT license.

        Select "None" (the default) to first try MOSEK, and then fall back to SCS if the license is invalid in some way.


    Returns
    -------
    u : (n,) numpy array
        Solution to the optimization problem, if optimal.

    See Also
    --------
    `min_quad_with_fixed` for solving a quadratic optimization problem while restricting certain degrees of freedom.
    `fixed_dof_solve` for solving a linear system while restricting certain degrees of freedom.

    Examples
    --------
    ```python
    >>> import gpytoolbox as gpy
    >>> import numpy as np
    >>> import scipy as sp
    >>> A = np.array([[1, 2]])
    >>> b = np.array([[1]])
    >>> u = gpy.min_l1_with_fixed(A=A, b=b)  # corresponds to argmin |u|_1 s.t. Au == b
    >>> u
    array([-0.        ,  0.5])
    >>> A @ u[:, None]  # check that the linear constraint is satisfied
    array([[1.]])
    ```

    """
    if solver is None:
        # try to use mosek; except any license-related failure and continue with SCS instead
        try:
            globals()["mosek"] = __import__("mosek")
            return min_l1_with_fixed(G, Q, L, c, k, y, A, b, d, verbose, params, solver="mosek")
        except ModuleNotFoundError as e:
            if verbose:
                print("MOSEK Python module not found.")
                print("Continuing with SCS...")
            return min_l1_with_fixed(G, Q, L, c, k, y, A, b, d, verbose, params, solver="scs")
        except mosek.Error as e:
            # all mosek errors related to licensing problems
            license_error_list = {mosek.rescode.err_license, 
                mosek.rescode.err_license_expired,
                mosek.rescode.err_license_version,
                mosek.rescode.err_license_old_server_version,
                mosek.rescode.err_size_license,
                mosek.rescode.err_prob_license,
                mosek.rescode.err_file_license,
                mosek.rescode.err_missing_license_file,
                mosek.rescode.err_size_license_con,
                mosek.rescode.err_size_license_var,
                mosek.rescode.err_size_license_intvar,
                mosek.rescode.err_optimizer_license,
                mosek.rescode.err_flexlm,
                mosek.rescode.err_license_server,
                mosek.rescode.err_license_max,
                mosek.rescode.err_license_moseklm_daemon,
                mosek.rescode.err_license_feature,
                mosek.rescode.err_platform_not_licensed,
                mosek.rescode.err_license_cannot_allocate,
                mosek.rescode.err_license_cannot_connect,
                mosek.rescode.err_license_invalid_hostid,
                mosek.rescode.err_license_server_version,
                mosek.rescode.err_license_no_server_support}
            if e.errno in license_error_list:
                if verbose:
                    print("MOSEK license error: " + str(e.errno))
                    print("Continuing with SCS...")
                return min_l1_with_fixed(G, Q, L, c, k, y, A, b, d, verbose, params, solver="scs")
            else:
                raise e
    elif solver == "mosek":
        globals()["mosek"] = __import__("mosek")
        return _min_l1_with_fixed_mosek(G=G, Q=Q, L=L, c=c, k=k, y=y, A=A, b=b, d=d, verbose=verbose, mosek_params=[] if params is None else params)
    elif solver == "scs":
        scs_params = dict(eps_abs=1e-9, eps_rel=1e-9, eps_infeas=1e-9)
        if not (params is None):
            scs_params.update(params)
        return _min_l1_with_fixed_scs(G=G, Q=Q, L=L, c=c, k=k, y=y, A=A, b=b, d=d, verbose=verbose, scs_params=scs_params)
    else:
        raise ValueError("Solver " + str(solver) + " not supported.")