Formal demonstration that minimizing the free energy equals maximizing the entropy I never had great intuition when it came to thermodynamic concepts and potentials even though reading a textbook and completing the exercises has never been a huge problem.
In one of them, I was asked to show that maximizing the Gibbs entropy $$-\sum_n p_n \text{ln}(p_n)$$ under the constraints of normalization $$\sum_n p_n =1$$ and the existence of a fixed average energy $\sum_np_nE_n =E^*$ gives the canonical ensemble, ie: $$p_n=\frac{e^{-\beta E_n}}{\sum_ne^{-\beta E_n}}$$. And then I am supposed to show that maximizing the entropy is equivalent to minimizing the free energy. It's quite evident looking at its definition: $$F= E -TS$$ At fixed T and E, the minimum of T matches the maximum of S (I assume S to be positive).
But is there an explicit variational derivation of this result? For example, by rewriting a Lagrangian with F as a function of $p_n$ (maybe something else than replacing E and S by their definition?)
 A: A solution to your exercise is obtained by using the method of lagrange multipliers.
The constraints we have to satisfy are three:
1) $max_{P_j} S[p]$
2) $\sum_{j} P_j E_j = E$
3) $\sum_{j} P_j =1$
Choosing as variation parameters $\lambda$ and $\gamma$, calculations follow as:
$S_{\lambda,\gamma}=-\sum_{j} P_j ln{P_j} + \lambda(\sum_{j} P_j E_j - E)+\gamma(\sum_{j} P_j -1)$
$\frac{ \partial S_{\lambda,\gamma} }{ \partial{P_j} }=0\Longrightarrow -ln{P_j}-1+\lambda E_j+\gamma=0 \Longrightarrow P_j=\frac{ e^{- \lambda E_j} }{ e^{1-\gamma} }$
Calling $Z$ the normalization constant we have:
$P_j= \frac{ e^{-\lambda E_j} }{Z}$
$\sum_{j} P_j=1 \rightarrow e^{1-\gamma}=\sum_{j}e^{-\lambda E_j}:=Z $
The values of the $P_j$ maximize entropy since:
$\frac{ \partial^2 S_{\lambda , \gamma}}{ \partial P^2_j}=\frac{-1}{P_j}$
The parameter $\lambda$ can be determined from:
$\frac{ \sum_{j} E_j e^{-\lambda E_j} }{ Z } = E$
Now i will try to show how the parameter $\lambda$ can be interpreted as the inverse of temperature. Let's introduce the function $F(\lambda , E_j ):=ln{Z}$. We have:
$dF=\frac{\partial F}{\partial \lambda} d\lambda + \sum_{j} \frac{\partial F}{\partial E_j} dE_j=-Ed\lambda-\lambda \sum_{j} \frac{N_j}{N} dE_j $ where $P_j=\frac{N_j}{N}$
The last formula can be rewritten as:
$d(F+E\lambda)=\lambda(dE-\sum_{j} \frac{N_j}{N} dE_j):=\lambda dQ$
The last association follows from the physical fact that (looking from the point of view of quantum mechanics if you like) $-\sum_{j} \frac{N_j}{N} dE_j$ can be interpreted as the work done on the system to vary the energy levels from $E_j$ to $E_j+dE_j$ and $dE$ is the variation of internal energy. So $dE-\sum_{j} \frac{N_j}{N} dE_j$ is the quantity of heat $dQ$ exchanged by the ensemble with the outer.
Since we only have an exact differential involving heat from thermodynamics we can conclude that $\lambda=1/T$
Now we can define:
$f:=\frac{-1}{\beta} ln{Z}=E-TS$
So the maximum values of the entropy are embedded in the definition of free energy and they determine the minimum value of it.
The same procedure applies if we start from the free energy:
Constraints: $E=\sum_{j} P_j E_j$ and $\sum_{j} P_j = 1$
Parameter as lagrange multiplier: $\mu$
$f_\mu=\sum_{j}P_jE_j+T\sum_{j}P_j ln(P_j)+\mu(\sum_{j} P_j -1)$
$\frac{\partial f}{\partial P_j}=E_j + T ln{P_j} + T + \mu =0 \Longrightarrow P_j=e^{\frac{-E_j}{T}} e^{\frac{\mu}{T}-1} $
$\sum_{i}P_i=1 \rightarrow e^{\frac{-\mu}{T}-1}=\frac{1}{\sum_{i} e^{\frac{-E_i}{T}} }:=\frac{1}{Z} \Longrightarrow P_i= \frac{e^{\frac{-E_i}{T}}}{Z}$
A: Optimizing $S$ is the same as optimizing a monoton function of it, so everything you'd do would be running in circles. The $p_n$ enters the formalism exactly in the entropy definition, where through the sum $\Sigma_n$, the $n$'s are "integrated out". The most microscopic object, which relates to the "non-microcanonical" potentials is the partition function 
$$Z=\Sigma_n\ \text{e}^{-\beta E_n},$$ 
and you can recast the free energy using this quantity as
$$F=-kT\ \text{log}(Z).$$
But this identification in terms of $Z$, motivated by phenomenological thermodynamics of equilibrium systems, already assumes you found your optimum $p_n\propto \text{e}^{-\beta E_n}$. The difficulting to abstract $F$ in another way, e.g. terms of probabilies of subsystems as you suggest, is that it inherently depends on $T$, and replacing that would just end up with a function of $S$.
Regarding interpretation, I've lost some words on thermodynamical potentials here.
A: I am not going to spend a lot of time on this, but what you want to do is show that assuming a uniform distribution of probability causes the second derivative of probability as a function of n to go to zero:
$$\dfrac{\partial^2 p}{\partial n^2}=0$$
A simple graphical display shows this occurs when the accumulation in p-n space is a straight line

Intuitively this can be interpreted in functional terms. Since the second derivative is zero, the straight line in our graph represents a critical function in the function space of monotonically increasing functions.  It also represent a type of minimum, since the change in area under the curve with respect to changes of ordering is zero, e.g.
$$\dfrac{\partial A}{\partial s} = 0$$
Where I define $s$ as the sequence or order of the component probabilities and $A$ is area under the curve.  As such, it is the curve that is conservative with respect to ordering.
