0
$\begingroup$

I wonder how to solve the following constrained problem

${\rm Minimize}_{\vec{A}}$ $\parallel Z\vec{A}-Y\parallel^2_2$ , $\quad\vec{A}\in\mathbb{R}^{n^2}$

such that: $A\in\mathbb{R}^{5\times 5}$ is positive definite

where $\vec{A}=vec(A)$. For the unconstrained case, which has a closed form solution, I used MATLAB command lsqlin(). With constraints, in MATLAB, I am stuck as the constraints should be in terms of the variable that is minimized $\vec{A}$. However, my constraint is in terms of the matrix form $A$.

I can also say

${\rm Minimize}_{A}$ $\parallel X^{\rm T}AX-Y\parallel^2_2$ ,

such that: $A\in\mathbb{R}^{5\times 5}$ and $X^{\rm T}AX >0$, where $X\in\mathbb{R}^5$

$\endgroup$
1
$\begingroup$

This is a convex semi-definite optimization problem which can be readily formulated (and solved, if not too gigantic) in MATLAB using either CVX or YALMIP, both free. You just have to specify A as being positive semi-definite. If you want A to be strictly positive definite, then specify $A - cI$ to be positive semi-definite, where c is as small positive number, such as 1e-6, and I is the Identity matrix of the appropriate dimension.

For this problem, CVX should be adequate, and has a lower learning curve and less installation hassle (semidefinite solvers are included).

Edit: CVX solution might be something like:

cvx_begin
variable A(6,6)
minimize(norm(Z*vec(A)-Y)) % I chose to minimize norm instead of norm squared
A == semidefinite(6)
cvx_end

At the conclusion of which, if successfully solved, A will contain the optimal solution, avaialable for you use in the MATLAB session.

$\endgroup$
  • $\begingroup$ Thank you for your answer, I am new to Yalmip and semi-definite programming. Actually this is a part of my problem which is bean already done in MATLAB, so I need to stick to MATLAB. I shall first follow the tutorial link provided....Thank you $\endgroup$ – user252783 Aug 14 '16 at 19:13
  • $\begingroup$ Do you mean to say in MATLAB or CVX or YALMIP? If yes, can you please give more details on the MATLAB command. A Quick search leads me to SeDuMi toolbox. Thank you for your time. $\endgroup$ – user252783 Aug 14 '16 at 19:18
  • 1
    $\begingroup$ CVX and YALMIP are toolboxes which run under MATLAB. You can use either, but I think CVX will be easier. Both of them act as high-level front end to solvers, such as SeDuMi. If you install CVX, SeDuMi gets automatically installed for you. They save you from having to get problems into standard form in solvers such as SeDuMi, which can be difficult and error-prone. $\endgroup$ – Mark L. Stone Aug 14 '16 at 19:29
1
$\begingroup$

The problem is given by:

$$ \arg \min_{X \in \mathcal{S}_{+} } \frac{1}{2} {\left\| A \operatorname{vec} \left( X \right) - b \right\|}_{2}^{2} $$

Where $ \operatorname{vec} \left( \cdot \right) $ is the Vectorization Operator and $ \mathcal{S}_{+} $ is the set of Positive Semi definite Symmetric Matrix (Convex Set). Namely the whole problem is a convex problem.

This could easily be solved in MATLAB utilizing the Projected Gradient Descent Method.

The iterations of the algorithms are simple:

  1. Step 1 (Gradient Descent Step) - $ \operatorname{vec} \left( {X}^{k + 1} \right) = {x}^{k} - \alpha \left( {A}^{T} A \operatorname{vec} \left( {X}^{k} \right) - {A}^{T} b \right) $.
  2. Step 2 (Projection onto Symmetric Matrix Set) - $ {X}^{k + 2} = \frac{1}{2} \left( {X}^{T} + X \right) $.
  3. Step 3 (Projection onto the PSD Matrix Set) - $ {X}^{k + 3} = V \hat{D} {V}^{T} $.
    Where $ \hat{D}_{ij} = \max \left( {D}_{ij}, 0 \right) $ where $ D $ is the Diagonal Matrix of Eigen Values of the Eigen Decomposition of $ {X}^{k + 2} $. Basically rebuilding $ {X}^{k + 2} $ by using only its Eigen Vectors which corresponds to positive eigen values.

enter image description here

The full MATLAB code with CVX validation is available in my StackExchnage Mathematics Q1891878 GitHub Repository.

$\endgroup$

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.