L2正则化最小二乘问题的类型判定与SeDuMi格式转换咨询

Hey there! Let's break down your optimization problem step by step, starting with what type of problem it is, then moving to how to format it for SeDuMi.

Your cost function $J = \min_{\boldsymbol{x}} \left{ |A\boldsymbol{x} - b|_2^2 + \lambda|\boldsymbol{x}|_2 \right}$ is a convex unconstrained optimization problem, specifically a quadratic-L2 composite problem. Let's break that down:

• The term $|A\boldsymbol{x} - b|_2^2$ is a convex quadratic function (it expands to a quadratic form in $\boldsymbol{x}$).
• The term $\lambda|\boldsymbol{x}|_2$ is a convex function (the L2 norm is convex, and scaling it by a positive $\lambda$ preserves convexity).
• Since the sum of convex functions is convex, the entire objective is convex—this means any local minimum is also the global minimum, which is great news for optimization.

Note: This is distinct from ridge regression, which uses $\lambda|\boldsymbol{x}|_2^2$ (the squared L2 norm) as the regularizer. Your problem uses the unsquared L2 norm, which leads to different behavior (for example, it can lead to sparser solutions in some cases, though not as aggressively as L1 regularization).

SeDuMi specializes in solving cone programming problems, which follow this standard form:
$$
\begin{align*}
\min_{\boldsymbol{z}} &\quad \boldsymbol{c}^T \boldsymbol{z} \
\text{s.t.} &\quad A_{\text{sedumi}} \boldsymbol{z} = \boldsymbol{b}_{\text{sedumi}} \
&\quad \boldsymbol{z} \in \mathcal{K}
\end{align*}
$$
where $\mathcal{K}$ is a Cartesian product of convex cones (like second-order cones, rotated second-order cones, or non-negative orthants).

To convert your problem, we'll use epigraphs and cone constraints to represent the non-linear terms (the L2 norm and the squared L2 norm) as linear constraints plus cone membership. Here's the step-by-step process:

Step 1: Rewrite the Problem with Auxiliary Variables #

First, we introduce auxiliary variables to split the objective into a linear function, then add constraints to link these variables back to the original terms:
$$
\min_{\boldsymbol{x}, t, s} \quad t + \lambda s \
\text{s.t.} \quad |A\boldsymbol{x} - b|_2^2 \leq t \
\quad |\boldsymbol{x}|_2 \leq s
$$

• $t$ acts as an upper bound for the squared L2 error term.
• $s$ acts as an upper bound for the L2 norm of $\boldsymbol{x}$.

Step 2: Map Constraints to Cones #

Now we need to represent these inequalities using cones supported by SeDuMi:

1. Squared L2 Error Constraint: $|A\boldsymbol{x} - b|_2^2 \leq t$ is a rotated second-order cone constraint. This fits the rotated cone definition: ${(t, 1, A\boldsymbol{x} - b) \mid 2t \cdot 1 \geq |A\boldsymbol{x} - b|_2^2, t \geq 0, 1 \geq 0}$. We'll need a dummy variable set to 1 to make this fit SeDuMi's cone structure.
2. L2 Norm Constraint: $|\boldsymbol{x}|_2 \leq s$ is a standard second-order cone constraint: ${(s, \boldsymbol{x}) \mid s \geq |\boldsymbol{x}|_2}$.

Step 3: Build SeDuMi Inputs #

Let's define all variables as a single vector $\boldsymbol{z} = [\boldsymbol{x}; t; u; v; s]$, where:

• $u$ is the dummy variable fixed to 1,
• $v = A\boldsymbol{x} - b$.

Constraint Matrix & RHS Vector

We need two linear equality constraints:

• $A\boldsymbol{x} - v = b$ (links $v$ to the original error term),
• $u = 1$ (fixes the dummy variable).

In MATLAB, you'd construct these as sparse matrices to keep things efficient:

% Assume A, b, lambda are already defined
n = size(A, 2); % Dimension of x
m = size(A, 1); % Dimension of b

% Constraint 1: Ax - v = b
block1 = [A, sparse(m, 1), sparse(m, 1), -speye(m), sparse(m, 1)];
b1 = b;

% Constraint 2: u = 1
block2 = [sparse(1, n), 0, 1, sparse(1, m), 0];
b2 = 1;

% Combine into SeDuMi's A and b
A_sedumi = [block1; block2];
b_sedumi = [b1; b2];

Objective Vector

Our objective is to minimize $t + \lambda s$, so the coefficient vector $\boldsymbol{c}$ has zeros for all variables except $t$ (coefficient 1) and $s$ (coefficient $\lambda$):

c_sedumi = zeros(n + 1 + 1 + m + 1, 1);
c_sedumi(n + 1) = 1; % Coefficient for t
c_sedumi(end) = lambda; % Coefficient for s

Cone Structure

Define the cones SeDuMi needs to enforce:

K.rq = m + 2; % Rotated cone for (t, u, v) (dimension m+2)
K.q = n + 1; % Standard second-order cone for (s, x) (dimension n+1)
K.l = 0; % No non-negative orthant needed

Step 4: Solve with SeDuMi #

Finally, call SeDuMi and extract your optimal $\boldsymbol{x}$:

[z, info] = sedumi(A_sedumi, b_sedumi, c_sedumi, K);
x_opt = z(1:n); % Extract the original variable from the solution vector

内容的提问来源于stack exchange，提问作者shashashamti2008