Enforce condition in lsqnoneg

I working on inverse problem which is rank deficient and for that i am using tikhonov regularization , for minization i am using lsqnoneg to resolve it which is giving me good result but now i have to enforce a condition in each iteration of minimzation of lsqnoneg, however lsqnoneg oterations are automatic i cant control it manually althohg i used fmincon but it is not giving me the same results can some one help what algorithm should i use so that i can enforce my conditon during optimization iterations and it gives results like lsqnoneg,

Tikh_Output.IA_recovered_line_1 = lsqnonneg(Combined_Coeff_Matrix,Combined_projection_line_1);

Tikh_Output.IA_recovered_line_2 = lsqnonneg(Combined_Coeff_Matrix,Combined_projection_line_2);

here is my code

[Torsten]

The conditions you can enforce must be realizable within the mathematical description of the problems you can solve with the different MATLAB solvers. Since we don't know your condition, we cannot tell which solver is adequate.

[sanjay]

I want apply condition that in every iteration the lsqnoneg recover my x it is bascially a 1601x1 matrix , it checks if any value between 1 to 1600 is less than 1601th pixel , if yes then it should make it equal to 1601th values,i also used options = optimset('OutputFcn', @enforce_Condition); this option to call the condition but unfortunately in matlab lsqnoeng doesnot support it

[Torsten]

Shouldn't this be equivalent to imposing the 1600 conditions

x(1) >= x(1601)
x(2) >= x(1601)
...
x(1600) >= x(1601)

?

[sanjay]

yes but i dont want apply this condition after i recovered all my values from lsqnoneg but i want to apply this condition during each iteration of lsqnoneg could you please help

