I'd say you are on the right track, but coming up with an optimal and/or efficient algorithm is another matter: it's a difficult problem. However, unless your interest is academic, a good-enough solution may suffice.
First, if you are not interested in coming up with your own solution, CGAL contains an algorithm for convex polyhedra decomposition already: http://doc.cgal.org/latest/Convex_decomposition_3/index.html
Now for the method; like many problems in 3D, it's often helpful to consider the 2D problem which is easier to understand. For 2D, the task is to identify reflex vertices, and split the polygon into two by creating a new edge (and possibly new vertices) from that reflex vertex, and continuing until you are left with no reflex vertices (and hence all-convex polygons).
Polygon Decomposition by J. Mark Keil contains the following algorithm (in unoptimised form):
diags = decomp(poly)
min, tmp : EdgeList
ndiags : Integer
for each reflex vertex i
for every other vertex j
if i can see j
left = the polygon given by vertices i to j
right = the polygon given by vertices j to i
tmp = decomp(left) + decomp(right)
if(tmp.size < ndiags)
min = tmp
ndiags = tmp.size
min += the diagonal i to j
Basically it exhaustively compares all possible partitions, and returns the one with the least diagonals produced. In this sense it is somewhat brute-force and optimal as well.
If you want "nicer looking" decompositions, that is ones that produce more compact shapes rather than elongated ones, you could also consider this one produced by Mark Bayazit, which is greedy (hence much faster) and looks nicer but has a few shortcomings. It basically works by trying to connect reflex vertices to the best one opposite to it, typically to another reflex vertex:
One of the shortcomings is that it ignores "better" decompositions by creating Steiner points (points that do not exist on an existing edge):
The problem in 3D can be similar; instead of reflex vertices, you identify "notch edges". A naive implementation would be to identify notch edges, and perform plane cuts on the polyhedron repeatedly until all polyhedra are convex. Check out "Convex Partitions of Polyhedra: a Lower Bound and Worst-Case Optimal Algorithm" by Bernard Chazelle for more details.
Note that this approach could produce worst case an exponential number of sub-polyhedra. This is because you could have degenerate cases like this:
But if you have a non-trivial mesh (think bumpy surface), you'll get poor results anyway. It's very likely that you'll want to do a lot of simplification beforehand, if you ever need to use this for complex meshes.