Return to Revisions

Yes, $y$ can violate the constraints. The one about box constraints ($0 \leq y \leq 1$) is OK by how $y$ is defined, the problem is the other one ($A^T y \leq b$). First I tried getting a feasibility proof unsuccessfully, then I decided to build a reproducible counterexample using Python:

import cvxpy as cp
import numpy as np

# Generate a random instance according to the conditions stated by OP (small c, larger n).
n = 150
c = 2

# Build p, A and b, which are elementwise positive.
np.random.seed(1)
p = np.random.uniform(0, 1, n)
A = np.random.uniform(0,1, (n,c))
b = np.random.uniform(0,1, c)

# Define and solve the CVXPY problem. 
# Note that we'll solve the primal problem only to get the dual variable lambda^*
x = cp.Variable(n)
prob = cp.Problem(cp.Maximize(p.T@x),
                 [A.T @ x <= b, 
                  x <= 1,
                  x >= 0 ])
prob.solve()

print("A dual solution is")
print(prob.constraints[0].dual_value)

# Construct the suggested heuristic solution, starting from the dual solution:
lambda_opt = prob.constraints[0].dual_value
r = p - np.matmul(A, lambda_opt)
y = (r > 0).astype(int)

# Verify feasibility for y:
print("Check nonpositive:", (A.T @ y) -b )

This piece of code outputs the array [0.138349, 0.11109537] at the last line, therefore, $A^T y - b \leq 0$ doesn't hold and $y$ is unfeasible. As a conclusion, without further information or hypotheses about $A, b$ and $p$, the proposed approach won't work in general.

Regarding the second part of your question, it reminds me about Approximation Algorithms. I cite from the Wikipedia article:

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one.

Assuming the problem of finding $\lambda^*$ easier as you mention, there are two scenarios:

1. If you can find $\lambda^*$ by other means and not solving the linear problem nor its dual, then you could use complementary slackness conditions to try find $x^*$. This somewhat relates to what you are building with the binding/nonbinding dual constraints (i.e. $r_i$ values). There are several examples available on how to procede, like here, here or here.

2. If the dual problem is "easier" to solve, your approach sounds similar to using a primal-dual method. You can read an explanation on how it works at Section 5.1 of this document, while the original source where it was proposed for solving linear programs is several decades old.¹

The general idea will be as follows:

1. Find a feasible dual solution $\lambda$.
2. Given $\lambda$, find some $x$ that minimizes the violation of complementary slackness in the primal problem. (This is the step that reminds me of what you are trying to approach when constructing $y$).
3. If complementary slackness holds, $y$ is optimal, and the algorithm terminates.
4. Otherwise, change $\lambda$ so as to improve the dual objective, and go to 2.

¹ Dantzig, George Bernard, Lester Randolph Ford Jr, and Delbert Ray Fulkerson. A PRIMAL--DUAL ALGORITHM. No. P-778. RAND CORP SANTA MONICA CA, 1956.