{"action":"opened","issue":{"url":"https://api.github.com/repos/RobotLocomotion/drake/issues/3888","repository_url":"https://api.github.com/repos/RobotLocomotion/drake","labels_url":"https://api.github.com/repos/RobotLocomotion/drake/issues/3888/labels{/name}","comments_url":"https://api.github.com/repos/RobotLocomotion/drake/issues/3888/comments","events_url":"https://api.github.com/repos/RobotLocomotion/drake/issues/3888/events","html_url":"https://github.com/RobotLocomotion/drake/issues/3888","id":184932386,"number":3888,"title":"Bringing SDP to Drake MathematicalProgram","user":{"login":"hongkai-dai","id":6314000,"avatar_url":"https://avatars.githubusercontent.com/u/6314000?v=3","gravatar_id":"","url":"https://api.github.com/users/hongkai-dai","html_url":"https://github.com/hongkai-dai","followers_url":"https://api.github.com/users/hongkai-dai/followers","following_url":"https://api.github.com/users/hongkai-dai/following{/other_user}","gists_url":"https://api.github.com/users/hongkai-dai/gists{/gist_id}","starred_url":"https://api.github.com/users/hongkai-dai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hongkai-dai/subscriptions","organizations_url":"https://api.github.com/users/hongkai-dai/orgs","repos_url":"https://api.github.com/users/hongkai-dai/repos","events_url":"https://api.github.com/users/hongkai-dai/events{/privacy}","received_events_url":"https://api.github.com/users/hongkai-dai/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-10-24T19:28:45Z","updated_at":"2016-10-24T19:28:45Z","closed_at":null,"body":"<H3> Challenge </H3>\r\nFor semi-definite programming problem, the problem setting can be quite different from other types of problems. The big difference is that \r\n\r\n1. The decision variable is a symmetric matrix, not a vector. \r\n2. The constraint \"X is positive semi-definite\" is not a constraint we can \"evaluate\", with smooth gradient.\r\n\r\n<H3> Proposed Solution </H3>\r\n\r\n1. Add a new type `SymmetricMatrix` to `DecisionVariable` class. Internally we store the upper-triangular part of this symmetric matrix as a vector, with size `n(n+1)/2`, where the symmetric matrix is of size `n x n`.\r\n2. Add the following function to `MathematicalProgram.h` \r\n   \r\n    ```\r\n    const DecisionVariableView MathematicalProgram::AddSymmetricMatrixVariables(int num_rows, const string& name=\"x\")\r\n    ```\r\n3. In the `Constraint` class, add a `PositiveSemidefiniteConstraint`, which evaluates the smallest eigen value of the matrix. This is a non-differentiable function.\r\n4. In the `Constraint` class, add a `LinearAndSymmetricMatrixInnerProductConstraint`, which evaluates the inner-product of matrix `A` and a symmetric matrix `X`, and vector `a` and `x` as\r\n\r\n    ```\r\n    lb <=  a'*x + trace(A'*X) <= ub\r\n    ```\r\n5. The semi-definite programming problem is defined in the following primal form\r\n   \r\n   ```\r\n   min_(x, X)  c'*x + trace(C'*X)\r\n   s.t      lb(i) <= ai'*x + trace(Ai'*X) <= ub(i)\r\n             x in K1\r\n             X is p.s.d\r\n   ```\r\n   where `K1` is some proper cone for vector `x`."}}
{"actor":{"display_login":"hongkai-dai"}}