5 - Advanced Convex Optimization

Leave the polished solver output closed for a moment. Imagine instead that someone slides a result across the table and asks, “How do you know this is globally best?” This blog is our attempt to answer that question without hand-waving.

Linear, quadratic, and conic models gave us a useful vocabulary. This blog asks a deeper question: why can some large nonlinear-looking problems still be solved reliably, while apparently simpler ones trap us in poor local solutions? The answer is not the name of a solver. It is convex structure.

We will build that structure carefully. We will prove convexity rather than guess it, derive duals rather than quote them, and connect each algorithm to the geometry it exploits. Then we will return to the 2024 CUMCM crop-planning problem and rebuild its uncertainty layer using scenarios and conditional value-at-risk (CVaR). The aim is not to make the paper look more advanced. The aim is to make the promise “this decision remains acceptable when the data are wrong” mathematically testable.

The advanced-convexity habit

Do not ask “Which algorithm should I mention?” Ask: What function and set do I have? What curvature can I prove? What certificate will tell me that I am done? The algorithm comes after those answers.

1. Convex Sets, Functions, and Epigraphs

A set is convex when every segment between two points stays inside:

Half-spaces, affine sets, norm balls, positive-semidefinite cones, and intersections of convex sets are convex. A union of convex sets is generally not. The set happens to be convex after recognizing it as the epigraph of ; a picture alone is not enough.

A function is convex if

Geometrically, the chord lies above the graph. The epigraph

is convex exactly when is convex. This observation converts many nonlinear objectives into constrained forms: minimizing is equivalent to minimizing subject to .

If is differentiable, convexity is equivalent to the global first-order lower bound

The tangent plane never rises above a convex function. If is twice differentiable on an open convex domain, is convex iff everywhere.

Proof examples

For log-sum-exp,

define softmax weights . Then

where . The Hessian is a covariance matrix, hence positive semidefinite.

For on , the directional second derivative is

so it is convex. This barrier is central to semidefinite and interior-point methods.

Useful closure rules include nonnegative weighted sums, pointwise maxima, affine composition , and partial minimization under suitable conditions. Composition must be checked carefully: a convex function composed with a convex inner function is not automatically convex unless monotonicity conditions hold.

Convexity check

Is convex? Try the Hessian test. Is convex on ? If not, is it concave? The outer square root is the same, but the inner structure changes the answer.

2. Strong Convexity, Smoothness, and Conditioning

A differentiable function is -strongly convex if

It is -smooth when

For twice differentiable , the inequalities

give strong convexity and smoothness. The ratio is a condition number. Long narrow level sets correspond to large : gradient descent zigzags because one direction requires a small stable step while another changes slowly.

From smoothness,

Choose to obtain

This descent lemma justifies the step size . For convex smooth functions, gradient descent achieves . With -strong convexity, distance contracts linearly:

$$|x_k-x^|^2\le\left(1-\frac\mu L\right)^k|x_0-x^|^2.$$

Scaling and preconditioning try to reduce . If kilograms, dollars, and binary indicators are all represented on wildly different scales, even a theoretically good method may behave badly.

3. Subgradients and Nonsmooth Models

At a kink, the ordinary gradient does not exist, but convexity still supplies supporting hyperplanes. A vector is a subgradient of at when

The set of all such vectors is . For ,

A point minimizes a proper closed convex function iff . With a convex feasible set , the condition becomes

where is the normal cone. This compact inclusion generalizes gradient-zero, KKT stationarity, and boundary optimality.

Subgradient descent uses . Unlike gradient descent, the objective may increase on an individual step. With bounded subgradients and appropriate diminishing steps, the best objective converges at roughly . That slow rate motivates proximal methods when the nonsmooth term has exploitable structure.

4. Conjugates and Duality Derived Systematically

The Fenchel conjugate is

It records all affine lower bounds of . Fenchel–Young follows immediately:

with equality exactly when .

Examples:

• If , then .
• If , then is when and otherwise.
• If is the indicator of convex set , then , the support function.

Consider

Introduce and multiplier :

Minimizing over and gives

Therefore the dual is

This one derivation produces duals for basis pursuit, regularized regression, network flows, entropy models, and many decomposable programs.

Strong duality needs conditions. Slater’s condition—existence of a point satisfying affine equalities and strictly satisfying convex inequalities—is a practical sufficient condition. Without a qualification, the duality gap may be positive and KKT multipliers may fail to exist.

5. Proximal Operators: Solving a Small Problem at Every Step

For a closed convex function , define

The quadratic keeps near while imposes structure. If , the prox is Euclidean projection onto . If , the prox is soft-thresholding:

To derive it, solve the one-dimensional problem separately for , , and , then combine the cases. The interval around zero collapses exactly to zero; sparsity is a consequence of the kink, not numerical coincidence.

For composite minimization with smooth and proximable , proximal gradient is

With , the basic method attains ; Nesterov acceleration or FISTA attains in objective error under standard assumptions.

For LASSO,

the update is

where is soft-thresholding. Every term has a role: the gradient improves data fit, and the prox decides which coefficients survive.

6. Splitting and ADMM

Suppose and are individually easy but their sum is not. Write

The scaled augmented Lagrangian leads to ADMM:

The primal residual is . The dual residual measures movement in the split variable; for the common form, . Stopping requires both to be small relative to absolute and relative tolerances.

ADMM is attractive when variables split by data block, geographic region, scenario, or regularizer. It is not automatically faster than a mature conic solver. Its value appears when decomposition makes subproblems parallel, private, or much smaller.

The penalty does not change the exact solution but strongly affects speed. If dwarfs , increase ; if the reverse holds, decrease it, rescaling the dual variable consistently.

7. Stochastic, Coordinate, and Large-Scale Methods

