forum.alglib.net
http://forum.alglib.net/

getting started with Linear (or Quadratic) Programming
http://forum.alglib.net/viewtopic.php?f=2&t=4439
Page 1 of 1

Author:  gene [ Wed Apr 13, 2022 3:59 pm ]
Post subject:  getting started with Linear (or Quadratic) Programming

Please point me to relevant examples and/or APIs in ALGLIB.

I want to find the vector x whose objective function
  • minimizes th L1 distance of x from a constant vector x0
  • where L1 distance = sum of absolute values = sum abs((x(i)-x0(i))

and subject to this set of linear constraints:
  • x(i+1) - x(i) >= constant(i) for i = 1..n-1 (i.e. x values in ascending order, with specified minimum spacing)
  • x(1) >= min_constant
  • x(n) <= max_constant

If I can get this working, then I want to try alternative distance metrics
  • L2 distance = sum of squared differences = sum (x(i)-x0(i)**2
  • L-infinity distance = max of absolute values = max abs((x(i)-x0(i))

Eventually, I want to extend the problem to two dimensions, with each x a point in the x-y plane.

Author:  gene [ Thu Apr 14, 2022 11:54 pm ]
Post subject:  Re: getting started with Linear (or Quadratic) Programming

I studied the manual and think I found the right examples:
For the L1 distance objective function which is discontinuous I will try:
    Nonsmooth nonlinearly constrained optimization
    https://www.alglib.net/translator/man/manual.cpython.html#example_minns_d_nlc

For the L2 distance objective function which is quadratic I will try:
    Linearly constrained dense quadratic programming
    https://www.alglib.net/translator/man/manual.cpython.html#example_minqp_d_lc1

Author:  tonyturtletwn [ Fri Jul 15, 2022 3:20 pm ]
Post subject:  Re: getting started with Linear (or Quadratic) Programming

I think L1 norm minimization can be cast as a linear programming problem.

Create non-negative dummy variables e_0l, e_0r, e_1l, e_1r, ...
then set equality constraints (in additional to the original constraints):
x(0) = x0(0) + e_0r
x(0) = x0(0) - e_0l
......

Then minimize e_0l + e0r + e_1l + e_1r + ...

So the LP example so be sufficient:
https://www.alglib.net/translator/man/manual.cpp.html#example_minlp_basic

Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/