Suppose first that you have two sets of EQUALITY constraints; seems to me you could relax ALL of them (setting their LMs to some arbitrary, but possibly well-chosen, values); you are basically concatenating all the multipliers into one big vector; there may be numerical ill-conditioning issues. Suppose all is well, then the sub-gradient step will move the LMs in the direction that improves the error on each violated constraint.

However, the bigger issue is that you appear to have some inequality constraints. Could these first be converted by introduction of slack variables? If not, you will need KKT conditions.

Dear Professor Morton E. O'Kelly,

I really appreciate the valuable help you gave me. I am trying to solve my model using slack variables for inequality constraints. Hope it works.

Kind regards,

Morteza Shabanzadeh

http://mortezash.blogfa.com/

The subgradient is a vector with one component for each Lagrangian multiplier.  The standard way to compute a subgradient is to set the value of a given component to the violation of the corresponding constraint, possibly normalised in some way.  Then the current vector of multipliers is updated by adding the subgradient vector multiplied by a small constant. Try looking at the papers by John Beasley on subgradient methods for location problems.  They are very clear.

Dear Adam,

Many thanks for your helpful comments. Surely, the method you mentioned and the papers of Prof. John Beasley could be fruitful for my research.

Regards,

Morteza

Dear Morteza, 

You can find some details on Lagrangian method with a numerical example here (dualizing two constraints): 

http://www.cs.uleth.ca/~benkoczi/OR/read/lagrange-relax-introduct-fisher85.pdf

I hope it will be helpful ! 

Regards.

http://www.cs.uleth.ca/~benkoczi/OR/read/lagrange-relax-introduct-fisher85.pdf

Dear Kadri,

Unfortunately, I could not download the mentioned paper and even I do not still know its topic.

I would be grateful if you could send it to me.

Regards,

Morteza

Dear Kadri,

I could download it today.

Thanks

Okey, 

Enjoy your reading !

Hi, you may find the following example useful. Please see the file attached.

I take the opportunity to thank you for those good answers to @ Morteza Shabanzadeh, I am in the same case as @ Morteza Shabanzadeh. I have implemented subgradient algorithm regarding the two sets of dualized constraints, the problem I am meeting is that LLB I is big that optimal value of original problem. Can you advise me?

Placide Nduwayo , if you have a minimisation problem, then the lower bound that you get with Lagrangian relaxation should not exceed the cost of the optimal solution to the original problem, regardless of what multipliers you use. If it does, then there must be a bug either in your code or in your relaxation.

Thank you Adam N. Letchford I think it that, I am testing lot of instances for many of them the value i find is good but for athers LLB is big than optimal value of original problem

Hi Morteza,

I am wondering whether did you get the answer to your question? If so, I would appreciate it if you could help me figure out how to solve my problem which is relaxed with two simultaneous lagrangian multipliers.

Thanks in advance.

I take the opportunity to thank you for those good answers to @ Morteza Shabanzadeh. I have a question, the formulation of the step size updation in subgradient LR method have a denominator“||Ax-b||”,if||Ax-b||=0，How can I determine the step size?

Yansong Bai within subgradient methods zero subgradient implies that the optimal solution is obtained and the algorithm terminates. For more information on stepsizes please refer to https://ieeexplore.ieee.org/abstract/document/9112667

Thank you Mikhail A. Bragin very much and I will read this paper later. Actually, I want to find the optimal "lambda" corresponding to the lagrangian relaxation to generate the . The objective function can be expressed as "(min)cx+lambda*(Ax-b)"(Ax=b is the equality constraints ). If the optimal solution is obtained, and Ax-b=0, then lambda can take different values,which the objective function value will not be influence.Does it mean the optimal solution(variable x) can corresponding to multiple values of lambda?

Yansong Bai it is possible that optimal lambda belongs to a set of optimal values.

Yansong Bai : The term Ax - b is a vector, and ||Ax - b|| is its norm. (I think they usually use the standard Euclidean norm, but I'm not sure.) So, if the solution to the current relaxation satisfies ||Ax-b|| = 0, then Ax = b, and x is the optimal solution of the original problem.

(Note that this argument applies only when all of the relaxed constraints are *equations*. If you relax inequalities, then things are more complicated, and you have to consider the complementary slackness conditions.)

Thank you Adam N. Letchford for your help.

Adam N. Letchford ，there is another problem needing your help,when ||Ax-b||=0 or is close to 0,the lambda can change greatly,that is,sum(lambda(k)-lambda(k-1)) can equal to a large number while ||Ax-b|| is equal to 0 or close to 0.

I guess you just need to reduce your step-size a bit more rapidly?

Thank you Adam N. Letchford for this valuable advice. I have use the multiplier update of the subgradient method(lambda(k)=lambda(k-1)+t(k)*(Ax-b),t(k)=(ZUB-ZD)/||Ax-b||^2,ZUB(upper bound) ). The data of process can be,

• iteration (1) ZUB (4822.9) ZD (3316.15) ||Ax-b||^2 (9) sum(lambda(k)-lambda(k-1)) (1506.8)
• iteration (2) ZUB (4822.9) ZD (3316.15) ||Ax-b||^2 (0.0078^2) sum(lambda(k)-lambda(k-1)) (1.93*E5)

Note that the objective function value (ZD) of the iteration 2 has not changed.

。。。。

I guess there must be something wrong with it, so it didn't go on，Is there something wrong with my understanding of subgradient iteration and the parameter installation?

In order to guarantee convergence, you need a "step size", which decreases from one iteration to the next. See for example this paper:

https://www.diva-portal.org/smash/get/diva2:658495/FULLTEXT01.pdf

Thank you very much for this paper, Adam N. Letchford . For example, I find if a problem can be foumulated as:

objective:f1=min 3x+4y;

constraints:x+y=6;

x=1;

0

Yansong Bai : sorry, but I can't understand the question that you posted on 25th April 2021. What is the original problem, and which constraints are you relaxing?

Well , Adam N. Letchford ，I thought before that the meaning of Lagrangian multiplier is the change of the objective function corresponding to the unit change at the right end of the constraint, so I try to change the unit amount at the right end of the constraint corresponding to the dual multiplier to see if I can find the corresponding dual multiplier according to the change of the objective function.

You might find this old paper by Geoffrion helpful:

https://link.springer.com/chapter/10.1007/BFb0120690

Thank you, Adam N. Letchford for your helpful comments.