how to write largest circle inscribed inside a triangle as an optimization problem?

Question

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$.

My institution is to cast to problem using supporting hyperplane theorem , but I don't know how to write the equation .

Thanks !!

Answer 1

EDIT: Geez, I totally forgot that Section 4.3.1 of Boyd & Vandenberghe's book Convex Optimization shows how to compute the Chebyshev center of a polyhedron described by inequalities. The Chebyshev center is the center of the largest inscribed circle of the polygon; and the model that computes it gives the radius as well.

I could have skipped all of this development and gone right to the simplified circle case below. Sorry about that. I will leave it in for posterity and in case others are interested. But you can go right to Section 4.3.1 of the book, or the corresponding example in the CVX example library, to see this in action.

---

It is well known that the task of inscribing an ellipsoid with the largest possible volume in a polyhedron described by linear inequalities $$a_i^T x \leq b_i, \quad i=1,2,\dots, n$$ is a convex program. Section 8.4.1 of Boyd & Vandenberghe's book Convex Optimization describes just how to do this. The model looks like this: \begin{array}{ll} \text{maximize}_{B,d} & \log\det B \\ \text{subject to} & \| B a_i \| + a_i^T d \leq b_i, ~i=1,2,\dots, m \end{array} The variables are a symmetric, positive definite matrix $B$ and a vector $d$. (The positive definiteness of $B$ is implicitly constrained by the objective function, so you do not need to specify it as a constraint.)

The actual volume of the ellipse is $\det B$, but that's not concave. So $\log\det B$ is chosen instead because it is concave and it yields the same result. You can also use $(\det B)^{1/n}$, which is not only concave but SDP-representable as well, so more solvers are likely to be able to handle it.

The example in that section is included in the CVX example library, using the $(\det B)^{1/n}$ alternative. It looks like this:

cvx_begin
    variable B(n,n) symmetric
    variable d(n)
    maximize( det_rootn( B ) )
    subject to
       for i = 1:m
           norm( B*A(i,:)', 2 ) + A(i,:)*d <= b(i);
       end
cvx_end

Now of course, you don't want an ellipse, you want a circle. One way to look at it is that you're solving the same problem as before, only you are fixing the relative shape of $B$ by ensuring that $B=\beta I$, where $I$ is the identity matrix. You could just add $B=\beta I$ as a constraint into the above model, with $\beta$ as an additional variable. But a little more care lets us simplify the objective considerably, and the result is a linear program: \begin{array}{ll} \text{maximize}_{\beta,d} & \beta \\ \text{subject to} & \beta \| a_i \| + a_i^T d \leq b_i, ~i=1,2,\dots, m \end{array}

Here is the corresponding CVX model:

cvx_begin
    variable beta
    variable d(n)
    maximize( beta )
    subject to
       for i = 1:m
           beta * norm( A(i,:)', 2 ) + A(i,:)*d <= b(i);
       end
cvx_end