1
$\begingroup$

I come across an optimization problem of the following form.

$$\max {\frac{1+v}{1-u}} \qquad \text{s.t.} \qquad ux^2+vy^2-xy \ge 0, \quad \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.

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

Improve this question
$\endgroup$
2
  • $\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
    Commented Mar 4, 2013 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
    Commented Mar 5, 2013 at 13:12

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Mar 4, 2013 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
    Commented Mar 4, 2013 at 23:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .