2
$\begingroup$

Is there a name for the following optimization problem? Is it solvable?

\begin{align} \min_{\pmb{u}} & \qquad \frac{1}{2}(\pmb{u}-\pmb{u}^m)^{T}(\pmb{u}-\pmb{u}^m)\\ \textrm{s.t.} & \qquad \pmb{A}(\pmb{u}) \textrm{ is positive definite} \end{align}

Here $\pmb{u}\,\in\mathbb{R}^{n},\pmb{u}^m\,\in\mathbb{R}^n$, $\pmb{u}^m$ is known, and $\pmb{A}(\pmb{u})\in\,\mathbb{R}^{m\times{m}}, m\approx{n}.$ The entries of $\pmb{A}$ depend linearly on the components of $\pmb{u}$ in a known manner. e.g. ${A}_{7,8}=c_1u_3 + c_2u_{12} + c_3u_{4}$ with $c_i$ known.

$\endgroup$

1 Answer 1

4
$\begingroup$

This can be considered to be a Linear Semidefinite Programming Problem (SDP), which is convex, and for which there are many available numerical optimization solvers.

To put it in standard form, which is not necessary with some optimization modeling systems or solvers, the convex quadratic objective function can be moved to the constraints as a Second Order Come Problem (SOCP) constraint (which is a special case of linear SDP constraint), but better left in SOCP form.

If strict positive definiteness is needed, the linear SDP constraint can be formulated as A(u) - small_positive_number*Identity_matrix is positive semidefinite., where small_positive_number is perhaps about 1e-5.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Could you please point me to something accessible about the formulation of SDP/SOCP? $\endgroup$
    – NNN
    Feb 8, 2022 at 5:51
  • 2
    $\begingroup$ Convex Optimization – Boyd and Vandenberghe web.stanford.edu/~boyd/cvxbook $\endgroup$ Feb 8, 2022 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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