[John D'Errico]

If the problem is singular though, the solution is not unique. So that fmincon does not give the same results as lsqnonneg is meaningless, because that is fully expected.

[sanjay]

Then what should i do to enforce condition during optimization which solver i should use?

[Torsten]

Use "lsqlin", set "lb" to zeros(1601,1) to ensure non-negativity of the solution and implement the condition from above by setting A and b in A*x <= b appropriately.

[sanjay]

This is how i have applied but results are not fine also it converges too early

A = [eye(1600), -ones(1600,1)];

b = zeros(1600, 1);

lb = zeros(1601, 1);

x0 = zeros(1601, 1);

[x, resnorm, residual, exitflag, output] = lsqlin(Combined_Coeff_Matrix, Combined_projection_line_1, ...

A, b, [], [], lb, [], x0);

[Torsten]

Your matrix A is incorrect ; the conditions you set would be

x(1) <= x(1601)
x(2) <= x(1601)
...
x(1600) <= x(1601)

[sanjay]

Then how should I put the A values so that i satisfies my conditon in which i want to check during each optimization operation that if from 1 to 1600 any of the vlaue is less than 1601th value then it shoud assign that variable the value of 1601 otherwise it should not do anything

[Torsten]

A = [-eye(1600), ones(1600,1)];

[sanjay]

This not giving me specific reuslts, can you tell this constraint checks the condtion on each iteration of optimization when x recovers?

[Torsten]

At least the solution should satisfy the constraints. It is the case for all optimization algorithms that constraints can be violated during the computational process (except for bound constraints, I guess). You should at least supply an initial guess x0 that satisfies the constraints if this is that important for you.

What do you mean by "This not giving me specific reuslts" ? Do you mean "satisfactory results" ?

[sanjay]

Satisfactory results mean the task i want from this is to check the recovered value of my solution in each iteration should check whether my values from 1 to 1600 are less than the alst value of my solution if yes then it should assign them the vlaue of 1601th to then otherwise leave then as it is. this in not happening in this case

[Torsten]

I know what "satisfactory results" mean, but you wrote "specific reuslts" that I couldn't understand.

Including the contraint A*x <= b should produce a solution that satisfies x(1) >= x(1601),...,x(1600) >= x(1601). Usually the way how you arrive at this solution (directly or by checking in each iteration) is irrelevant. But for some reason that I don't understand this doesn't seem to be the case here.

There is no optimization tool in which you can directly change optimization variables depending on some conditions during the optimization process. You can only change constraints or the objective function. If you want to do this, you have to use "fmincon" - the problem description for "lsqlin" is fixed right from the beginning and cannot be altered during the computational process.

[sanjay]

Okay i explain what i am trying to do, i am working on an inverse problem and i have create my coefficent matrix and measurement using this i am trying to recover my X, i am successfull in doing so using lsqnoneg, but i have been given a task that i have to apply this condition in each optimization iteration to chek if some of the vlaues recovered in each iteration of optimization falls below the last value of the solution then make it equal to last value otherwise leave it as it is? do you think this constraint based approach is doing so or i should use fmincon

[Torsten]

As I said: You can't change solution variables during the optimization process in MATLAB optimizers. The changes must be initiated by your definition of the objective function or by the definition of your constraints. So neither "lsqlin" or "fmincon" can help you in this respect.

But if you want the optimal solution that satisfies x(1) >= x(1601), ... , x(1600) >= x(1601), then the constraint-based solution with "lsqlin" should be correct in my opinion (althogh the result you get might not be as expected).

Do you get the same results with lsqnonneg and lsqlin if you work without the A*x <= b constraint and only set the lower bounds vector lb to zeros(1601,1) ?

[sanjay]

Yes i tried without constraint then the reconstruction results are coming same in lsqin and lsqnoneg,

Answer 1

[Matt J]

Suppose your original problem is,

Rewrite the problem by making the change of variables x=Q*z where z>=0 and

Q=eye(1601); Q(:,end)=1;

Then the problem becomes,

which you can solve with lsqnonneg. After solving for z, you can retrieve x with x=Q*z.

[sanjay]

Hi i am sorry i am not understanding it ? how can i use this in lsqnoneg there no ption for constraint , are you talking about constraint here x=Q*z ? can you explore or tell me in more easy way

[Torsten]

@sanjay

This is a more elegant formulation of your problem that doesn't need constraints and can directly use "lsqnonneg", but will most probably not change the result.

[sanjay]

I tried this method its working but can you let me know why it will not change the result

[Torsten]

I tried this method its working but can you let me know why it will not change the result

Because the underlying mathematical problem is the same. The only difference is how it is formulated for the solver.

If you get different results if you solve

min: ||C*x-d||

under the constraints

A*x <= b
x >=0

with lsqlin and

min: ||C*Q*z-d||

with lsqnonneg and compute x from

x = Q*z

after getting the solution for z, then C is most probably rank-deficient, but at least ||C*x-d|| and ||C*Q*z-d|| from the two computations should be the same.

[sanjay]

Yes my C is basically rank deficient but my question is it enforcing the conditon during my optimization ? is it checking every everytime whether x recovering in iteration is greater than or equal to last value of x? because that is what is want

[Matt J]

but my question is it enforcing the conditon during my optimization ?

When optimizing over z with lsqnonneg, the only condition being enforced is z>=0.

However, for any z>=0, you can readily verify that x=Q*z will satisfy your desired boundary conditions on x. The converse is also true. Starting with any x satisfying the boundary conditions, we can construct a corresponding z>0 by doing,

which is in fact the same as z=Q\x;

[Torsten]

is it checking every everytime whether x recovering in iteration is greater than or equal to last value of x?

Your inputs to "lsqlin" or "lsqnonneg" are constant (C,A,b,lb,ub) and don't change during the solution process. So it is completely irrelevant if your constraints will be violated or not during the computation.

If you could interfere in the solution process and change the inputs depending on an intermediate result, things would be different.

[sanjay]

Then what about the Q we multiplied with z, is it not enforcing the condition , here in whole discussion is it happening that my X solution vlaues are checked whether these values are greateter than or equal to last vlaue of my X in each optimization stage? as i got the result in which all those values which were less than last value of X have been replace with last vlaue of X , but i need to is it applying thr condition after recovering all the vlaues of X or is it applying during optimization

[Torsten]

You tell the solver that you want to find an X that minimizes ||C*X-d||, and the solution vector X should not be arbitrary, but satisfy that all components of X should be greater or equal than the last component, and the solver computes such an X. This is solved as an integrated problem - thus the condition is not applied after recovering x(1),...,x(1600), but during the optimization because the value of x(1601) influences ||C*X-d||. Or is the last column of C a zero column ?

[Matt J]

Then what about the Q we multiplied with z, is it not enforcing the condition

Yes. Again, for any z>=0, the x obtained by doing x=Q*z will satisfy your desired boundary condition.

Conversely also, for any x satisfying your boundary condition, the corresponding z=Q\x will satisfy z>=0. They are in a 1-1 relationship.

[sanjay]

No my C is coeeficeint matrix and d is my measurements and i am applying this to recover my X, but now i wanted to apply the condition that during each iteration of optimization although this condition can be applied after recovering all the x , it checks whether my x vlaues are greater than or equal to zero but as there was not way to put direct condition during lsqnoeng function so i asked this question and you proposed this solution which is giving me fine results but wanted to confrim that this solution is checking my relavent condition during optimization ,

[Torsten]

now i wanted to apply the condition that during each iteration of optimization although this condition can be applied after recovering all the x , it checks whether my x vlaues are greater than or equal to zero

??? Greater or equal zero ? I thought greater or equal x(1601) ?

[sanjay]

yes >= 6101

[Matt J]

@sanjay, please indicate whether your comments are directed to me or to Torsten (or somebody else).

Regarding what is is happening during optimization: when lsqnonneg is used to optimize over z, it generates a sequence of iteration vectors z_i, i=0,1,2,... which, because of the particulars of lsqnonneg's algorithm, all satisfy z_i>=0 throughout the optimization. lsqnonneg does not know about x at all or do any manipulations in the space of x.

However, as we have discussed, since the sequence generated by lsqnnnoneg satisfies z_i>=0, then you could create a corresponding sequence x_i=Q*z_i which would satisfy your desired boundary conditions for all x_i.

Also, for the purposes of optimization, it is irrelevant whether your constraints are satisfied at every iteration of the optimization (even if in this case they are). As long as the z_i converges to an optimal solution for z (which it does), then the x_i will converge to an optimal solution for x, because the two problems are in a 1-1 relationship.

[Torsten]

@Matt J

It seems to me that @sanjay gets x(i) = x(1601) for all 1<=i<=1600 as solution, and now he/she suspects that this is set after the optimization is terminated. Of course, this is not the case.

[sanjay]

Yes @Matt J you are right i have the suspect that whether my condition is being checked during optimization or after optimization as i have very little knowlede about these optimization techniques , i am sorry for the incoveneince i am creating, but as x = Qz is calcualted after reovering z so i am afraid this condition is checked after the end of all optimization happend can you please clear me

[Matt J]

@sanjay

The condition z>=0 is checked throughout the optimization by the lsqnonneg algorithm. The condition on x is never "checked", but we know in advance that if z>=0, the appropriate condition on x will be satisfied both during and after the optimization.

[sanjay]

@Matt J thank you , could please let me know where my condition on X is exactly cheked, when we multiply C with Q then is it happening here in CQz-d other than z>=0?

[Matt J]

could please let me know where my condition on X is exactly cheked ... other than z>=0

@sanjay I don't understand the question. I already told you in my last comment that the condition on X is never explicitly checked. Only the (entirely equivalent) condition z>=0 is checked.

[sanjay]

let me explain again z>=0 is checked but the whole discussion is i am enforcing the condition which X(1)>=X(1601),X(2)>=X(1601),,,,,,,,X(1600)>=X(1601) where this condition is satisfied using Q and z approach? and if i dont use this Q and z approach and recover my X and then apply this condition, so do you think they are same or they both approach has difference?

[Torsten]

Both approaches (using lsqlin with lb = 0 and A*x <= b or using lsqnonneg for optimization in z where x is determined after the optimization as x = Q*z) are correct and should give the same result (at least ||C*x-d|| and ||C*Q*z-d|| should be the same)). Test it.

If you don't trust in the appoach with the coordinate transformation

z(i) = x(i) - x(1601) (1 <= i <= 1600)
z(1601) = x(1601)

or explicitly rewritten in x

x(i) = z(i) + z(1601) (1 < = i <= 1600)
x(1601) = z(1601)

or rewritten in matrix form

x = Q*z

use the approach in x.

I don't know what you mean by "recover my X and then apply this condition".

[Matt J]

i am enforcing the condition which X(1)>=X(1601),X(2)>=X(1601),,,,,,,,X(1600)>=X(1601) where this condition is satisfied using Q and z approach?

Yes. Torsten already said it, but just for emphasis, the condition X(1)>=X(1601),X(2)>=X(1601),,,,,,,,X(1600)>=X(1601) means the very same thing as the condition z>=0. Therefore, if you have optimized over z subject to z>=0, you have done the very same thing as when you optimize over X subject to the constraints X(1)>=X(1601),X(2)>=X(1601),,,,,,,,X(1600)>=X(1601).