The square $[0,1]^2$ is cut into some number of regions by $n$ random lines. We can chose these random lines by randomly picking a point on one of the four sides, picking another point randomly from any of the other three sides and then connecting the dots. We do this $n$ times.
What is the probability after $n$ lines that the largest region has area $1/2$ or greater?
(A follow-up question: Is the circle in the square best at avoiding random lines?)
Aaron and fedja have pointed out that the problem is equivalent to finding the convex region in the plane with area $1/2$ with the highest probability that a random line does not intersect it.
The optimal convex region $\Delta$ has boundary a union of eight segments, each satisfying a differential equation from a certain one-parameter family, that hence are smooth.
Pick a corner of the square, choose coordinates so that that corner is point $(0,0)$, and consider the segment of the boundary $C$ of $\Delta$ whose tangent lines touch the two sides of the square adjacent to that point.
If we write this segment of $C$ as the graph of a decreasing function $y(x)$, then the tangent line at the point $(x,y)$ connects the points $\left(x- \frac{y}{\dot{y}},0\right)$ and $\left(0, y+ \dot{y}x \right)$ on these two sides, where $\dot{y}$ is the derivative with respect to $x$. So if we plot the region in the $a,b$ plane consisting of those $(a,b)$ such that the line connecting $(a,0)$ and $(b,0)$ does not intersect $\Delta$, the boundary of that region is the parameteric curve $\left(x- \frac{y}{\dot{y}}, y- \dot{y}x \right)$ and thus the area of the region is $$ - \int \left(x- \frac{y}{\dot{y}} \right) \frac{d}{dx} \left(y - \dot{y}x \right) dx$$
$$= - \int \left(x- \frac{y}{\dot{y}} \right) \left(\frac{dy}{x} - \ddot{y}x - \dot{y} \right) dx$$
$$= \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$
the negative sign being because $\left(y- \dot{y}x \right)$ is a decreasing function of $x$ by convexity.
So we are optimizing $$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$ subject to an upper bound on $ \int y dx$ which by Lagrange multipliers is equivalent to optimizing
$$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx - \lambda \int y dx$$
for some $\lambda>0$.
By calculus of variations, if we set $F(y, \dot{y}, \ddot{y}) = x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) - \lambda y$, then the optimal value of $y$ satisfies $$\frac{dF}{dy} - \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y}} \right) \right) =0$$
We can evaluate $$\frac{dF}{d \ddot{y}} = x^2 - \frac{xy}{\dot{y}}$$ $$\frac{d}{dx} \left(\frac{dF}{d\ddot{y}} \right)= 2x-\frac{y}{\dot{y}} - x + \frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{ d\dot{y}} =\frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y} }\right) = \frac{y}{\dot{y}} -x $$ $$ \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \frac{dy^2}{dx^2}}\right) \right) = 1 - \frac{y \ddot{y}}{\left( \dot{y}\right)^2} -1$$
$$\frac{dF}{dy} = - \lambda - x \frac{\ddot{y}}{\dot{y}}$$
so the differential equation is
$$ - \lambda - x \frac{\ddot{y}}{\dot{y}} + \frac{y \ddot{y}}{\left( \dot{y}\right)^2} =0$$
or
$$ \lambda \left( \dot{y}\right)^2 +( x \dot{y} -y )\ddot{y} =0$$
If we let $t= \dot{y} \frac{x}{y}$ be the dimensionless derivative, then $\dot{y} = t\frac{y}{dx}, \ddot{y} = \frac{d}{dx}\left( t\frac{y}{x}\right)= \dot{t}\frac{y}{x} + t^2 \frac{y}{x^2} - t \frac{y}{x^2} =\frac{y}{x^2} \left( \frac{dt}{d\log x} +t^2-t\right)$
so we can write the equation (ignoring factors of $y$ or $x$) as
$$ \lambda t^2 + (t-1) \left( \frac{dt}{d\log x} + t^2-t \right) =0$$
$$\frac{dt}{d \log x} = - \lambda \frac{t^2}{t-1} + t -t^2 $$
so either we have $t$ a constant solution of $(t^2-t)(t-1) + \lambda t^2 =0$ with $y$ a constant times $x^t$ or we can express $\log x$ and $\log y$ as integrals of rational functions of $t$.
$$\log x = \int \frac{1}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$
$$\log y = \int \frac{t}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$
Matt F. in the comments did the integrals and found that the formulas, while explicit, are quite nasty. Perhaps this can be fixed by changing the parameter, but this seems unlikely.
It should be possible to do similar calculations for the other kind of segment, but the next step would be to calculate the different ways these segments can be stitched together, which amounts to solving an equation involving eight of these explicit solutions. That seems difficult unless the solutions are really nice - although I'm sure it can be done with the aid of a suitable computer algebra system.
UPDATED AGAIN Here are some lower bounds and the results of $10^6$ random trials. The $1$-dimensional case is quite informative and is discussed at the end.
One way to get an exponential lower bound is to choose an area $1/2$ subset and find the chance that it remains intact after $n$ lines. A tilted square, the intact isosceles right triangle after the first line (if there is one), an optimal octagon and centered circle (in that order) give such bounds which are increasingly good. However an exponential model is not the right one to use.
The chance that a single line avoids the tilted square with corners $(1/2,0),(1,1/2),(1/2,1),(0,1/2)$ (of area $1/2$) is $1/6:$ With probability $1$, the point first chosen is not a corner of the original square or the tilted one. wlog it is on the left half of the bottom. Then the second point needs to be on the lower half of the right side. The chance of this is 1/6. So the chance that none of $n$ lines cut the tilted square is $$\frac1{6^{n}}.$$
This can be improved to $$\frac4{6^n}=\frac2{3\cdot 6^{n-1}}$$ by considering instead isosceles right triangles. The chance that the first line crosses two adjacent sides is $2/3.$ If this does happen then one of the diagonals misses this line and splits the square into two isosceles right triangles with area $1/2.$ One is cut and the other intact. For every subsequent choice the first point is outside the intact half with probability $1/2$ and the second with probability $1/3.$
Here is a certain octagon along with the circle with center $(\frac12,\frac12)$ and radius $\frac1{\sqrt{2\pi}}.$ 
I find that the octagon above is the best of its kind. I get that the probability it stays intact is about $$(\frac{2(0.4797667)}3)^n=0.31984^n.$$ The lower left corner is at about $(0.32606,0.11670).$
For the octagon, and also the circle, the exact probability of a line missing it can, in principle, be found using several integrals. They are not that nice so I evaluated them numerically. The probability of a line missing the circle is about $.34470989$ hence $$0.34470989^n.$$
Perhaps some shape of the form $t$circle+$(1-t)$octagon beats the circle. However another octagon might do even better for that process.
It is not all that hard to randomly generate lines. One need only keep track of the vertices of the one maximum area region. Then a new line either misses it or intersects two of the sides creating two new vertices and two regions.
In $10^6$ random trials it happened $4$ times that only the $20$th line left all regions with size less than $\frac12.$ Of course the first line is always OK. $187209$ times the second line was fatal, the other $812791$ it wasn't. The counts were
$$[1, 1000000], [2, 812791], [3, 580116], [4, 376623], [5, 228824], [6, 131445],$$$$ [7, 72077], [8, 38186], [9, 19805], [10, 10009], [11, 4852], [12, 2299],$$$$ [13, 1070], [14, 540], [15, 259], [16, 113], [17, 47], [18, 18], [19, 4]$$
As suggested by Emil, the correct model is possibly of the form $f(n) c^n$ for some $f(n)$ with sub-exponential growth. This is supported by the following:
Consider the similar problem in $1$-dimension:
The interval $[0,1]$ is divided into $n+1$ subintervals by $n$ random points. What is the probability that the longest subinterval has length at least $\frac12?$
It turns out that the exact answer is $\frac{n+1}{2^n}.$ It is easiest to prove the more general form: Given that the largest currently surviving interval has length $\frac12+x,$ the probability of surviving the next $n$ random points is $$\frac{n(2x-1)+1}{2^n}.$$
Given this exact result, we don't need an upper bound. But getting one helped me understand Christian's method: I claim that an upper bound, valid for all $n$ is $$N\left(\frac12+\frac1N\right)^n.$$ Fix an integer $N>2$ and consider the $N$ intervals $I_t=[\frac{t}{2N},\frac{t}{2N}+\frac{N-1}{2N}]$ with $1 \leq t \leq N.$ A subinterval $[s,s+\frac12]$ contains one of these (move each endpoint inward to the nearest $\frac{a}{2n}.$) If some interval of length $\frac12$ stays undivided, so does at least one of the $I_t.$ The chance that any particular one stays undivided by $n$ random points is $(\frac12+\frac1N)^n.$ So the chance that at least one does is less than $N\left(\frac12+\frac1N\right)^n.$ This is an upper bound on what we seek.
Thinking of numbers on a clock-face, say that one of these lines is:
Each of these figures shows an 8-2 slash (in red), an 11-5 slash (in blue), and the acceptable ranges for endpoints (in green).
An 8-2 slash and an 11-5 slash together divide the square into pieces of area at most 227/455, which is less than 1/2, and which is the case shown in the second figure. So the probability that $n$ lines leave an unbroken region of area greater than 1/2 is at most
$$P(\text{no 8-2 slashes}) + P(\text{no 11-5 slashes}) - P(\text{no 8-2 slashes & no 11-5 slashes}).$$
Now consider the probability of an 8-2 slash. The probability that a randomly chosen line goes from the top to the bottom is $1/6$. The probability that such a line is an 8-2 slash is $(3/7)^2$, so the overall probability of an 8-2 slash is $3/98$. This is the same as the probability of an 11-5 slash.
Thus the probability of an unbroken region of area greater than 1/2 is at most $$\left(1-\frac{3}{98}\right)^n + \left(1-\frac{3}{98}\right)^n - \left(1-\frac{6}{98}\right)^n = 2\left(\frac{95}{98}\right)^n - \left(\frac{92}{98}\right)^n .$$
This is enough to establish an exponential upper bound.
A crude, but easy to prove (given fedja's comment to Aaron's answer) upper bound is $(2/3+\epsilon)^n$ for all $\epsilon>0$ and for large $n$.
This follows by just observing that if we fix any point on the boundary and connect it to one or two arcs whose combined length is more than $2/3$ of the remaining three sides, the area covered is always $>1/2$. So for any convex area $|A|\ge 1/2$ whatsoever, the probability of not hitting $A$ with a random line is $p_A\le 2/3$.
For a given $\delta>0$, we can find finitely many sets $A_1,\ldots , A_N$ (convex polygons, let's say), $|A_j|\ge 1/2-\delta$, such that every convex $|A|\ge 1/2$ contains an $A_j$. (This seems intuitively clear, but to be perfectly honest, I didn't think very hard about this; it's similar in spirit to compact subsets being a compact space themselves with respect to Hausdorff distance.)
As discussed above, the probability of a random line not intersecting $A_j$ is $\le 2/3+\epsilon$, so the claim follows.
This is really a comment to ChristianRemling that requires a figure, so please don't down-vote it.
If "all lines connect the same two adjacent edges" (as you write), then the probability a region of area greater than $1/2$ survives is always 1.0, as illustrated by this figure:
Note that every tight bound (for the full problem with arbitrary edge connections) should yield for $n=1$ that the probability is $1.0$. (Several proposed answers do not have that value.) The lowest lower bound for $n=2$ is clearly $0$, as it is possible the two lines split the area into regions each having area less than $1/2$.
Some background information: What is the average size of the largest remaining region after the first cut?
One of the sides is chosen for the first point, and (without loss of generality) we rotate the figure so that this is at the bottom. Call the position of its end $x_1$. There are three remaining sides, each chosen with probability $1/3$. The point on one adjacent side (see left figure) is at $x_2$ and the area of the largest portion is $1 - x_1 x_2/2$. (The calculations for the other adjacent side are the equivalent.) The opposite side (see right figure) creates two areas, and we choose the largest. The expected area of the largest surviving region is thus:
${1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 \max({1 \over 2} |x_2-x_1| + x_1, 1 - {1 \over 2} |x_2-x_1| + x_1)\ dx_1 dx_2 \\ = {1 \over 3}{7 \over 8} + {1 \over 3}{7 \over 8} + {1 \over 3}{2 \over 3} = {29 \over 36}$.
Now one might make the very oversimplified assumption that the shapes of such regions on successive cuts are independent (they are not!) and compute the expected "surviving" largest area by intersection areas, then compute the probability this area is greater than $1/2$ as a function of $n$.
