Pushpa Publishing House

Journal Menu

Content

Volume 24 (2024)

Volume 23 (2023)

Volume 20 (2021)

Volume 19 (2020)

Volume 18 (2019)

Volume 17 (2018)

Volume 16 (2017)

Volume 15 (2016)

Volume 14 (2015)

Volume 13 (2015)

Volume 12 (2014)

Volume 11 (2014)

Volume 10 (2013)

Volume 9 (2013)

Volume 8 (2012)

Volume 7 (2012)

Volume 6 (2011)

Volume 5 (2011)

Volume 4 (2010)

Volume 3 (2010)

	Volume 3, Issue 2 Pg 87 - 172 (June 2010)
	Volume 3, Issue 1 Pg 1 - 86 (March 2010)

Volume 2 (2009)

Volume 1 (2009)

International Journal of Numerical Methods and Applications

International Journal of Numerical Methods and Applications
Volume 3, Issue 1, Pages 1 - 23 (March 2010)

HIT-AND-RUN ALGORITHMS FOR FEASIBILITY AND DETECTION OF NECESSARY LINEAR MATRIX INEQUALITY CONSTRAINTS
Shafiu Jibrin

Abstract:
In a recent work, the semidefinite coordinate directions algorithm (SCD) has been used within another algorithm (called Algorithm 6) for feasibility of a system of linear matrix inequality constraints. Algorithm 6 finds a feasible point with probability one, if the feasible region has a non-empty interior. If the system is found to be feasible, then Algorithm 6 is switched to SCD to detect the necessary constraints. We present a modification of Algorithm 6 called Modified SCD. If the feasible region has a non-empty interior, then Modified SCD also finds a feasible point with probability one. In addition, Modified SCD automatically becomes the usual SCD, once a feasible is found. There is no need to switch Modified SCD to the usual SCD. In fact, Modified SCD is a hit-and-run Monte Carlo method for detecting necessary constraints that can be started from any point (feasible or infeasible). Test results show that Modified SCD takes less time than Algorithm 6 to find a feasible point. We similarly, give modifications of the two semidefinite diagonal directions algorithms (SDDs), namely: Modified original SDD and Modified uniform SDD. These also find feasible points and detect necessary constraints. We compare Modified SCD, Modified original SDD and Modified uniform SDD. Our test results indicate that Modified uniform SDD and Modified SCD are the best for feasibility and constraint detection. However, it is difficult to decide which is better between Modified uniform SDD and Modified SCD. We think that the performance of each of them depends on the problem type and might be the best in certain cases.

Keywords and phrases: semidefinite programming, linear matrix inequalities, redundancy, Monte Carlo method.

Number of Downloads: 251 | Number of Views: 745