Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Closed-form solution of a quadratic optimization problem

  1. Jul 14, 2012 #1

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

    [itex] \displaystyle \max_{\xi\ge 0, \lambda\ge 0}\,\, -\frac{1}{2}\||\xi\||^2
    +(\xi,\,\lambda) -\frac{1}{2}\||\lambda\||^2[/itex]

    Here [itex]\xi[/itex] and [itex]\lambda[/itex] are vectors.
    Thank you.
  2. jcsd
  3. Jul 14, 2012 #2


    User Avatar
    Science Advisor

    The expression is easier to see as -1/2||ξ-λ||2. So the max is 0, when the vectors are equal.
  4. Jul 15, 2012 #3
    Thank you very much, mathman.
    So the level set corresponding to the maximum value is [itex]\xi=\lambda, \,\,\lambda\ge 0, \xi\ge 0[/itex]
  5. Jul 15, 2012 #4


    User Avatar
    2017 Award

    Staff: Mentor

    One remark:

    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 [itex]||\lambda||\ge 0, ||\xi||\ge 0[/itex]? This follows from the definition of the norm.
  6. Jul 16, 2012 #5
    Thank you for your reply, mfb.

    In fact I don't compare vectors with real numbers. In the notation [itex] \lambda\ge 0,\,\,\xi\ge 0,\,\,\,\,\,0\,\,[/itex] 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?

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


    User Avatar
    2017 Award

    Staff: Mentor

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

    In your equation, [itex]\lambda= \xi[/itex] 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.
  8. Jul 17, 2012 #7
    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.
    [itex]x\ge y [/itex] iff [itex]\forall i,\,\,\,x_i\ge y_i. [/itex]
  9. Jul 18, 2012 #8


    User Avatar
    2017 Award

    Staff: Mentor

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

    If there is any positive solution which satisfies [itex]\lambda=\xi[/itex], the expression in unbounded.
    If there is no positive solution at all, [itex]\lambda=\xi=0[/itex] 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:
    [tex]-\frac{1}{2}(\lambda_1-\xi_1)^2 + \lambda_1 X_1 + \xi_1 Z_1[/tex]
    I drop the index now, as it is always 1.
    Using the individual derivatives, this has a maximum in the whole plane where [itex]\lambda-\xi + X=0[/itex] and [itex]-\lambda+\xi + Z=0[/itex]. 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 [itex]\lambda=\xi[/itex]: 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 [itex]\lambda=0[/itex]: [itex]-\frac{1}{2}\xi^2 + \xi Z[/itex].
    For Z<0, the maximum is at [itex]\xi=0[/itex].

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

    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 -2Yi-Ci > 0 for any i gives an unbound expression.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook