# Optimization with bilinear constraint

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}

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$$

• Since $a \ge 0$ perhaps you can factor $a$ out and solve the problem with $a = 0$ and $a >0$ separately? – copper.hat Jun 19 '19 at 16:33
• @copper.hat I am not sure if I understand your idea. $a$ and $Y$ are not known, how can I factor $a$ out? – Duns Jun 19 '19 at 16:37
• Sorry, I made a mistake. – copper.hat Jun 19 '19 at 16:44
• 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. – Rodrigo de Azevedo Jun 20 '19 at 7:17
• I have corrected the problem with /rm. – Duns Jun 20 '19 at 8:01

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

• 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)? – Duns Jun 19 '19 at 17:23
• 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. – Johan Löfberg Jun 19 '19 at 17:35
• thank you. Where can I find a convergence proof for these two methods: bisection and linearization – Duns Jun 20 '19 at 6:53
• 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) – Johan Löfberg Jun 20 '19 at 7:05
• I see!. Thank you for the details. – Duns Jun 20 '19 at 9:23