2
$\begingroup$

Let $ a,b,c \in \mathbb{R}_{+} $ be non-negative and $ Y, B, C \in \mathbb{S}_{+} $ a Hermitian positive semi-definite matrices. $D$ is a diagonal matrix with non-negative entries. Solve

$$ \begin{align} & \max_{a, Y} ~ a \\ & s.t. \\ & a \cdot {\rm{Tr}} (BY) - {\rm{Tr}} (CY) + a \cdot b \leq 0 \\ & {\rm{Tr}} (DY) \leq c \\ & Y \succcurlyeq 0 \\ & a \geq 0 \end{align}$$

Additional information:

To the best of knowledge the first constraint is bilinear and I wonder whether there is a smarter way of handling this constraint. Thus far, I have found two solutions, which are the following:

  1. Alternate optimization: Find a feasible $ a $ and then optimize for $ Y $. Then, fix $ Y $ to optimize $ a $. And continue doing this sequentially.

  2. First-order Taylor approximation: Linearize the fisrt constraint and solve the new problem for a number of iterations.

These two approaches require me to iterate over several instances. Can we do better? Thank you!

Update: I have found this previous post (Optimization problem with quadratic objective and a bilinear constraint), where the unknown parameters of a bilinear constraint are put together in a matrix. Can the first constraint in my problem be transformed in the same manner? Any hints would be great! $$ \begin{bmatrix} Y & 0 \\ 0^T & a \end{bmatrix} \succcurlyeq 0 $$

Improve this question
$\endgroup$
  • $\begingroup$ Since $a \ge 0$ perhaps you can factor $a$ out and solve the problem with $a = 0$ and $a >0$ separately? $\endgroup$ – copper.hat Jun 19 '19 at 16:33
  • $\begingroup$ @copper.hat I am not sure if I understand your idea. $a$ and $Y$ are not known, how can I factor $a$ out? $\endgroup$ – Duns Jun 19 '19 at 16:37
  • $\begingroup$ Sorry, I made a mistake. $\endgroup$ – copper.hat Jun 19 '19 at 16:44
  • $\begingroup$ Notation could be improved. Having both $a$ and $A$ is not great. Having both $a$ and $\rm a$ is confusing. Given parameters from the first letters of the Latin alphabet. Unknowns from the last letters. $\endgroup$ – Rodrigo de Azevedo Jun 20 '19 at 7:17
  • $\begingroup$ I have corrected the problem with /rm. $\endgroup$ – Duns Jun 20 '19 at 8:01
2
$\begingroup$

The problem is quasi-convex in that it is convex for every fixed $a$ and the feasible set decreases for increasing $a$. Hence it can be solved by bisection in $a$

Example code on bisection to explain strategy https://yalmip.github.io/example/decayrate/

If you use MATLAB/YALMIP, you can do it very easily using built-in functionality (here using mosek as SDP solver)

A = randn(5);A = A*A';
C = randn(5);C = C*C';
D = randn(5);
Y = sdpvar(5);
sdpvar a
b = 1;c = 1;
Model = [a*trace(A*Y) - trace(C*Y) + a*b <= 0, Y >= 0, trace(D*Y) <= c];
bisection(Model,-a,sdpsettings('solver','mosek'))

I belive the problem is ill-posed though (unless $D$ has certain structure relative to $A$ and $C$) which allows $Y$ to grow arbitrarily large

Improve this answer
$\endgroup$
  • $\begingroup$ Johan, thank you for your reply. Yes, $D$ is a diagonal matrix with non-negative values. I have not tried using bisection because this method would have required me to find two good initial points where the optimal solution should lie. Thus, instead I decided to linearize and initialize $a$ with 0. I think, I will give it a try with the bisection method and see how it performs. On the other hand, do you think that linearizing is silly (given that $a$ is a non-negative real value)? $\endgroup$ – Duns Jun 19 '19 at 17:23
  • 1
    $\begingroup$ Finding initial values for the bracketing is trivial, YALMIP does also that automatically (simply increase $a$ quickly until infeasible, and you have the starting interval). With a linearization strategy, you will have to add line-searches etc, and a proof that you actually converge to the globally optimal solution. Bisection is simple and you have guaranteed quick convergence. $\endgroup$ – Johan Löfberg Jun 19 '19 at 17:35
  • $\begingroup$ thank you. Where can I find a convergence proof for these two methods: bisection and linearization $\endgroup$ – Duns Jun 20 '19 at 6:53
  • $\begingroup$ Bisection is trivial and classical, you half the search-space in every iteration, hence if your initial gap betweeen upper and lower bound is $U-L$, you will arrive at a desired tolerance $\delta$ in $\log_2((U-L)/\delta)$ iterations. Proving convergence of a linearization strategy (if possible) depends on your overall algorithm (line-search, backtracking etc etc) $\endgroup$ – Johan Löfberg Jun 20 '19 at 7:05
  • $\begingroup$ I see!. Thank you for the details. $\endgroup$ – Duns Jun 20 '19 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.