This is a Community Wiki Solution.
Feel free to edit and add.
I will point up and mark solution for any other solution made by the community.
KKT
The Lagrangian is given by:
$$ L \left( y, \lambda \right) = \frac{1}{2} {\left\| y - x \right\|}^{2} + \mu \left( {e}^{T} y - k \right) - {\lambda}_{1}^{T} y + {\lambda}_{2}^{T} \left( y - e \right) $$
The KKT Constraints:
\begin{align}
\left( 1 \right) \; & {\nabla}_{y} L \left( y, \lambda \right) = y - x + \mu e - {\lambda}_{1} + {\lambda}_{2} & = 0 \\
\left( 2 \right) \; & {\nabla}_{\mu} L \left( y, \lambda \right) = {e}^{T} y - k & = 0 \\
\left( 3 \right) \; & -{\lambda}_{1}^{T} y & = 0 \\
\left( 4 \right) \; & {\lambda}_{2}^{T} \left( y - e \right) & = 0 \\
\left( 5 \right) \; & {\lambda}_{1} & \geq 0 \\
\left( 6 \right) \; & {\lambda}_{2} & \geq 0
\end{align}
Multiplying $ \left( 1 \right) $ by $ {e}^{T} $ and using $ \left( 2 \right) $ yields:
$$ {e}^{T} y - {e}^{T} x + \mu {e}^{T} e +{e}^{T} {\lambda}_{2} \Rightarrow \mu = \frac{ {e}^{T} x - k }{ n - {e}^{T} {\lambda}_{1} + {e}^{T} {\lambda}_{2} } $$
Plugging the result into $ \left( 1 \right) $ yields
Seems to be hard to get analytic solution.
Any other way to solve this system of equations?
Under Work...
Feel free to continue.
Projected Subgradient
Dual Projected Sub Gradient
Given a Problem in the form:
\begin{align*}
\arg \min_{x} & \quad f \left( x \right) \\
s.t. & \quad {g}_{i} \left( x \right) \leq 0 , \; i = 1, 2, \cdots, m \\
& \quad x \in \mathcal{S}
\end{align*}
Where
- $ \mathcal{S} \in \mathbb{E} $ is Convex.
- $ f : \mathbb{E} \rightarrow \mathbb{R} $ is convex.
- $ {g}_{i} : \mathbb{E} \rightarrow \mathbb{R} $ is Convex.
Then, from Amir Beck's Lecture Notes, The Dual Projected Sub Gradient is given by:
- Pick $ {\lambda}^{0} \in {\mathbb{R}}_{+} $.
- For $ k = 0, 1, 2, \cdots $ Calculate:
- $ {x}_{k} = \arg \min_{x \in \mathcal{S}} \left\{ f \left( x \right) + \sum_{i = 1}^{m} {\lambda}_{i}^{k} {g}_{i} \left( x \right) \right\} $.
- $ {\lambda}_{i}^{k + 1} = {\left[ {\lambda}_{i}^{k} + {t}_{k} \frac{ {g}_{i} \left( {x}^{k} \right) }{ {\left\| {g}_{i} \left( {x}^{k} \right) \right\|}_{2} } \right]}_{+} $.
In this problem $ f \left( y \right) = \frac{1}{2} { \left\| y - x \right\| }^{2} $, $ i = 1, 2, ..., n, \; {g}_{i} \left( y \right) = -{y}_{i} $, $ i = n + 1, n + 2, ..., 2n, \; {g}_{i} \left( y \right) = {y}_{i} - 1 $ and $ \mathcal{S} = \left\{ x \mid {e}^{T} x = k \right\} $.
The Sub Problem $ {x}_{k} = \arg \min_{x \in \mathcal{S}} \left\{ f \left( x \right) + \sum_{i = 1}^{m} {\lambda}_{i}^{k} {g}_{i} \left( x \right) \right\} $ should be solved using Projected Sub Gradient.
In this case the Projection Operator is given by $ {\mathcal{P}}_{{e}^{T} x = k} \left( x \right) = x - e {\left( {e}^{T} e \right)}^{-1} \left( {e}^{T} x - b \right) $.
The Gradient of $ L \left( y, \lambda \right) = \frac{1}{2} { \left\| y - x \right\| }^{2} + \sum_{i = 1}^{m} {\lambda}_{i} {g}_{i} \left( x \right) $ is given by $ {\nabla}_{y} L \left( y, \lambda \right) = y - x + {\left[ \left( {\lambda}_{n + 1} - {\lambda}_{1} \right), \left( {\lambda}_{n + 2} - {\lambda}_{2} \right), \cdots, \left( {\lambda}_{2n} - {\lambda}_{n} \right) \right]}^{T} $.
This is a MATLAB code which implements the method:
function [ vY ] = ProjX( vX, numElmntsK )
%UNTITLED6 Summary of this function goes here
% Detailed explanation goes here
numDim = size(vX, 1);
vE = ones([numDim, 1]);
hProjFunc = @(vY) vY - (vE * ((vE.' * vE) \ ((vE.' * vY) - numElmntsK)));
hGFunc = @(vY) [-vY; (vY - vE)];
hGradLFun = @(vY, vLambda) vY - vX - vLambda(1:numDim) + vLambda((numDim + 1):(2 * numDim));
% numIterDual = 6000;
numIterProj = 150;
vY = vE;
vY = numElmntsK * (vY / sum(vY));
vLambda = 0.5 * ones([(2 * numDim), 1]);
stepSize = 0.0075;
minConstVal = inf;
minConstThr = 0.00005;
while(minConstVal > minConstThr)
% Dual Projected Sub Gradient
for jj = 1:numIterProj
% Projetcted Sub Gradient
vY = hProjFunc(vY - (stepSize * hGradLFun(vY, vLambda)));
end
vLambda = vLambda + (stepSize * hGFunc(vY) / norm(hGFunc(vY), 2));
vLambda = max(vLambda, 0);
minConstVal = abs(sum(vLambda .* hGFunc(vY)));
end
end
Let $f:2^{\{1,2\}} \rightarrow \mathbb{R}$ with
$$f(\{1\})=100$$
$$f(\{2\})=\frac{1}{2}$$
$$f(\{1,2\})= 101$$
$$f(\emptyset)=0$$
$f$ is supermodular. The solution of
\begin{equation}
\max_{S \subseteq V}\, f(S)\quad \text{s.t}\, \lvert S \rvert \leq k
\end{equation}
for $k=1$ is $\{1\}$ with $f(\{1\})=100$.
If we now minimize $-f$ and turn around the constraint direction, we obtain the following problem:
\begin{equation}
\min_{S \subseteq V}\, -f(S)\quad \text{s.t}\, \lvert S \rvert \geq 1
\end{equation}
Now, we obtain the optimum is at $S=\{1,2\}$. Thus, the two problems are not equivalent and just switching the constraint direction is not enough.
Best Answer
To your first question: It seems there are some implicit restrictions that should be made explicit. Are there nonnegativity constraints on the variables $y_{l,c}$? In order to guarantee a solution, you must have positive lower bounds on $p_{l,c}$, as otherwise the logarithm blows up. (Constraints of the form $p_{l,c} > 0$ are frowned upon in optimization; $p_{l,c} \ge \epsilon$ is usually preferred.)
Assuming reasonable assumptions as outlined above ($I_{l,c} > 0$), your problem is a convex optimization problem. (The objective function is concave, but the corresponding minimization problem $\min (-f)$ --- see your second question --- is convex.)
I am not sure why you want to use a particular algorithm. GRG is probably not too bad, but there are other algorithms out there. Are you planning to implement this yourself? (That would be an entirely different question.) The best approach is likely to depend on $L$ and $C$. For a start I would recommend either just a simplistic approach like the built-in Excel solver or perhaps the Frontline solver or OpenSolver add-ins for Excel, or an open-source package such as Ipopt.