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?

  • $\begingroup$ 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. $\endgroup$ – Gilead Mar 4 '13 at 16:39
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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\\-1/2 & v\end{pmatrix}\begin{pmatrix} x\\y\end{pmatrix}$$ and note that it is nonnegative everywhere iff $\begin{pmatrix}u &-1/2\\-1/2 & v\end{pmatrix}$ is positive semidefinite.

  • 2
    $\begingroup$ 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. $\endgroup$ – Noah Stein Mar 4 '13 at 19:32
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Mar 4 '13 at 23:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.