4
$\begingroup$

I have a standard linear programming problems I want to solve:

$$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. \end{aligned} \right. $$

$F^T$ is a vector that doesn't involve $x$.

The problem with the above minimization is that, I don't know what $n$, the number of variable $x$ is — it is also a part of the minimization. There are a few constraints governing how the vector $x$ should behave. Additionally, there are constraints linking from $x_i$ to $x_{i+1}$. This means that given $x_i$, we know how to form the constraint for $x_{i+1}$. Also, even though we don't know about $n$, but in my problem I can easily construct the corresponding $f_i$ term for each $x_i$.

The constraints are complicated in the sense that it is not easy to express the constraints in the following form:

$$ Ax \leq a $$

and

$$ Bx = b $$

What I can do, at best, is to express $a$ and $b$ involving a first order of $x$ ( i.e., no $x^2$ and above). The matrix $A$ and $B$ are known values with no involvement of $x$.

I understand that linear programming can be used to tackle problems such as this. But the two problems I mention above ( don't know what $n$ is, and cannot separate out the matrix/vector easily) stop me from proceeding.

Is there any other techniques I can use to solve the problem?

$\endgroup$
  • $\begingroup$ May be you can have a look at the simplex method, Dual simplex method,...etc. They are the ones which i learnt when i studied this course, but now i have forgotten! $\endgroup$ – anonymous Aug 28 '10 at 8:13
  • $\begingroup$ @Chandru1, as far as I know these methods require you to separate out the known matrix/vector values, which is not possible in my case. $\endgroup$ – Graviton Aug 28 '10 at 8:15
  • $\begingroup$ Are the dimensions of $A$, $b$, or $f$ available? $\endgroup$ – J. M. is a poor mathematician Aug 28 '10 at 8:35
  • 3
    $\begingroup$ Maybe just post the actual problem you have, and let the collective minds of this site wade through the thicket themselves? $\endgroup$ – J. M. is a poor mathematician Aug 28 '10 at 9:03
  • 1
    $\begingroup$ Ok, probably I do not understand your problem. $\endgroup$ – Tsuyoshi Ito Aug 30 '10 at 12:26
2
$\begingroup$

If I understand your question correctly, I believe there are two ways to tackle this problem:

  1. If the issue is just in the generation of the constraints $Ax \leq a$ and $Bx=b$, then these forms can be forced out using automatic differentiation. Specifically, let $g(x) = Ax -a$ and $h(x) = Bx - b$. To generate, $a$ and $b$, we evaluate $g(0)$ and $h(0)$, respectively. In order to generate $A$ and $B$, take an arbitrary point $x$ and evaluate $g^\prime(x)$ and $h^\prime(x)$ using the Jacobian code from an available automatic differentiation toolbox to generate $A$ and $B$, respectively. Even with a linear operator, it's sometimes easier to just use AD to generate them in the case that we have a matrix-free implementation of the operator. Note, it's likely that the AD code will want to fix the number of variables, so this may not be the appropriate solution. However, it depends on the code and the setup that you have.

  2. Matrix-free implementations of an interior point method do not require the number of variables to be known. Typically, they just require certain vector operations to be defined. There may be a different list, but I typically work with

    • init(x) - Initialize memory
    • copy(x) - copy a vector
    • scal(alpha,x) - $\alpha x$
    • axpy(alpha,x,y) - $\alpha x + y$
    • innr(x,y) - $\langle x,y\rangle$
    • prod(x,y) - pointwise product
    • linv(x,y) - inverse of the pointwise product
    • srch(x,y) - how far we can go in the direction y form x till we violate nonnegativity
    • barr(x) - log-barrier function

Technically, we can generalize this to work with general symmetric cone constraints, but we should ignore that for now. Anyway, none of these operations require the size of the vector to be defined as long as we can compute them. Then, based on these operations, we have enough information to implement an interior point method to take care of the inequality constraints and an SQP method to take care of the equality constraints. Now, candidly, if the number of variables is large, it's going to perform poorly. Basically, there's a number of linear systems that need to be solved. However, if the number of equality constraints is bigger than about 50 the Krylov methods used to solve these linear systems will start to deteriorate badly. The way to get around this is to use a preconditioner, but without a matrix you're going to have to be very clever. That'll depend on the problem structure.

In terms of existing codes and algorithms, Optizelle can do this. However, again, you really, really will need an effective preconditioner for the equality constraints in order to have a shot at making this work well. Specifically, a preconditioner for $BB^T$.

As a final note, in general, for a linear program, you typically want to use a linear programming specific algorithm like a specialized primal-dual interior point method or the simplex method. Typically, for the LP specific primal-dual interior point methods, you'll need to be able to take the Choleski factorization of a very particular system. If you don't know the number of variables, this won't work. That pushes you back to more general algorithms like those that Optizelle uses. That said, this code is not specialized for linear programs, so the performance will suffer.

$\endgroup$

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.