- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Computation of convex conjugates in linear time using...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Computation of convex conjugates in linear time using graph-matrix calculus Haque, Tasnuva
Abstract
Computational Convex Analysis focuses on computing the convex operators which are used very often in convex analysis. The Fenchel conjugate is one of the most frequently used convex operator. The objective of this thesis is to develop an algorithm for computing the conjugate of a bivariate Piecewise Linear-Quadratic (PLQ) function. Although some algorithms already exist for computing the conjugate of a bivariate PLQ function, their worst-case time complexity is not linear. Our challenge is to improve the worst case time complexity to linear. We use a planar graph to represent the entities of a PLQ function. Each node of the graph contains a GPH matrix which represents an entity of the PLQ function . In addition, we store the adjacency information and type of all entities. We traverse the graph using breadth first search and compute the conjugate of each entity. Moreover we store the information of visited entities using a binary flag. So we never need loop through all entities to check whether it is already visited. As a result we get linear computation time in the worst case. We perform numerical experiment which confirms that our algorithm is running in linear-time. We provide a comparison of the performance of this algorithm with the previous algorithms. Finally we explained how to extend this algorithm in higher dimensions while keeping the worst-case time complexity linear.
Item Metadata
Title |
Computation of convex conjugates in linear time using graph-matrix calculus
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2017
|
Description |
Computational Convex Analysis focuses on computing the convex operators
which are used very often in convex analysis. The Fenchel conjugate
is one of the most frequently used convex operator. The objective of this
thesis is to develop an algorithm for computing the conjugate of a bivariate
Piecewise Linear-Quadratic (PLQ) function. Although some algorithms already
exist for computing the conjugate of a bivariate PLQ function, their
worst-case time complexity is not linear. Our challenge is to improve the
worst case time complexity to linear.
We use a planar graph to represent the entities of a PLQ function. Each
node of the graph contains a GPH matrix which represents an entity of the
PLQ function . In addition, we store the adjacency information and type of
all entities. We traverse the graph using breadth first search and compute
the conjugate of each entity. Moreover we store the information of visited
entities using a binary flag. So we never need loop through all entities to
check whether it is already visited. As a result we get linear computation
time in the worst case.
We perform numerical experiment which confirms that our algorithm
is running in linear-time. We provide a comparison of the performance of
this algorithm with the previous algorithms. Finally we explained how to
extend this algorithm in higher dimensions while keeping the worst-case time
complexity linear.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2017-03-30
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0343417
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2017-05
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International