Difference between revisions of "User:Zhan"
(→DoA) |
|||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
==DoA== | ==DoA== | ||
| + | What are the next starts I should choose to reduce gemstones type difference, the discrete optimization point of view... | ||
| + | |||
=== Discrete formulation === | === Discrete formulation === | ||
| − | |||
Let us consider the gemstones as a vector ''y'' = (''y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>, y<sub>4</sub>'') in N<sup>4</sup>, where the components respectively respresent the number of '''margonite gemstones''', '''stygian gemstones''', '''torment gemstones''', '''titan gemstones'''. | Let us consider the gemstones as a vector ''y'' = (''y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>, y<sub>4</sub>'') in N<sup>4</sup>, where the components respectively respresent the number of '''margonite gemstones''', '''stygian gemstones''', '''torment gemstones''', '''titan gemstones'''. | ||
| Line 20: | Line 21: | ||
Now, let ''g'' be a finite number ''n<sub>i</sub>'' of composition of functions ''f<sub>i</sub>'', (''i'' in {1,...,4}). We consider ''g'' to be solution if it is the minimal number of composition which gives the minimum possible difference of gemstones. This gives the following minimization problem: | Now, let ''g'' be a finite number ''n<sub>i</sub>'' of composition of functions ''f<sub>i</sub>'', (''i'' in {1,...,4}). We consider ''g'' to be solution if it is the minimal number of composition which gives the minimum possible difference of gemstones. This gives the following minimization problem: | ||
| − | argmin<sub>''g''</sub> (max<sub>(i, j)</sub> |g<sub>i</sub>(y) - g<sub>j</sub>(y)| + ''d||n||<sub>1</sub>''), where ''d'' is small. | + | g<sup>*</sup> = argmin<sub>''g''</sub> (max<sub>(i, j)</sub> |g<sub>i</sub>(y) - g<sub>j</sub>(y)| + ''d||n||<sub>1</sub>''), where ''d'' is small. |
Let us set ''h<sub>(i,j)</sub>(y)'' = |g<sub>i</sub>(y) - g<sub>j</sub>(y)|. This is a polyhedral function with respect to ''n'': | Let us set ''h<sub>(i,j)</sub>(y)'' = |g<sub>i</sub>(y) - g<sub>j</sub>(y)|. This is a polyhedral function with respect to ''n'': | ||
| − | ''h<sub>(i,j)</sub>(n, y) = |''y<sub>i</sub> - y<sub>j</sub> + k<D<sub>(i,j)</sub>,n>''| where <., .> is the usual scalar product. | + | ''h<sub>(i,j)</sub>(n, y)'' = |''y<sub>i</sub> - y<sub>j</sub> + k<D<sub>(i,j)</sub>,n>''| |
| + | |||
| + | where <., .> is the usual scalar product and ''D<sub>(i,j)</sub>'' is the difference of the lines ''i, j'' of the system matrix. | ||
=== Continuous setting === | === Continuous setting === | ||
| Line 39: | Line 42: | ||
for all couple (i,j) in {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)} | for all couple (i,j) in {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)} | ||
| + | |||
| + | We remark that each of these constraints are convex. | ||
| + | |||
| + | === Computation of the solution === | ||
| + | |||
| + | Due to the nature of the problem, it is possible to get the global solution numerically. | ||
| + | |||
| + | This was tested using Juniper.jl : https://github.com/lanl-ansi/Juniper.jl | ||
==Contact== | ==Contact== | ||
| − | |||
In game character name '''Kunvie Zhan''' | In game character name '''Kunvie Zhan''' | ||
Latest revision as of 17:39, 8 June 2021
Contents
DoA
What are the next starts I should choose to reduce gemstones type difference, the discrete optimization point of view...
Discrete formulation
Let us consider the gemstones as a vector y = (y1, y2, y3, y4) in N4, where the components respectively respresent the number of margonite gemstones, stygian gemstones, torment gemstones, titan gemstones.
Then, we consider successful runs by the following functions going from N4 to N4:
f1(x) = x + k(1, 2, 3, 4)
f2(x) = x + k(4, 1, 2, 3)
f3(x) = x + k(3, 4, 1, 2)
f4(x) = x + k(2, 3, 4, 1)
Where k = 2 in Hard Mode (HM), and where the functions respectively represent start city, start veil, start gloom, start foundry.
Now, let g be a finite number ni of composition of functions fi, (i in {1,...,4}). We consider g to be solution if it is the minimal number of composition which gives the minimum possible difference of gemstones. This gives the following minimization problem:
g* = argming (max(i, j) |gi(y) - gj(y)| + d||n||1), where d is small.
Let us set h(i,j)(y) = |gi(y) - gj(y)|. This is a polyhedral function with respect to n:
h(i,j)(n, y) = |yi - yj + k<D(i,j),n>|
where <., .> is the usual scalar product and D(i,j) is the difference of the lines i, j of the system matrix.
Continuous setting
Let us now consider z in R. The discrete problem is equivalent to this one:
minz z + <n, 1>
under:
z >= yi - yj + k<D(i,j),n>
z >= yj - yi + k<D(j,i),n>
for all couple (i,j) in {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)}
We remark that each of these constraints are convex.
Computation of the solution
Due to the nature of the problem, it is possible to get the global solution numerically.
This was tested using Juniper.jl : https://github.com/lanl-ansi/Juniper.jl
Contact
In game character name Kunvie Zhan
