Optimization: Gradient of constraints - How to solve in a quadratic formula?

64 Views Asked by At

Assume that we have our objective function (matrix algebra)

$$J(x) = \frac{1}{2}x^T Q x + c^T x$$

With the constraints:

$$lb \le x \le ub \\ lba \le Ax \le uba$$

I begin first to determine how large $x$ can be. So I will first use these constraints first. $$x \le ub \\ Ax \le uba$$

We concatenate these into one constraints $g(x) = \left\{\begin{matrix} x & -ub & \\ Ax & -uba & \end{matrix}\right.$

The second thing I need to do is to find the gradient of $J(x)$ which is the derivative respect on $x$:

$$\triangledown J(x) = x^T Q + c^T$$

And the same for $g(x)$

$$\triangledown g(x) = \left\{\begin{matrix} 1 & & \\ A & & \end{matrix}\right.$$

Now I need to put $\triangledown J(x) = \lambda \triangledown g(x)$ and find the $x$

But the problem is that $\triangledown g(x)$ has twice the dimension of $\triangledown J(x)$

Do you know how to solve this?

1

There are 1 best solutions below

9
On BEST ANSWER

In $\nabla J(x) = \lambda \nabla g(x)$, both sides are of dimension $x$. But there is a more fundamental problem: that equation alone does not solve the problem. What you need are the KKT conditions (neccessary and sufficient if $Q$ is positive semidefinite). Define the Lagrangian $$L(x,\lambda_1,\lambda_2, \lambda_3, \lambda_4) = 0.5 x^TQx + c^Tx + \lambda_1^T(x-u) + \lambda_2^T(l-x) + \lambda_3^T(Ax-u_A)+\lambda_4^T(l_A-Ax).$$ The stationarity condition w.r.t. $x$ is what you tried to derive: $$Qx + c + (\lambda_1 - \lambda_2) + A^T (\lambda_3 - \lambda_4) = 0$$ The other KKT conditions are complementary slackness: $$\lambda_1^T(x-u) = 0, \;\lambda_2^T(l-x) = 0, \;\lambda_3^T(Ax-u_A) = 0,\; \lambda_4^T(l_A-Ax)=0$$ and primal/dual feasibility: $$l \leq x \leq u, \; l_A\leq Ax\leq u_A, \; \lambda_1\geq 0, \;\lambda_2\geq 0, \;\lambda_3\geq 0, \;\lambda_4\geq 0.$$ Finding a solution that satisfies all these conditions is not easy. I recommend using a QC(Q)P solver such as CPLEX/Gurobi/Mosek (commercial) or Ipopt (free).