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$ Commented Jul 10, 2023 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$ Commented Jul 10, 2023 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$ Commented Jul 10, 2023 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$ Commented Jul 10, 2023 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$ Commented Jul 11, 2023 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$ Commented Jul 12, 2023 at 9:51
  • $\begingroup$ @Blueman sounds good — happy to help $\endgroup$ Commented Jul 12, 2023 at 13:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.