1 of 54

2 of 54

Lecture 11: Distributed Optimization

2

The Lecture will be recorded

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

3 of 54

Course Plan

3

without�Uncertainty

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

4 of 54

Agenda

4

  1. Use a simple multi-agent problem example
  2. Explain 3 important concepts by example
  3. Consolidating and prescribing a simple algorithm for multi-agent coordination

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

5 of 54

The needy robots’ problem

5

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

6 of 54

The needy robots’ problem

6

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

7 of 54

A. How strict is the constraint?

7

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

8 of 54

A. How strict is the constraint?

8

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

9 of 54

A. What do we gain by relaxing the constraint a bit?

9

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

10 of 54

A. What do we gain by relaxing the constraint a bit?

10

 

 

 

How can we assess the slope?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

11 of 54

A. The dual variable of the constraint

11

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

12 of 54

B. Privacy, Autonomy, and Distributed Computation

12

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

13 of 54

B. Privacy, Autonomy, and Distributed Computation

13

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

14 of 54

B. Privacy, Autonomy, and Distributed Computation

14

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

15 of 54

B. Privacy, Autonomy, and Distributed Computation

15

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

Then, each robot solves:

 

Penalty for using the shared resource

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

16 of 54

B. Privacy, Autonomy, and Distributed Computation

16

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

Then, each robot solves:

 

Penalty for using the shared resource

How much should we penalize usage?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

17 of 54

B. Privacy, Autonomy, and Distributed Computation

17

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

Then, each robot solves:

 

How much should we penalize usage?�Analogously to the constraint violation�

We (the coordinator), set:

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

18 of 54

B. Privacy, Autonomy, and Distributed Computation

18

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

Then, each robot solves:

 

How much should we penalize usage?�Analogously to the constraint violation�

We (the coordinator), set:

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

19 of 54

B. Privacy, Autonomy, and Distributed Computation

19

 

Now, the robots complain that their utility is private data, and they don’t want to share it with us. Also, they don’t want us to tell them how much to charge.

We are actually fine with that, because we were starting to get tired of solving this big optimization…

So, we let them self-organize… �Can each robot decide for itself?�It could, if we didn’t have this coupling constraint…�So, we remove the coupling constraint and instead we penalize its violation in the objective function

 

Then, each robot solves:

 

How much should we penalize usage?�Analogously to the constraint violation�

We (the coordinator), set:

 

a.k.a. a Decomposition algorithm: we can use it to break a problem into multiple smaller ones.

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

20 of 54

C. Auctions

20

We have had enough of these needy robots!�We think: “Look, we have this energy. The robots all want it. Let them compete (and pay!) for it.”

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

21 of 54

C. Auctions

21

We have had enough of these needy robots!�We think: “Look, we have this energy. The robots all want it. Let them compete (and pay!) for it.”

 

Each robot declares how much energy it wants at the current price.

If demand exceeds supply, we simply raise the price...

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

22 of 54

C. Auctions

22

We have had enough of these needy robots!�We think: “Look, we have this energy. The robots all want it. Let them compete (and pay!) for it.”

 

Each robot declares how much energy it wants at the current price.

If demand exceeds supply, we simply raise the price...

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

23 of 54

C. Auctions

23

We have had enough of these needy robots!�We think: “Look, we have this energy. The robots all want it. Let them compete (and pay!) for it.”

 

Each robot declares how much energy it wants at the current price.

If demand exceeds supply, we simply raise the price...

 

 

 

 

The auction ends up at the so called market-clearing price, where supply equals demand

If we set a lower price, demand exceeds supply.

If we set a higher price, energy is wasted.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

24 of 54

C. Auctions

24

 

 

 

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

25 of 54

C. Auctions

25

 

 

 

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

  1. The optimal dual variable of the resource constraint, �capturing the sensitivity of the objective to the resource
  2. The Lagrange multiplier, �capturing the ideal penalty so that agents solve the problem distributedly
  3. The market-clearing price,�capturing the price for which supply equals demand

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

26 of 54

C. Auctions

26

 

 

 

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

  1. The optimal dual variable of the resource constraint, �capturing the sensitivity of the objective to the resource
  2. The Lagrange multiplier, �capturing the ideal penalty so that agents solve the problem distributedly
  3. The market-clearing price,�capturing the price for which supply equals demand

Different Interpretations of the Same Thing!

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

27 of 54

C. Auctions

27

 

 

 

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

  1. The optimal dual variable of the resource constraint, �capturing the sensitivity of the objective to the resource
  2. The Lagrange multiplier, �capturing the ideal penalty so that agents solve the problem distributedly
  3. The market-clearing price,�capturing the price for which supply equals demand

Different Interpretations of the Same Thing!

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

28 of 54

C. Auctions

28

 

 

 

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

29 of 54

29

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

30 of 54

30

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

31 of 54

31

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

32 of 54

32

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

33 of 54

33

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

“a robot buys energy until it’s marginal utility equals the price”

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

34 of 54

34

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

 

 

“a robot buys energy until it’s marginal utility equals the price”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

35 of 54

35

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

“a robot buys energy until it’s marginal utility equals the price”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

36 of 54

36

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

“a robot buys energy until it’s marginal utility equals the price”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

37 of 54

37

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

Intuitively: If we could buy one more kWh of energy, what is the highest per-unit price that we would be willing to pay?

“a robot buys energy until it’s marginal utility equals the price”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

38 of 54

38

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

“a robot buys energy until it’s marginal utility equals the price”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

39 of 54

39

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

“a robot buys energy until it’s marginal utility equals the price”

= the market-clearing price!

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

40 of 54

40

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

41 of 54

41

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

42 of 54

42

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

43 of 54

43

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

44 of 54

44

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

45 of 54

45

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

46 of 54

46

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

47 of 54

47

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

48 of 54

48

Distributed �Optimization

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

49 of 54

49

Dual Decomposition for Distributed Optimization

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

50 of 54

50

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

51 of 54

51

B. Distributed �Optimization

 

 

 

A. The dual �variable

 

What happens at the optimum, is that:

  1. all robots have equal marginal utility
  2. the constraint is satisfied with equality

 

...or the price is zero 🡪 “Complementary Slackness”

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

52 of 54

Next Week

52

Game Theory

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

53 of 54

Questions

53

vevox.app

151-897-505

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

54 of 54

Quiz

54

vevox.app

116-283-637

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty