Geometric computation and plotting with Yalmip

Yalmip is modeling language in Matlab for mathematical optimization (or programming in the language of Operation Research). There are many excellent optimization solvers out there, for Matlah or not, commercial or free or open source. However, each of them uses a different programming and modeling interface. Some are quite difficult to use. Most require you to transform your optimization problems into a standard form to be able to solved by the solver. Thus, it is unintuitive. Furthermore, in many practical applications, you must apply many technical tricks to transform or approximate your problems just to be able to solve them (efficiently). Manually doing this is both time-consuming and error-prone, and you may not know all the tricks, especially if you are not an expert.

Yalmip solves these difficulties by providing a consistent, well-designed, intuitive, and easy-to-use modeling language. The language is symbolic and uses a syntax very close to the mathematical languge used to formulate optimization problems. It also transforms your problems automatically, applies many useful tricks accurately, then calls external solvers to solve them for you. More information can be found on its website.

I have just discovered that Yalmip can also plot (constraint) sets. Basically, it samples the variable space with a grid and solves a sequence of optimization problems to calculate the feasible points. Then a (bounded convex) representation of the constraint set can be formed and plotted. This has been available in Yalmip for quite a while, but I only discovered it when I needed to plot a complex set and MPT could not handle the task. This feature is very helpful. To plot standard geometric objects such as a polytope or an ellipsoid, Yalmip is much slower than a specialized toolbox like MPT, but it is more flexible and more powerful. Therefore, you should stick to specialized toolboxes for standard objects, and use Yalmip for the rest.

Another more useful feature of Yalmip is the ability to perform geometric computation, such as Minkowski sum/difference and contracting/expanding sets. Examples can be found here. Although these computations can be performed by specialized toolboxes (MPT, ellipsoid), they are limited in capability. For example, using the polytope class in MPT, you can only compute the Minkowski difference between polytopic sets. Minkowski difference between a polytope and an ellipsoid (essentially shifting and contracting the polytope in a metric defined by the ellipsoid) can however be carried out by Yalmip, using its robust optimization framework and the robustify command. Another example is the range computation of a polytopic set, i.e. \{ y | y = A x + b, x \in P\} where P is a polytope, A and b are given matrix and vector. MPT can only compute this set if A is non-singular (and of course, square). With Yalmip, you are able to compute this set when A is singular and even non-square. Depending on the set and the dimensions you are working on, the computation can be very heavy and time-consuming, but at least it is possible.

All these computations will be implemented in a collection of Matlab functions for my research, and will be published on my github account.

This entry was posted in Matlab, Research and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s