I have been trying to solve a least squares problem of the following form:

$$ \begin{equation} \min_{\vec{x}} \frac{1}{2} \lVert f(\vec{x}) - f_{\text{target}} \rVert_{2}^2 + \alpha\Big( \frac{1-\rho}{2} \lVert \vec{x} - \vec{x}_{\text{orig}} \rVert_{2}^{2} + \rho \lVert \vec{x} - \vec{x}_{\text{orig}} \rVert_{1} \Big), \end{equation} $$

where $f$ is a continuous function $ f: \mathbb{R}^{N} \to \mathbb{R}^{K}$ and $\vec{x} \in \mathbb{R}^{N}$. The first term in the objective function above is hence minimizing the distance between the vector $f(\vec{x})$ and a given vector $f_{\text{target}}$. The next two terms are regularization terms ($\lvert \cdot \rvert_{1,2}$ are the $L_{1}$ and $L_{2}$ norms respectively) . $\vec{x}_{\text{orig}}$ is the starting vector.

I have been able to get a solution in a fairly quick time by using the scipy.optimize function with SLSQP solver. However, the addition of linear constraints seems to not work. The constraints are of the form

$$ \begin{align} l_{1} &\leq \sum_{i \in I_{1}} x_{i} \leq u_{1} \\ l_{2} &\leq \sum_{i \in I_{2}} x_{i} \leq u_{2} \\ &\vdots \\ l_{n} &\leq \sum_{i \in I_{n}} x_{i} \leq u_{n} \\ \end{align} $$

where $I_{m}$ are partitions of $\{1 \cdots n \}$. So the constraints are on the sums of the elements of the vector $\vec{x}$.

I have attempted to integrate these constraints within the function call optimize through the constraints list.

def fun_upper_constraint(x, indices, ub):
    return ub - np.sum(x[indices])

def fun_lower_constraint(x, indices, lb):
    return np.sum(x[indices]) - lb

def generate_constraint_dict(indices, ub, lb):
    return {"type": "ineq", "fun": fun_upper_constraint, "args": (indices, ub)}, {
        "type": "ineq",
        "fun": fun_lower_constraint,
        "args": (indices, lb),

Adding constraints this way causes the optimizer to not find the optimum with the status message Positive directional derivative for linesearch. Hence, I wonder whether there is a way to encode these constraints in a way that is compatible with what the SLSQP solver expects.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy