# Maximizing a function over a polytope

I have to maximize
$$f(x,y)=-\log(xy)$$ However I need it over the polytope $T=\mathrm{conv}\{(1/2,1/2),(1,2),(2,1)\}$ and this gives me problems: Then I get $$f_x(x,y)=1/x=0$$ $$f_y(x,y)=1/y=0$$ and I get $x=1$ and $y=1$. However, I know the answer is $(1/2,1/2)$? But I simply don't see why. The point $(1,1)$ is in the convex hull so why isn't this the solution? Is it because it isn't on the "border".

I then need to state it's unique by using the below mentioned definitions:

Let $$V=\{x_1,...,x_m \}\subset\mathbb{R}$$ and $$P=\mathrm{conv}\{x_1,\dots,x_m \}=\{\lambda_1 x_1+\dots+\lambda_m x_m \mid\lambda_i\geq 0,\lambda_1+...+\lambda_m=1\}$$

The optimization problem $$\max_{x\in V} f(x)$$ has a global maximum at $x \in V$, where
$$f(x_0 )=\max\{f(x_1 ),\dots,f(x_m)\}.$$
This maximum is unique iff $f(x_0 )=f(x_j)$ for a unique $j=1,\dots,m$.

• Hi Ann and welcome to scicomp! Please provide the complete constrained optimization problem. Also, please clarify your notation. What exactly does $log(x,y)$ mean?
– Paul
Oct 15 '15 at 14:12
• Regard the function f: {(x,y)∈R^2|(x,y)>0}→R given by: f(x,y)=-log⁡(xy) where log denotes the natural logaritme. Furthermore let T denote the convex hull of the points: ((1/2,1/2),(1,2),(2,1))∈R^2. Solve the optimization problem: max⁡{f(x,y)|(x,y)∈T} Is there more than one optimal point?
– Ann
Oct 15 '15 at 14:23
• @Ann How do you get $x=1=y$ as a minimum? The equation $1/x = 0$ has no solution (otherwise you'd get the contradiction $1 = 0\cdot x = 0$). This implies that any maximizer must lie on the boundary. Oct 15 '15 at 15:04
• @ChristianClason, of course you are right. My calculater gave me that answer and I simply didn't control it. But how do you calculate the solution then ? Can you simply check the three corner points because one of those must be the solution?
– Ann
Oct 15 '15 at 15:26
• @Ann, no, the solution could also lie on one of the facets $\lambda x_1 + (1-\lambda) x_2$, $\lambda\in (0,1)$. You need to look for maximizers of the function restricted to each facet, $F(\lambda) = f(\lambda x_1 + (1-\lambda) x_2)$ with the restriction $\lambda \in [0,1]$. This will give you three candidates for maximizers, and you pick the one with the largest value (which will turn out to be one of the corners because your homework problem was constructed that way). Oct 15 '15 at 16:51

## 1 Answer

The immediate answer to your question is that for constrained optimization problems, the solution does not have to satisfy $\partial f(x,y)/\partial x=0, \partial f(x,y)/\partial y=0$. Consequently, your initial approach to find the minimum won' work.

For the concrete problem you have here, the objective function is convex, and by definition so is the domain on which you want to minimize it. Consequently, the maximum will lie on the boundary, and you really only have to find the maximum of the objective function on each of the three lines that bound your polygon. Indeed, this will show that the maximum lies where you expect it to be.