The linear programming can be described as

$\min\ {\bf c}^{T}{\bf x}$

$ s.t.\ {\bf Ax=b} $,

$\ \ \ \ \ \ \ \ \ \|{\bf x}\|^{2}_{2}\le U$,

$\ \ \ \ \ \ \ \ \ x_{i}\ge 0,\ i=0,1,...,N-1$,

where ${\bf x}\in\mathbb{R}^{N\times 1}$, ${\bf c}\in\mathbb{R}^{N\times 1}_{+}$, ${\bf A}\in\mathbb{R}^{M\times N}_{+}$, ${\bf b}\in\mathbb{R}^{M\times 1}_{+}$, $\|\cdot\|_{2}$ is the $\ell2$-norm and $U$ is a constant scalar.

The first question is:

How to handle the last constraint (the positivity constraint)?

I can solve the problem analytically by using the method of Lagrange multipliers after I relax the the constraint. But I don't know how to solve the entire problem.

And other question is:

Is there any algorithm that can solve the problem efficiently?

Numerical results can be solved by MATLAB using the SQP algorithm, but I think there must be some simple and efficient algorithms.



I would first try to throw this at a state-of-the-art (convex) QCP (Quadratically Constrained Program) solver such as Cplex, Gurobi or Mosek. They have specialized solvers for this type of problem that typically outperform a general purpose NLP solver (sometimes by a large margin).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.