# What kind is this optimization problem

I come across a problem like

$\max {\frac{1+v}{1-u}}$

$s.t.~$ $ux^2+vy^2-xy\ge0$ $\forall x,y\in\mathbb{R}$

I do not know much of optimization. What I have done is that $ux^2+vy^2\ge 2\sqrt{uv}xy\ge xy$, so I let $uv=\frac{1}{4}$ and get the seemingly correct answer.

My question is that What kind of opt problem is it? Where can I get some resources to quickly learning to solving this kind of problem?

-
It looks like a nonlinear fractional program (en.wikipedia.org/wiki/Fractional_programming). You can solve it as a general nonlinear program, but there may be specific properties you can exploit if you treat it as a fractional program. – Gilead Mar 4 '13 at 16:39
I'm perplexed by what you're trying to maximize. As soon as you have one pair, $(u_0,v_0)$, that satisfies the inequality for all $x,y$, any pair $(u_0,v)$ with $v>v_0$ also satisfies the inequality. Letting $(u_0,v_0)=(1/2,1/2)$ (since $u_0x^2+v_0y^2-xy = (x-y)^2/2$), it looks like you wind up "maximizing" $2(1+v)$ over $v>1/2$. – Barry Cipra Mar 5 '13 at 13:12

Let us simplify your constraints. Namely, set $x=r\sin\phi$, $y=r\cos\phi$. Then it simplifies to $u\sin^2\phi + v\cos^2\phi \geq \sin\phi \cos\phi$, for all $0\leq \phi\leq 2\pi.$ Then divide both sides by $\cos^2\phi$, and set $z:=\frac{\sin\phi}{\cos\phi}$. You'll get quadratic inequality $f(z):=uz^2-z+v\geq 0$, for all $z$.
So we have to describe the set of $u$ and $v$ such that the latter always holds. The discriminant of $f(z)$ is $1-4uv$, and so one has $1-4uv\leq 0$, otherwise $f(z)$ has two distinct real roots, and $f$ can't be nonnegative everywhere. Note that also we see, by setting $x$ or $y$ to 0, that $u\geq 0$ and $v\geq 0$.
So we simplified your constraints, getting rid of $x$ and $y$, to the following form: $uv\geq 1/4$, $u\geq 0$, $v\geq 0$. The rest looks like a standard exercise in "elementary" nonlinear optimization.
as suggested by the comment by Noah below, an easier way is to directly specify the constraint is to write down $$ux^2+vy^2-xy=(x,y)\begin{pmatrix}u &-1/2\&bsol;-1/2 & v\end{pmatrix}\begin{pmatrix} x\&bsol;y\end{pmatrix}$$ and note that it is nonnegative everywhere iff $\begin{pmatrix}u &-1/2\&bsol;-1/2 & v\end{pmatrix}$ is positive semidefinite.
Another way to see this is to note that the constraint is the definition of positive semi-definiteness of the matrix $\begin{bmatrix} u & -1/2 \\\ -1/2 & v\end{bmatrix}$. Your equivalent form is just the corresponding determinant condition on the minors. – Noah Stein Mar 4 '13 at 19:32
surely, as we are in the univariate case, the positivity of $f$ is equivalent to it being a sum of squares, which boils down to that matrix being positive semi-definitene. – Dima Pasechnik Mar 4 '13 at 23:35