Jump to content
Objectivism Online Forum

My summmer research poster (Math/Bio people may be interested)

Rate this topic


tnunamak

Recommended Posts

This summer I spent 10 weeks working with one of my favorite professors, an optimization mathematician, using Ampl, a mathematical programming language (to write linear programs in), to model the behavior of single cell organisms (we have been using ecoli and yeast to test it).

I'll let the poster speak for itself, if you have questions I'll happily answer them. It can be found at the URL given below. Thanks for looking :D

http://www.cs.trinity.edu/~tnunamak/PosterFinal.pdf

Edit: Fixed a spelling mistake in the title

Edited by tnunamak
Link to comment
Share on other sites

Finally another optimization researcher on the forum!

Congratulations on the completion of the poster. Your research looks really fascinating.

I have one constructive comment concerning the mathematics. Under "Future work" you indicate

Future goals of the project include calculating the dimension of the optimal set in order to determine the extent of degeneracy.

Mathematically, this does not really make any sense. The number of denegerate (optimal) solutions is entirely unrelated to the dimension of your feasible region.

In addition, it appears as if your mathematical program is a network optimization problem. These problems tend to have many degenerate extreme point solutions. Thus, in this case, encountering a lot of degeneracy should not be surprising. Anyway, if you want to discuss any of this, feel free to contact me. Linear optimization is my idea of fun.

Edited by DarkWaters
Link to comment
Share on other sites

Thanks :)

Before this summer, I didn't even know what a linear program was. My background in math is three semesters of calculus, differential equations and a bit of linear algebra, and an abstract math course (proof writing/logic). That said, this project has been heavily directed by my advisor and much of the thinking has come from him. I have come at this project from the computer science side of it, mostly parsing text, etc. Luckily, I think I have gotten fairly proficient with the basics of using a language such as Ampl, and am becoming comfortable with optimization techniques. I still don't know a lot of the theory behind linear optimization, so I am constantly forcing my advisor to fill me in :).

Mathematically, this does not really make any sense. The number of denegerate (optimal) solutions is entirely unrelated to the dimension of your feasible region.

This is something I'll have to ask my advisor about, as it was his idea. I would be surprised to find there was not even a slight correlation, but you may be right. I'll follow up when I return for the fall semester.

In addition, it appears as if your mathematical program is a network optimization problem. These problems tend to have many degenerate extreme point solutions. Thus, in this case, encountering a lot of degeneracy should not be surprising.

Indeed. That was what really motivated this project in the first place. FBA is an established technique which involves an established model. Much of the literature in the field, from what I understand, is coming from people without much of an optimization background. They all seemed to have overlooked the possibility of the optimal solution being non-unique, which is why we have defined new terminology.

Anyway, if you want to discuss any of this, feel free to contact me. Linear optimization is my idea of fun.

I hope this reply is suitable. Thanks for your comments!

Link to comment
Share on other sites

This is something I'll have to ask my advisor about, as it was his idea. I would be surprised to find there was not even a slight correlation [between the dimension of the feasible region and the number of degenerate extreme points], but you may be right. I'll follow up when I return for the fall semester.

There is no correlation. A simple example:

Draw a regular hexagon on a sheet of paper. Let this be a two-dimensional feasible region. We can represent this polygon as the feasible region of a linear program with six constraints, where there is a bijective mapping from the constraints to the sides of the polygon. None of the extreme points (corners) are degenerate because each extreme point has exactly two active constraints (and this is a two dimensional feasible region).

However, we can arbitrarily turn any of the extreme points into a degenerate extreme point by drawing a line that is tangent to that extreme point and by representing that new line as a new (but redundant) constraint. In fact we can make any number of the extreme points degenerate by adding constraints that are tangent to extreme point solutions. Thus, in two dimensions, we can create an example with 0 of 6 extreme point solutions as degenerate, with 1 of 6 extreme point solutions as degenerate, w/ 2 of 6 degenerate, ..., with all extreme points as degenerate.

Needless to say, we can easily extend this to any regular (convex) n-gon in two dimensions. Similarly, we can extend this to regular polytopes in higher dimensions as well.

Thus, the number of degenerate extreme points is completely independent of the dimension of the feasible region. Essentially because for any finite dimension greater than one, there are examples of bounded feasible regions with no degenerate extreme points, with all degenerate extreme points and with any number in between.

Degeneracy is usually a topic reserved for graduate students. It is difficult to explain these things without being able to draw pictures. Anyway, I hope that this helps!

Edited by DarkWaters
Link to comment
Share on other sites

  • 1 month later...

Your explanation makes sense. I do have a question though. In your 2-D hexagonal feasible region example, I take it that the cardinality of the set of all possible degenerate solutions is the same as the cardinality of the natural numbers or the reals (not sure which). If you extend the feasible region to higher dimensions, does the cardinality of this set remain the same? If not, then wouldn't that indicate a correlation between degeneracy and solution-space dimension?

I apologize for the late reply... the semester has gotten off to a quick start :). We do plan to publish a paper or two before Christmas, and I'll be going to a conference in November to present our work and ideas. Thanks for the comments.

Link to comment
Share on other sites

This summer I spent 10 weeks working with one of my favorite professors, an optimization mathematician, using Ampl, a mathematical programming language (to write linear programs in), to model the behavior of single cell organisms (we have been using ecoli and yeast to test it).

I'll let the poster speak for itself, if you have questions I'll happily answer them. It can be found at the URL given below. Thanks for looking :)

http://www.cs.trinity.edu/~tnunamak/PosterFinal.pdf

Edit: Fixed a spelling mistake in the title

This looks rather interesting. Have you published any detailed papers yet. If so can you provide some journal references?

Thanks.

Bob Kolker

Link to comment
Share on other sites

Hi,

I take it that the cardinality of the set of all possible degenerate solutions is the same as the cardinality of the natural numbers or the reals (not sure which).

The set of natural numbers is a countably infinite set and the set of real numbers is an uncountably infinite set. That being said, it does not really make sense to discuss the cardinality of these sets.

Anyway, if you want to know the answer to the question: "Can there be an infinite number of degenerate feasible solutions to a two dimensional linear program?" The answer is no since a linear program can only have a finite number of extreme points and all degenerate solutions must be extreme points (mainly since linear programming assumes a finite number of constraints and decision variables.)

There is a branch of mathematical optimization called semi-infinite programming, which allows infinitely many constraints. I have not looked into this area much. I would not be surprised if strange things can happen.

If you extend the feasible region to higher dimensions, does the cardinality of this set remain the same? If not, then wouldn't that indicate a correlation between degeneracy and solution-space dimension?

A corollary of my previous argument is the following: assume no knowledge of the number of decision variables or the number of constraints in your linear program. For any given dimension d we can construct a linear program whose feasible region is d dimensional that has x degenerate extreme points, where x is an arbitrary non-negative and finite integer. Sorry, but there is no correlation. :)

I'll be going to a conference in November to present our work and ideas.
Are you going to INFORMS? If you are, you are welcome to come see my presentation! Edited by DarkWaters
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...