Closed-form solution of a quadratic optimization problem

[lementin]

Hello,

My question is as follows. Is it possible to obtain a closed form solution to

\displaystyle \max_{\xi\ge 0, \lambda\ge 0}\,\, -\frac{1}{2}\||\xi\||^2<br /> +(\xi,\,\lambda) -\frac{1}{2}\||\lambda\||^2

Here \xi and \lambda are vectors.
Thank you.

 

[mathman]

The expression is easier to see as -1/2||ξ-λ||². So the max is 0, when the vectors are equal.

 

[lementin]

Thank you very much, mathman.
So the level set corresponding to the maximum value is \xi=\lambda, \,\,\lambda\ge 0, \xi\ge 0

 

[mfb]

One remark:

\lambda\ge 0, \xi\ge 0

Are you sure that you want to compare vectors with real numbers?
Your vectors could be real numbers, fine, but in this case I would not expect any formulas with scalar products and so on.

Do you mean ||\lambda||\ge 0, ||\xi||\ge 0? This follows from the definition of the norm.

 

[lementin]

Thank you for your reply, mfb.

In fact I don't compare vectors with real numbers. In the notation \lambda\ge 0,\,\,\xi\ge 0,\,\,\,\,\,0\,\, is actually the 0 vector (that is all its components are 0).

I would also like to extend my question here. How to find the closed form solution of the following problem, where linear terms are added?

\displaystyle\max_{\lambda\ge 0 ,\,\, \xi\ge 0}-\frac{1}{2}\||\lambda-\xi\||^2 +(\lambda, -Y-q)+ (\xi, -Y+q-CI),\,\,
where all components of Y are either 1 or -1, C>0, I is the identity matrix, and q is an arbitrary vector.

 

[mfb]

How do you define \geq for vectors? As far as I know, there is no standard way to do this.

In your equation, \lambda= \xi fixes the first expression to 0. Now, find any vector which gives some positive or negative value for the scalar products, and you can make the product arbitrary large by multiplying the vector with a positive or negative constant.

 

[lementin]

Thank you very much, mfb. This really seems to be the case that with some choices of constants within the inner products the expression can be unbounded from above.

I meant a partial order on the vector space, with not all vectors being comparable.
x\ge y iff \forall i,\,\,\,x_i\ge y_i.

 

[mfb]

Oh, your relation requires a specific basis of the vector space.

If there is any positive solution which satisfies \lambda=\xi, the expression in unbounded.
If there is no positive solution at all, \lambda=\xi=0 is the maximum.
If both cases do not help, note that the individual components are all independent, assuming the standard scalar product. Let's take the index 1 and use X=-Y-q, Z=-Y+q-CI:
-\frac{1}{2}(\lambda_1-\xi_1)^2 + \lambda_1 X_1 + \xi_1 Z_1
I drop the index now, as it is always 1.
Using the individual derivatives, this has a maximum in the whole plane where \lambda-\xi + X=0 and -\lambda+\xi + Z=0. This can be satisfied for X+Z=0 only. In this case, the first expression is sufficient and a maximum exists for all X, as you can get any arbitrary difference between two positive numbers.

Otherwise, look at \lambda=\xi: If X+Z = -2Y-C > 0, the expression is unbounded. If not, we have a maximum, but not in the whole plane, therefore it has to be at the constraints:

Look at \lambda=0: -\frac{1}{2}\xi^2 + \xi Z.
For Z<0, the maximum is at \xi=0.

Look at \xi=0: -\frac{1}{2}\lambda^2 + \lambda X.
For X<0, the maximum is at \lambda=0.

Therefore, if X<0, Z<0, the maximum is at (0,0). If one of those is >0, you have a simple one-dimensional expression. The case X>0, Z>0 leads to X+Z>0 and the unbounded case discussed above.Put everything together, and you get your global maximum ;).
Note that -2Y_i-C_i > 0 for any i gives an unbound expression.