indirect method for least-squares with inequality constraints

Question

I aim to find $x \in \mathbb{R}^n$ that

$\min_x |D \cdot F \cdot x|^2$

subject to $x_i = X_i$ and $x_j \geq X_j$ ,

$i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets.

it is easy to do $D \cdot F \cdot x$ because D is diagonal and F is the discrete Fourier transform. But actually storing and computing on F is not practical.

MATLAB's lsqlin works for small cases. It looks like it uses a direct method, qpsub, if the problem has a mix of equality and inequality constraints.

Are there any solvers or quick implementations you could refer me to?

Answer 1

Iterative methods for bound-constrained least squares problems exist; one example I found pretty quickly was On Iterative Algorithms for Linear Least Squares Problems With Bound Constraints by Bierlaire, Toint, and Tuyttens.

You should still be able to use MATLAB's lsqlin by supplying some options to the function. To use an iterative algorithm, prior to calling lsqlin, set the options struct using

options = optimoptions(@lsqlin, 'Algorithm', 'trust-region-reflective', ...
                       'JacobMult', YourMatrixFreeObjectiveFunction)
% Your lsqlin call should look something like...
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)

Consult the lsqlin documentation for more details.

You'll need to alter your problem slightly in order to use the trust region algorithm; the trust region reflective algorithm does not allow any equalities, so you'll have to simply set $x_{i} = X_{i}$ for $i \in I$ within your objective function, and only solve for $x_{j}$ such that $j \in J$.