0
$\begingroup$

I've been given a problem:

min $f(x) = c^Tx$

s.t.

$\sum_{i}x_i = 0$

$\sum_{i}x^2_i$ = 1

I've created the Lagrangian function

$L(x,\lambda) = c^Tx - \lambda_1\sum_{i}x_i - \lambda_2\left(\left(\sum_{i}x^2_i\right)-1\right)$

But I'm not sure how I can arrive at any particular solution given the $\nabla_x$ of the Lagrangian doesn't really help me. Should I augment the function to be an unconstrained minimization by replacing the values of $x_i$ using the 2 equalities? I'm not sure where to proceed.

$\endgroup$
7
  • $\begingroup$ If you find the solution for $\nabla_x$ and plug it into your lagrangian, you get a dual function $g(\lambda)$ and constraint $\lambda \ge 0$. From there you can try to derive the solution for the dual. If the duality gap is 0, then the optimal dual will be the same as the optimal primal. By the way, I think your lagrangian is wrong. $\endgroup$
    – MoneyBall
    Dec 6, 2020 at 9:00
  • $\begingroup$ why would $\lambda$ be non-negative given these are equality constraints, shouldn't they be unbounded? $\endgroup$
    – mathcomp guy
    Dec 6, 2020 at 9:04
  • $\begingroup$ yes, you're right. I use $\lambda$ for inequality constraints and $\nu$ for equality constraints, so I got confused. $\endgroup$
    – MoneyBall
    Dec 6, 2020 at 9:07
  • $\begingroup$ Why do you think the Lagrangian is wrong it's following the traditional definition of the Lagrangian function? The -1 is not part of the summation in the 2nd constraint. $\endgroup$
    – mathcomp guy
    Dec 6, 2020 at 9:33
  • $\begingroup$ In the title, you write that you're talking about quadratic inequality constraint but you provided only a quadratic equality constraint. So is it an equality or inequality? $\endgroup$
    – Hume2
    Dec 6, 2020 at 12:16

1 Answer 1

Reset to default
1
$\begingroup$

You derivate the Lagrangian with respect to each $x_i$ and $\lambda_1$ and $\lambda_2$ and put it equal to 0. $$ \frac{\partial L}{\partial x_i}=c_i-\lambda_1-2x_i\lambda_2=0 \\ \frac{\partial L}{\partial \lambda_1}=-\sum_{i=1}^{n}x_i=0 \\ \frac{\partial L}{\partial \lambda_2}=-\sum_{i=1}^{n}x_i=0 $$ From the first equation, you get: $$ x_i=\frac{c_i-\lambda_1}{2\lambda_2} $$ If you fill it into the second equation, you get $\lambda_1$: $$ \lambda_1=\frac{1}{n}\sum_{i=1}^{n}c_i $$ If you fill it into the third equation, you get $\lambda_2$: $$ \lambda_2 = \pm\frac{1}{2}\sqrt{\sum_{i=1}^{n}(c_i-\lambda_i)} $$ So you have two solutions: $$ x=\pm\frac{c-\frac{1}{n}\sum_i c_i}{||c-\frac{1}{n}\sum_i c_i||_2} $$ And you can easily check that one is minimum and the other one is maximum. The minimum is this one: $$ x=-\frac{c-\frac{1}{n}\sum_i c_i}{||c-\frac{1}{n}\sum_i c_i||_2} $$

$\endgroup$

You must log in to answer this question.

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