Bounded Condition Number


(Jeff McGuire) #1

I am wondering if there are ways to bound the condition number of a matrix that is being optimized?
For instance, for a simple 2 by 2 matrix A that I am trying to maximize the product of eigenvalues subject to a maximum ratio of the two eigenvalues given by tau. In practice there are other constraint LMIs in this particular problem, but I think this captures the basic issue, namely that the condition # is quasi-convex.

  minimize(det_inv(A))
  subject to
      A==semidefinite(2);
      lambda_max(A)>=tau*lambda_min(A);

yields an error: Invalid constraint: {convex} >= {concave}
even when tau =1 and the second constraint is always
satisfied by the solution even if that equation is commented out (e.g. the largest eigenvalue is >= the second eigenvalue).

Is there a smart way to recast this problem such that the constraint equation that limits the value of the condition number is convex?


(Mark L. Stone) #2

“Linear Matrix Inequalities in System and Control Theory,” by Boyd, ElGhaoui, Feron, Balakrishnan


Section 3.1 Minimizing Condition Number by Scaling
Section 3.2 Minimizing Condition Number of a Positive-Definite Matrix

Also, there is some material in “Condition number of a positive definite matrix” in Section 6.2.2 "Eigenvalue optimization: of the “MOSEK Modeling Cookbook” Release 3.1 https://docs.mosek.com/modeling-cookbook/sdo.html

Also search for “condition number” (several scattered pages) in “Convex Optimization”, Boyd and Vandenberghe http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

All of this is easy to code in CVX.


(Jeff McGuire) #3

Thanks Mark! Will read through those.


(Jeff McGuire) #4

For anyone trying to do this, the constraint equation
to add to your CVX code is:

lambda_min(A)*(K^2)*eye(length(A)) >= A

where K is the desired upper limit on the condition # and A is a square symmetric matrix that you’re optimizing.