Maximize $\min(abh,cdg)k+\min(abj,fdg)l+\min(ebh,cdi)l+\min(ebj,fdi)m$ subject to $a+e=c+f=1$

249 Views Asked by At

Let $a,b,c,\ldots,m\ge0$ with $a,c,e,f\le1$. I want to maximize $$\varphi(a,c,e,f):=\min(abh,cdg)k+\min(abj,fdg)l+\min(ebh,cdi)l+\min(ebj,fdi)m$$ over all choices of $a,c,e,f$ subject to $a+e=c+f=1$. Unfortunately, I don't have much to contribute, since I'm not familiar with this kind of problems. I could imagine that the solution is simple, but I might be wrong.

It might be useful to note that $2\min(x,y)=x+y-|x-y|$ for all $x,y\ge0$.

3

There are 3 best solutions below

1
On BEST ANSWER

Simplified solution

The feasible region of $0\le a\le 1,0\le c\le 1$ is divided into polygons by the four lines $$abh=cdg,abj=(1-c)dg,(1-a)bh=cdi, (1-a)bj=(1-c)di. (1)$$

Within each polygon the objective function is linear and its maximum therefore occurs at a vertex of the polygon The maximum over all polygons therefore has to occur at a point of intersection of two of the eight lines given by the four lines (1) together with the lines $a=0,a=1,c=0,c=1$.

Solving these equations in pairs gives the following set of points at which the objective function needs to be evaluated. The maximum of these values is the required solution.

Since $a+e=c+f=1$, it is sufficient to give the values of $(a,c)$. These are as follows, where any points lying outside the unit square can be ignored.

Solutions with $a=0$ $$(0,0),(0,1),(0,\frac{bh}{di}),(0,\frac{di-bj}{di})$$ Solutions with $a=1$

$$(1,0),(1,1),(1,\frac{bh}{dg}),(1,\frac{dg-bj}{dg})$$

Further solutions with $c=0$ $$(\frac{dg}{bj},0),(\frac{bj-di}{bj},0)$$

Further solutions with $c=1$

$$(\frac{dg}{bh},1),(\frac{bh-di}{bh},1)$$

Remaining 6 solutions

$$(\frac{dg}{b(j+h)},\frac{h}{j+h}),(\frac{bh}{d(g+i)},\frac{g}{g+i}),(\frac{h(bj-di)}{d(gj-hi)},\frac{g(bj-di)}{b(gj-hi)})$$ $$(\frac{g(di-bh)}{b(ij-gh)},\frac{h(bj-dg)}{d(i-g)}),(\frac{g}{g+i},\frac{dg+di-bj}{d(g+i)}),(\frac{bj+bh-di}{b(h+j)},\frac{h}{h+j}).$$

5
On

The basic strategy is to use Lagrange multipliers to find the local maxima and minima of the function, and then find the maximum of the function at the boundaries of the domain. This gives us the set of all points that might produce the maximum. To narrow this list down, we then have to plug each point into $\varphi$ and see which one produces the largest value. Normally we would also have to worry about whether the function diverges to infinity or about what happens when $(a,c,e,f)\rightarrow \infty$ on some path, but thankfully in this case the domain is bounded and $\varphi$ is defined everywhere on its domain.

The two constraining functions are $g(x)=a+e$ and $h(x)=c+f$. Imagine that you're walking along the intersection of the curves $g(x)=1$ and $h(x)=1$. At any point $x$ let's call the set of direction you're allowed to move in $A_x$. We know that walking in the direction of the gradient vector $\nabla \varphi(x)$ will lead to you to greater values of $\varphi$. We are interested in the points where $\nabla\varphi(x)$ is perpendicular to every vector in $A_x$, because this means the only way to increase the value of $\varphi$ is to walk straight off the constraining curves. ($x$ is either a local minima or maxima) Let's call $A_x^{\bot}$ the set of vectors perpendicular to $A_x$. Then $\nabla \varphi(x)\in A_x^{\bot}$.

If we move on the curve $g(x)=1$ then for every point on that curve we are moving perpendicular to $\nabla g(x)$ other wise we would wander off the contour. So moving along the intersection of $g(x)=1$ and $h(x)=1$ means we are moving perpendicular to $\nabla g(x)$ and $\nabla h(x)$. Thus, these two vectors span $A_x^{\bot}$ and we are interested in points $x$ where $\nabla \varphi(x)$ can be written as a linear combination of $\nabla g(x)$ and $\nabla h(x)$. $$\nabla \varphi(x)=\lambda \nabla g(x) + \mu \nabla h(x)$$

