Abner's Postgraduate Days

Ref.: Optimization Theory

For optimimzation of intertemporal allocation of resources, there are two usual appraoches, optimal control and dynamic programming. The former one is good for analysis and the later one is good for simulation.

Ref. Dynamic optimization problems:

Dynamic optimization problems involve dynamic variables whose values change in time. Such problems exist in the areas of optimal control, parameter estimation for dynamic models, reactor network synthesis where the dynamic models arise from the differential modeling of the tubular reactors (plug flow reactors), and for dynamic simulation and optimization.

Some links

• MIT OCW 14.128 Dynamic Optimization & Economic Applications (Recursive Methods), Spring 2003
• Texas A&M University. Agec 637 Production Economics and Dynamic Optimization, Prof. Woodward.
• Course 02711: Static and Dynamic Optimization

Dynamic Programming

Optimal Control Theory

:

Ref. : Optimal control From Wikipedia, the free encyclopedia.

Optimal control theory is a mathematical field that is concerned with control policies that can be deduced using optimization algorithms.

The control that minimizes a certain cost functional is called the optimal control. It can be derived using Pontryagin's maximum principle, or by solving the Hamilton-Jacobi-Bellman equation.

Ref. : The Mathematical Atlas 49: Calculus of variations and optimal control; optimization

Reference book:

• Elements of Dynamic Optimization by Alpha C. Chiang.
• Stokey, Nancy L., and Robert E. Lucas, Jr., with Edward C. Prescott. Recursive Methods in Economic Dynamics. Cambridge, MA: Harvard University Press, 1989.
• Optimal Control Theory: An Introduction, by Donald E. Kirk
• Optimal Control and Estimation (Dover Books on Advanced Mathematics), by Robert F. Stengel
• Optimal Control Theory and Static Optimization in Economics by Daniel Leonard, Ngo van Long

• Title: SubGemini: Identifying Subcircuits using a Fast Subgraph Isomorphism Algorithm
• Authors: Miles Ohlrich, Carl Ebeling, Eka Ginting, and Lisa Sather
• Source: Proceedings of IEEE/ACM Design Automation Conference,Dallas,1993:31-37
• Speaker: C. S. Ou
• Time: 03.09 (Friday) 19:30-21:00
• Place: Room 550, Department of Computer Science, NTHU

The authors proposed the heuristic algorithm to solve the problem Subgraph Isomorphism which is in NP-C.

Since the citcuit of VLSI design is a complicated network as hypergraph representation, for simplicity, they defined some kinds of vertices, P node for pMOS, C node for cMOS, etc. And they define the bubble node to represent the wire of IC circuit which is a hyperedge.

They labelled some informations on each vertex. Those informations about connection configuration will help them to find some ``key vertex'' as candidate for starting to check subgraph isomorphism.

That is the first phase of SubGemini.

The second phase is the procedure of checking subgraph isomorphism as traditional appraoch like BFS. Since we got those special ``key vertices'' as starting point, this algorithm will find subgraph isomorphism very fast. However this algorithm is not guarantee to find every isomorphic subgraph if those subgraphs coupled very close.



After the introduction of SubGemini, the speaker C. S. Ou also introduces his research that solve this problem by a very large matrix consisting of many small connection configuration matrices, e.g. one pMOS P1 and one CMOS C3 is connected by source of P1 and drain of C3, then its connection configuration matrix is look like the 3X3 0-1 matrix M which all entries are zero besides M(s,d).

They code thus connection configurations for some possible cases and set up some rules to filter most useless cases, eventually reduce such very large matrix into a much smaller one.

Finally they solve this reduced matrix as the problem SUBMATRIX which is also in NP-C. And the experimental results show that this algorthm got better performance.

ef.: Teresa M. Przytycka: An Important Connection Between Network Motifs and Parsimony Models. RECOMB 2006: 321-335

We demonstrate an important connection between network motifs in certain biological networks and validity of evolutionary trees constructed using parsimony methods.

We introduce a graph theoretical characterization that helps to select correct characters. Given a set of characters and a set of taxa, we construct a network called character overlap graph.

Here "taxa" means a grouping or classifing of organisms. It does not implies the specific biological class of organisms.

Given a set of taxa and a set of characters, one could constcut the character overlap graph, that the vertices are characters and the edge exists iff. there exists a taxon contains both characters.

Each taxon is described by a binary vector of attributes. Those attributes so called characters. If a taxon has a attributes, then it assigns 1 to the attribute in the binary vector, otherwise assgins 0.

Therefore we could use those informations like taxon to build an evolution tree using parsimony approach, i.e., Maximum Parsimony Tree Problem. Most variations of it are in NP-C. In spite of it, the correctness problem, i.e., the correctness of the bulit evolution tree, is also open.

Intuitively, its correctness depends strongly on choosing appropriately charactors and taxa. The goal of this paper is to give a method to improve the correctness of evolution tree which is contructed by parsimony approach.

First, author defined "persistent," i.e., a charactor is persistent if it is gained exactly once and lost at most once, and persistent parsimony means all charactors are persistent.

The author found that the hole, chordless cycle of length at least four, is rare in charactor overlap graph whose charactors are chose as protein domains. In contrast, the hole is abundant in charactor overlap graph whose charactors are chose as introns. Furthermore the correctness of tree built by domain overlap graph is better than built by intron overlap graph. (refers the references [11], [27], [10], [29] of this paper.)

The author believe this phenomenon is meaningful. He prove that

If all charactors are persistent then corresponding charactor overlap graph is chordal.

Therefore we could measure whether the chosen charactors lead to incorrect evolutionary tree by the Edge-Deletion Problem of chordal graph. Unfortunately it is in NP-C.

The author adapt the idea of network motif. He just counts the number of squares, the chordless cycles with length 4, of the charactor overlap graph, and compare it to the number of squares of charactor overlap graph whose charactors gain or loss randomly.

Although the relation between non-persistent charactors and the number of squares is not so clear. Few non-persistent charactors might lead to large number of squares, and large number of squares might have small non-persistent charactors. We still could benefit from it by finding the charactors involved in a large number of squares. It is a significant noise of the data. (In domain overlap graph, those charactors, that involved in a large number of squares, are the promiscuous domains which are known to appear in many diverse multidomain proteins.)

Ref.: Teresa M. Przytycka, Chordal Graphs in Computational Biology - New Insights & Applications, Seminars, Computing Science, Simon Fraser University.

we introduced and studied graph theoretical representation of multidomain proteins called domain overlap graph. In the domain overlap graph, the vertices are protein domains and two domains are connected by an edge if there is a protein that contains both domains.

This leads the studies of a graph-theoretical framework, based on properties of chordal graphs and cographs [3].

References:

1. Teresa M. Przytycka, George Davis, Nan Song, Dannie Durand: Graph Theoretical Insights into Evolution of Multidomain Proteins. RECOMB 2005: 311-325
2. Teresa M. Przytycka. An important connection between network motifs and parsimony models. RECOMB 2006, Lecture Notes in Computational Biology, 2006. (My Note)
3. Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations, Zotenko E, Guimaraes KS, Jothi R, Przytycka TM. Algorithms for Molecular Biology 2006, 1:7