If , a full gradient costs component evaluations. Stochastic gradient uses an unbiased estimate :

Noise makes early progress cheap but prevents constant-step iterates from settling exactly. Mini-batches trade variance for computation. Variance-reduced methods periodically use full gradients or control variates to recover faster convergence on finite sums.

Coordinate descent updates one coordinate or block. For smooth plus separable penalty, coordinate subproblems often have closed-form soft-threshold solutions. It is effective when individual columns are cheap and the solution is sparse.

Projected gradient handles a simple convex set :

Projection onto a box clips coordinates; projection onto a simplex can be obtained by sorting and thresholding; projection onto an affine set solves a least-squares system. The word “projection” hides an optimization problem, so complexity depends on .

8. Risk as a Convex Object: VaR and CVaR

Let be loss under decision and uncertain scenario . Value-at-Risk at confidence is a loss quantile:

VaR reports a threshold but ignores how severe the tail becomes beyond it. CVaR measures expected tail loss. The Rockafellar–Uryasev representation is

$$\operatorname{CVaR}\alpha(L)=\min_\eta\left[\eta+\frac1{1-\alpha}\mathbb E(L-\eta)+\right].$$

With scenarios and probabilities , introduce :

If each scenario loss is convex, the CVaR model is convex. If losses are affine, it is an LP. We have converted a tail statistic into auxiliary variables and linear inequalities.

Suppose five equally likely losses are and . Choosing between 9 and 20 leaves only the 20-loss scenario in the hinge term. At the empirical optimum the CVaR is 20: it focuses on the worst 20% tail rather than the mean 8. A risk-neutral plan may accept a rare catastrophe because average profit is high; a CVaR plan prices the catastrophe directly.

Risk aversion can be expressed as

or as a constraint $\operatorname{CVaR}\alpha\le R{\max}\lambda$ is not “the correct value”; it represents a stakeholder tradeoff. Show a frontier rather than hiding the choice.

9. Winning-Paper Case: Risk-Aware Crop Planning

The 2024 CUMCM crop-planning excellent paper extends its deterministic plan by treating demand, yield, price, and cost as uncertain, then incorporating CVaR. Let denote the planting plan from the previous blog. For scenario , define profit

where yield affects the link between planted area and sellable production. Let loss be . A transparent risk-aware objective is

subject to

plus land, crop, rotation, and sales constraints for every scenario. Here estimates VaR; records excess loss beyond it.

Building scenarios without manufacturing certainty

If the prompt states ranges rather than distributions, do not pretend they are precisely Gaussian. A defensible design might include:

1. a nominal scenario;
2. low/high demand by crop family;
3. adverse yield and high cost;
4. favorable demand but constrained production;
5. correlated shocks, such as reduced yield coinciding with higher market price.

Scenario probabilities should come from evidence when available. Otherwise present them as assumptions and test alternatives. Independent random draws can destroy meaningful correlations. A drought that reduces multiple crop yields simultaneously is not represented by perturbing every crop independently.

Comparing decisions, not only objective values

For each and , report expected profit, CVaR, worst-case profit, rotation feasibility, and how much planted area changes. A plan whose expected profit drops 1% while tail loss drops 30% may be compelling. A plan whose crop allocation changes completely under a tiny probability adjustment is fragile even if its reported CVaR is attractive.

The excellent paper uses a DEGA heuristic to solve its extended model. That does not remove the need for bounds. Because much of the scenario-CVaR layer is linear once discrete crop choices are introduced, a MILP formulation can benchmark reduced instances. Compare heuristic value against the MILP incumbent and bound, then explain any remaining gap.

A four-scenario miniature

Let two crop allocations satisfy , . Scenario profits are

With equal probabilities, vegetable has mean , below wheat’s only by equality here, but far worse downside. At , empirical loss-CVaR focuses on the single worst scenario: wheat’s tail loss is , vegetable’s is . A risk-neutral objective is indifferent, while any positive tail-risk penalty prefers wheat. Changing the values slightly can create a genuine tradeoff; the point is to inspect the mechanism before solving hundreds of scenarios.

10. Certificates, Failure Modes, and Reporting

A convex algorithm is trustworthy only when formulation and diagnostics agree. Track:

• primal feasibility;
• stationarity or dual feasibility;
• complementary slackness where relevant;
• primal-dual gap;
• objective change and iterate change;
• conditioning and scaling;
• out-of-sample scenario performance.

For composite problems, the proximal-gradient mapping

generalizes the gradient. is an optimality condition, so is more meaningful than merely counting iterations.

Common failure modes include:

1. asserting convexity because a plot “looks bowl-shaped”;
2. using a Hessian test outside its domain;
3. treating KKT conditions as a global certificate for a nonconvex model;
4. reporting a dual variable without its units or sign convention;
5. tuning risk parameters on the same scenarios used to claim robustness;
6. comparing algorithms at different tolerances;
7. declaring convergence because the objective stopped changing while constraints remain violated;
8. describing a heuristic as “convex optimization” merely because some subexpression is convex.

Sources and further reading

• CUMCM official site and excellent-paper display for the 2024 crop-planning case.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization.
• Neal Parikh and Stephen Boyd, Proximal Algorithms.
• Stephen Boyd et al., Distributed Optimization and Statistical Learning via ADMM.
• Rockafellar and Uryasev, Optimization of Conditional Value-at-Risk.

Convex optimization is powerful not because it makes modeling automatic, but because it connects geometry, algorithms, and certificates. When you can prove curvature, derive a dual, and measure optimality, the solver’s answer becomes an auditable argument rather than a mysterious number.

If you made it this far, here is the hidden exercise: derive the conjugate of without expanding the square until the last line. The answer quietly explains why translating a quadratic changes the dual by a linear term. Write it in the margin; it will reappear when we study robust and distributed models.