2
$\begingroup$

I would like to minimize over quite large set of $a_i$ some function $f(a_1,a_2,\dots,a_n)$ subject to a set of $k$ linear constraints: $$ i=1\dots n: \quad a_i\ge0;\quad j=1\dots k:\quad\sum_{i=1}^n m_{ji}a_i\ge b_j,\tag1 $$ where the matrix $m$ and the vector $b$ are given. This is very similar to LinearProgramming, except for the art of the minimized function. Ideally the command should have 3 parameters: $f,m,b$ and probably the size of the vector $n$, though the latter can be read from the dimensions of the matrix $m$ and should return the minimized value of $f$ and the corresponding minimizing vector.

I can find the solutions for small $m$ with Minimize, but it is not realistic to type all the constraints by hand.

For test purpose the function $f$ can be considered just quadratic $f=a.M.a$.

Any help is appreciated.

$\endgroup$
16
  • $\begingroup$ tried QuadraticOptimization?. e.g. QuadraticOptimization[{m,ConstantArray[0,n]},{m,b}] $\endgroup$
    – kglr
    Feb 17, 2021 at 17:28
  • $\begingroup$ @kglr My function is in fact not quadratic. I would like to have a general solution for an arbitrary (scalar) function $f$. $\endgroup$
    – drer
    Feb 17, 2021 at 18:46
  • $\begingroup$ Please check this library.wolfram.com/infocenter/MathSource/795 J. C. Culioli made excellent work more than 20 year ago. $\endgroup$ Feb 17, 2021 at 18:47
  • $\begingroup$ @PierreALBARÈDE Thank you. I will check. But as I already said Minimize works well with my function. The only problem is that I don't know a way to submit my linear constraints in a "compressed form". $\endgroup$
    – drer
    Feb 17, 2021 at 18:51
  • 1
    $\begingroup$ .. or VectorGreaterEqual[{m.a,b}]? $\endgroup$
    – kglr
    Feb 17, 2021 at 19:06

1 Answer 1

4
$\begingroup$

You can specify linear inequality constraints succinctly using VectorGreaterEqual or using Element + NonNegativeReals:

constraints1 = Element[{m.a - b, a}, NonNegativeReals];

constraints2 = VectorGreaterEqual /@ {{m.a, b}, {a, 0}}; 

Example:

SeedRandom[1];
ClearAll[a, b, m]

n = k = 4;
m = RandomReal[4, {n, k}];
a = Array[Symbol["a" <> ToString[#]] &, n]
b = RandomReal[{-3, 3}, k];

obj = a.m.a;

sol1 = Minimize[{obj, constraints1}, a]
{0.553132, {a1 -> 0., a2 -> 0., a3 -> 0.807969, a4 -> 0.}} 

We get the same result using constraints2:

sol2 = Minimize[{obj, constraints2}, a]
{0.553132, {a1 -> 0., a2 -> 0., a3 -> 0.807969, a4 -> 0.}} 
$\endgroup$
1
  • $\begingroup$ Thank you very much! It is always a pleasure to learn from experts. $\endgroup$
    – drer
    Feb 18, 2021 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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