Handle constraints and nonsmooth penalties explicitly

Try

Minimize (x−2)² over the interval [0,1]. Starting at zero with gradient step 1/2 produces the infeasible raw point two. Projecting back gives one, the constrained optimum. The projection is part of the algorithm, not an after-the-fact cosmetic correction. At the constrained optimum the ordinary gradient remains nonzero, so a stopping rule based only on its norm would incorrectly demand further unconstrained movement beyond the feasible set.

Predict

Predict the correct fixed-point condition: x=P_C(x−α∇f(x)) for a positive step α. The projection characterization converts it to ∇f(x)·(y−x)≥0 for every feasible y. For convex differentiable f, the tangent lower bound then proves global optimality. For nonconvex f, it is a first-order constrained stationarity condition only. Geometry and objective convexity perform separate roles in this argument.

Experiment

Inspect the proximal operator of the absolute-value penalty. For τ=1, minimize (1/2)(x−z)²+|x| for different input values z.

Input z	Proximal minimizer	Mechanism
−3	−2	Move one unit toward zero
−1/2	0	Zero lies in the subgradient interval
2	1	Move one unit toward zero

Derive the first and third rows by differentiating on the appropriate sign region. At zero, use the subgradient condition rather than pretending |x| has an ordinary derivative. The complete formula is sign(z)max(|z|−τ,0), called soft thresholding. Its flat middle region explains exact zeros in penalized solutions.

Understand

For a proper closed convex function h, its proximal map at z minimizes h(y)+(1/(2α))||y−z||² with α>0. The quadratic term gives a unique minimizer in finite dimensions under these standard assumptions. If h is the indicator of a nonempty closed convex set, taking value zero inside and positive infinity outside, the proximal map is Euclidean projection. Thus constrained and penalized steps share one mathematical construction.

For f+h with differentiable convex L-smooth f, proximal gradient minimizes the surrogate f(x)+∇f(x)·(y−x)+(1/(2α))||y−x||²+h(y). This is prox_(αh)(x−α∇f(x)). When 0<α≤1/L, the descent lemma makes the surrogate an upper bound on the true objective, with equality at the current point. Minimizing it gives objective descent. Under the usual convex assumptions and an existing minimizer, standard proximal-gradient convergence follows; a full rate proof additionally tracks a distance-to-solution inequality and telescopes it. The majorization calculation here explains why the step is sensible rather than asserting convergence from a decreasing plot alone.

Apply

For projected gradient, define a gradient mapping Gα(x)=(x−P_C(x−α∇f(x)))/α. It vanishes at the fixed-point condition, unlike the ordinary gradient at many boundary optima. In the opening example, x=1 yields a raw point two and projection one, so Gα=0 while f′(1)=−2. Explain which residual measures the constrained condition and why both should not be interpreted interchangeably.

If the feasible set is disconnected, projection can be nonunique and its convex variational inequality may fail. If h is nonconvex, the proximal subproblem can also have multiple solutions. These facts do not prove every nonconvex method fails, but they invalidate automatic reuse of the convex proof. Specify how a chosen branch is selected and what weaker conclusion, if any, is established.

Continue

State whether the difficult structure is a constraint or a penalty, and whether its proximal step is solved exactly or approximately. Continue to Integer relaxations, where a disconnected feasible set arises naturally from whole-number decisions. Convex relaxations will supply useful bounds, but projection or rounding will require new reasoning to recover a valid integer solution.