2
$\begingroup$

I'm working on a program where I want to solve problems of the type:

$$Ax\leq b $$

Where $A$ is a $m\times n$ matrix with $a_{ij} \in \mathbb{R}$, $x \in \mathbb{R^n} $ and $b \in \mathbb{R^m} $.

With the following conditions:

  • $\sum_{j=0}^n x_j= 1$
  • $x_j\geq 0, \forall \,j\in J$
  • $b_i\geq 0, \forall \, i\in I$

There's three kind of solutions i want to find:

  • The one(s) that minimizes $x$
  • The one(s) that maximizes $x,$ along with some indication of which $x_j$ that make it be maxed - see the example below I don't know how to describe this properly.
  • The solution that is the closest to $x_j = \frac{1}{n}, \: \forall \,j\in J $

A very simple example:
given:
$\:A = (1.5, 0.2)$
$\:b=1$
I would want to find the following solutions:

  • $S_1=\{x_1=0\quad \wedge\quad x_2=1\} $
  • $S_2 =\{x_1=0.615\quad \wedge\quad x_2=0.385\},\quad$ "$x_1$ is the variable that makes this meet the limit".
  • $S_3=\{x_1=0.5\quad \wedge\quad x_2=0.5\} $

I thought it would be straight forward by implementing the Simplex algorithm. But then i would need to have an objective function (don't I?) which I can't see that i have.
Can I construct Objective functions for the different cases I want to solve or any good suggestions on how to do this?
It might be worth mentioning that $\#J, \#I \leq 20$ and that I have never worked with linear programming before :)
Thanks.

*Edit*, yea what do i mean about max/minimizing..

Something like this:
$min\{c^T x\,|\, x\in \mathbb{R^n} \wedge Ax \leq b \wedge x,b \geq 0\}$
$max\{c^T x\,|\, x\in \mathbb{R^n} \wedge Ax \leq b \wedge x,b \geq 0\}$

I'm not really sure about the c vector but as far as i understand it's the one I'm missing? Most of what i know about LP is from here:
https://en.wikipedia.org/wiki/Linear_programming#

$\endgroup$
5
  • $\begingroup$ You can use lingo to solve it. Lingo is a good tool to solve linear programming problem. $\endgroup$
    – fusheng
    Jul 10 at 12:47
  • $\begingroup$ @Blueman What does "minimizing/maximizing" $Ax$ mean to you in the case that $m > 1$? How can you minimize a vector? $\endgroup$
    – Ben Grossmann
    Jul 10 at 13:35
  • $\begingroup$ You need to figure out how to write your objective so that you are trying to maximise/minimise a number, rather than a vector. For example you could try to maximise or minimise the sum $\sum_{i} x_i$. By "the solution closest to $(1/n, \ldots, 1/n)$, you should define what you mean by closest. Closest in the $L_1$ norm could mean to minimise $\sum_i |x_i - 1/n|$ (this is a linear program), wheras in the $L_2$ norm it could mean to minimise $\sum_i (x_i - 1/n)^2$: this is a quadratic program. $\endgroup$
    – Joppy
    Jul 10 at 14:41
  • $\begingroup$ Since you are forcing components of $x$ to sum to 1, there are really only two objectives -- (1) maximize variability (2) minimize variability, both of which can be encoded as sums of absolute values using LP formulation. Will add an example as an answer later today. $\endgroup$
    – Annika
    Jul 10 at 18:57
  • $\begingroup$ The simplex algorithm's first step is to find a sufficient initial basis solution. This step doesn't look at the objective function, and if you have no objective function, then you can stop after this step, as it returns you a sufficient solution. $\endgroup$
    – Sudix
    Jul 11 at 2:31

1 Answer 1

Reset to default
1
$\begingroup$

As pointed out by @Joppy and myself -- your objectives need to tweaked a bit to get this to an LP-formulation -- specifically the $L_1$ norm of $x-(1/n)\mathbf{1}$ seems to be what you are trying to get at with your examples.

$$L_1(x) = \sum_{i=1}^n|x_i-1/n|$$

With constraints:

$Ax\leq b$

$\sum_1^n x_i = 1$

$x_i \geq 0 \; \forall i \in 1..n$

You give a "constraint" for $b$ but I don't think this is what you want, as it will just set $b_i$ such that the constraint is never tight over the feasible region (effectively removing it from consideration). I think you meant that the RHS is a parameter that is always a non-negative vector (in non-negative orthant of $\mathbb{R^m}$)

With this there are two objectives we can pursue:

  1. $\max L_1$: Maximize the extremeness/variability of the $x_i$ -- we want them as far from $1/n$ as possible. Since the components must sum to 1 and are positive, this will lead to most $x_i$ being close to $0$ and a few close to $1$ so $L_1$ is large. This will simultaneously maximize and minimize components of $x$, to your first two objectives.
  2. $\min L_1$: Minimize the extremeness/variability of the $x_i$ -- this is precisely your third objective and minimizing $L_1$ above will get you there.
$\endgroup$
2
  • 1
    $\begingroup$ Thanks. Yes, the constrain on $b$ is a physical restriction. I'll see if i can get it to work and get the solutions I'm looking for. I might have some follow up questions to achieve it all but I will return and mark as an answer if not so :) $\endgroup$
    – Blueman
    Jul 12 at 9:51
  • $\begingroup$ @Blueman sounds good — happy to help $\endgroup$
    – Annika
    Jul 12 at 13:17

You must log in to answer this question.

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