1
$\begingroup$

I want to solve a least-squares problem of the form:

$$\begin{array}{ll} \text{minimize} & \|Ax-b\|_2^2\\ \text{subject to} & \mathcal{L}(x)\succeq0\end{array}$$

with $\mathcal{L} : \mathbb{R}^n \to \mathbb{R}^{m \times m}$ being a linear operator.

This paper claims that they used Mosek to solve a problem of this form. To my best knowledge, the Mosek documentation on semidefinite programming does only include examples with linear objectives.

How do I need to formulate the problem described above to solve it with Mosek?

$\endgroup$
  • $\begingroup$ Mosek handles quadratic objectives with linear constraints (and certain varieties of quadratic constraints). $\endgroup$ – anomaly Nov 16 '19 at 20:27
  • $\begingroup$ Do you mean that this problem is not solvable with Mosek? $\endgroup$ – Felix Crazzolara Nov 16 '19 at 20:28
  • $\begingroup$ No, I mean that the problem you describe is exactly what mosek handles. $\endgroup$ – anomaly Nov 16 '19 at 20:29
  • $\begingroup$ Could you please link to the corresponding page in the documentation or an example. I don't understand how this is equivalent to quadratic or linear constraints. $\endgroup$ – Felix Crazzolara Nov 16 '19 at 20:33
  • 1
    $\begingroup$ Please let me know if you agree with my edits. $\endgroup$ – Rodrigo de Azevedo Nov 17 '19 at 9:43
3
$\begingroup$

You first write the problem as minimization of a new variable $t$ with the constraints $ \|Ax-b\|_2^2\leq t$ (and all your other constraints). The quadratic constraints can then be written using a second-order cone constraint as $\left|\left|\begin{matrix}1-t\\2(Ax-b)\end{matrix}\right|\right|\leq 1+t$. At that point, you have a mixed second-order and semidefinite cone program.

Having said that, in practice you would most often use a modelling language which would do this manipulations for you and then call Mosek.

You absolutely do not write the quadratic constraints as an LMI through a Schur complement as illustrated in the link in the comments. That's like trying to multiply two numbers by using logarithmic rules. Sure it's one way to do it if you have a calculator without any support for multiplication, but if your calculator has multiplication, use that button.

$\endgroup$
  • $\begingroup$ Affine conic constraints in MOSEK are only supported for the Matlab interface though afaik. I unfortunately cannot use the Matlab interface. Would it be just incovenient for me to formulate the problem using a Schur complement, or does it also affect the performance of MOSEK? $\endgroup$ – Felix Crazzolara Nov 17 '19 at 11:47
  • $\begingroup$ What do you mean? All these types of constraints are supported in any Mosek API you would use. You would never ever formulate quadratic constraints as LMIs with Mosek (or SeDuMi, SDPT3 or any other other mixed socp-sdp solver for that matter) $\endgroup$ – Johan Löfberg Nov 17 '19 at 15:05

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.