To make things slightly less cluttered we'll use the fact that $\varphi(a,c,e,f)$ has a maximum where $2\varphi(a,c,e,f)$ does. Using the trick you mentioned and simplifying the resulting equations we get $$bhk+bjl-\frac{abh-cdg}{|abh-cdg|}(bhk)-\frac{abj-fdg}{|abj-fdg|}(bjl)=bhl+bjm-\frac{ebh-cdi}{|ebh-cdi|}(bhl)-\frac{ebj-fdi}{|ebj-fdi|}(bjm)$$ $$dgk+dil+\frac{abh-cdg}{|abh-cdg|}(dgk)+\frac{ebh-cdi}{|ebh-cdi|}(dil)=dgl+dim+\frac{abj-fdg}{|abj-fdg|}(dgl)+\frac{ebj-fdi}{|ebj-fdi|}(bjm)$$ $$a+e=1$$ $$c+f=1$$ Of course in order produce these equations we had to make a multitude of assumptions like $abh\neq cdg$ for example. So the case where $abh=cdg$ has to be analyzed separately.

Anyways, the terms with the absolute values are effectively $\pm1$ so we don't have to worry about solving further and we can just proceed case by case. But there sure are a lot of cases! For example, what if we picked $a,c,e,f$ such that in the first equation we have $$bhk+bjl+bhk+bjl=bhl+bjm+bhl+bjm$$ Well then this equation is only consistent iff $b=0$ or $hk+jl=hl+jm$. Of course, this is all assuming we are able to pick $a,c,e,f$ such that $cdg > abh$, $fdg > abj$, $cdi > ebh$, $fdi > ebj$. Then of course, there's still the question of whether or not these values of $a,c,e,f$ will even make the second equation consistent.

Btw, the boundaries of the domain are $a=0,e=1$, $a=1,e=0$, $c=0,f=1$, $c=1,f=0$. So there are four more optimization problems that will need to be analyzed. If you want to keep your sanity while solving this problem, you'll need to find some shortcuts: some ways of eliminating sets of points from your consideration by proving they could never produce the maximum for all $b,d,g,h,i,j,k,l,m$.

1
On

Edition of 02.09.2019

HINT

$$\color{brown}{\textbf{SIMPLE CASES}}$$

Let the goal function is $F.$

If $\mathbf{(b=0)\vee (d=0),}$ then $F=0.$

Similarly, $F=0$ if $\mathbf{(h=0)\wedge(j=0)}$ or $\mathbf{(g=0)\wedge(i=0)}.$

Case $\color{green}{\mathbf{h=0}}.$

$$F(e,f) = l\min((1-e)bj,fdg) + m\min(ebj,fdi),$$ $$\max F(e,f)= \max F(e,1) = l\min((1-e)bj,dg) + m\min(ebj,di).$$

If $\mathbf{(dg > bj)\wedge(di>bj)}$ then $$\max F(e,f) = \max (F(0,1),F(1,1)) = \max(lbj, mbj).$$

If $\mathbf{(dg > bj)\wedge(di\le bj)}$ then $$\max F(e,f) = \max F(e,1),\quad\text{where}\quad e\in\left\{0, \dfrac{di}{bj}, 1\right\}.$$

If $\mathbf{(dg \le bj)\wedge(di > bj)}$ then $$\max F(e,f) = \max F(e,1),\quad\text{where}\quad e\in\left\{0, 1-\dfrac{dg}{bj}, 1\right\}.$$

If $\mathbf{d(g+i)\le bj}$ then $$\max F(e,f) = \max F(e,1),\quad\text{where}\quad e\in\left\{0,1-\dfrac{dg}{bj}, \dfrac{di}{bj}, 1\right\}.$$

If $\mathbf{(dg\le bj)\wedge(di\le bj)\wedge(bj\le d(g+i))}$ then $$\max F(e,f) = F(e,1) = ldg+mdi,\quad\text{where}\quad e\in\left(1-\dfrac{dg}{bj}, \dfrac{di}{bj}\right),\quad f=1.$$

Cases $\color{green}{\mathbf{j=0,\quad g=0,\quad i=0}}$ can be considered similarly.

$$\color{brown}{\textbf{COMMON CASE}}$$

Denote $$bh=p,\quad bj=q,\quad dg=r,\quad di = s,$$

then $$F(a,c) = k\min\dbinom{pa}{rc} + l\min\dbinom{qa}{r(1-c)} + l\min\dbinom{p(1-a)}{sc} + m\min\dbinom{q(1-a)}{s(1-c)}.$$

Applying the previous approach with the significant bounds and intersections, the required result can be achieved.

For the corners, $$F_C = \max(F_{00},F_{01},F_{10},F_{11}),$$ where $$F_{00} = \min\dbinom{mq}{ms},\quad F_{01} = \min\dbinom{lp}{ls},\quad F_{10}=\min\dbinom{lq}{lr},\quad F_{11}=\min\dbinom{kp}{kr}.$$

For the left side,

$$F_L=\max\limits_c F(0,c) = \max\limits_c\left(l\min\dbinom{p}{sc} + m\min\dbinom{q}{s(1-c)}\right).$$

Etc.