Multi-scale texture synthesis is a rising research in recent years. There are two shortcomings: First, the exemplar design is very difficult, Second, Multi-scale texture synthesis uses pixel matching. Pixel matching can not capture the big structure information of the texture and it requires significant resources. A new multi-scale texture synthesis algorithm based optimization was proposed. The algorithm designs input exemplar textures using graph structure, constructs an exemplar-relation graph, adopts patch matching synthesis, introduces optimization to keep patch matching properly, and the size of the block can be adjusted and a jitter function was proposed. The algorithm absorbed the random characteristic of the pixel matching, and enhanced synthesis efficiency. Experimental results show that the method is effective.