# 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

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.