bibjLdZddlmZddlmZmZddlmZmZm Z m Z m Z m Z m Z erddlmZddlZddlmZddlmZdd lmZdd lmZdd lmZdd lmZdd lmZddl m!Z!ddl"m#Z#edGddZ$edGddZ%edGddZ&edGddZ'e e$e%e&e'fZ(eGddZ)eGddZ*d'dZ+d(dZ,d)d Z- d*d!Z. d+d"Z/d,d#Z0 d-d$Z1Gd%d&e!Z2y).a Copyright 2025, the CVXPY authors Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. SOC dimension reduction to 3D cones. This module provides the SOCDim3 reduction which converts arbitrary-dimensional Second-Order Cone (SOC) constraints to equivalent systems of 3D SOC constraints. This enables solvers that only support 3D SOC to handle arbitrary dimensional SOC constraints. The decomposition uses a binary tree structure: - Dimension 1: Convert to NonNeg constraint (||[]|| <= t becomes t >= 0) - Dimension 2: Convert to NonNeg constraints (|x| <= t becomes t-x >= 0, t+x >= 0) - Dimension 3: Pass through unchanged - Dimension 4: Chain of two 3D cones (special case for efficiency) - Dimension n > 4: Binary split into balanced tree of 3D cones Example: A dimension 5 cone ||(x1, x2, x3, x4)|| <= t becomes:: ||(x1, x2)|| <= s1 (3D cone) ||(x3, x4)|| <= s2 (3D cone) ||(s1, s2)|| <= t (3D cone) where s1, s2 are auxiliary variables. ) annotations) dataclassfield) TYPE_CHECKINGAnyDictListOptionalTupleUnion)ProblemNreshape)vstack)NonNeg)SOC)cvxtypes) Expression)Variable) Reduction)SolutionT)frozenc.eZdZUdZdZded<dZded<y) NonNegTreeaTree node for cases that reduce to NonNeg constraints. - Dim-1 (||[]|| <= t): reduces to t >= 0 - Dim-2 (|x| <= t): reduces to t-x >= 0, t+x >= 0 Attributes ---------- original_dim : int Original dimension (1 or 2). nonneg_ids : tuple Constraint IDs of the NonNeg constraints. For dim-1: (id of t >= 0,) For dim-2: (id of t-x >= 0, id of t+x >= 0) int original_dimtuple nonneg_idsN)__name__ __module__ __qualname____doc__r__annotations__r r^/home/cdr/jupyterlab/.venv/lib/python3.12/site-packages/cvxpy/reductions/cone2cone/soc_dim3.pyrr@s L#Jr&rc*eZdZUdZded<dZded<y)LeafTreea/Tree node for a single 3D cone. Represents a leaf in the decomposition tree - an actual 3D SOC constraint. Attributes ---------- cone_id : int The constraint ID of the 3D SOC cone. original_dim : int The original dimension of this cone (always 3 for LeafTree). rcone_idrNr!r"r#r$r%rrr&r'r)r)Ts LL#r&r)c4eZdZUdZded<ded<dZded<y) ChainTreea Tree node for dim-4 special case: two chained cones. For dimension 4 (||(x1, x2, x3)|| <= t), we use a chain structure: ||(x1, x2)|| <= s ||(s, x3)|| <= t This avoids the unbalanced 1+2 split that would occur with generic binary split. Attributes ---------- leaf_cone_id : int Constraint ID of the leaf cone (contains x1, x2). root_cone_id : int Constraint ID of the root cone (contains s, x3). original_dim : int Always 4 for chain decomposition. r leaf_cone_id root_cone_idrNr,rr&r'r.r.es"L#r&r.c:eZdZUdZded<ded<ded<ded<y) SplitTreeaTree node for binary split decomposition. For dimension n > 4, we split x into two halves and recursively decompose: ||x_left|| <= s1 ||x_right|| <= s2 ||(s1, s2)|| <= t Attributes ---------- root_cone_id : int Constraint ID of the root cone (contains s1, s2). left : DecompositionTree Left subtree (decomposition of x_left). right : DecompositionTree Right subtree (decomposition of x_right). original_dim : int Original dimension of this cone. rr0DecompositionTreeleftrightrN)r!r"r#r$r%rr&r'r3r3}s!$  r&r3c>eZdZUdZded<ded<ded<dZded<y ) SOCTreeDataaDecomposition data for a single original SOC constraint. Attributes ---------- trees : List[DecompositionTree] List of decomposition trees, one per cone in elementwise SOC. num_cones : int Number of individual cones (1 for simple SOC, >1 for elementwise). original_dim : int Dimension of each cone. axis : int Axis parameter from original SOC constraint. zList[DecompositionTree]treesr num_conesrraxisN)r!r"r#r$r%r;rr&r'r8r8s#  #"ND#Mr&r8cJeZdZUdZeeZded<eeZ ded<y)SOCDim3InverseDataa*Data needed to reconstruct original SOC duals from decomposed problem. Attributes ---------- soc_trees : Dict[int, SOCTreeData] Mapping from original SOC constraint ID to its decomposition data. old_constraints : List Reference to original problem constraints. )default_factoryzDict[int, SOCTreeData] soc_treesr old_constraintsN) r!r"r#r$rdictr?r%listr@rr&r'r=r=s().d(CI%C!$7OT7r&r=ct|ddS)aReshape expression to scalar form (1,) for SOC constructor. Parameters ---------- expr : Expression Expression to reshape (should be scalar or shape (1,)). Returns ------- Expression Expression with shape (1,). )rForderr)exprs r'_to_scalar_shaperHs 4S ))r&c*|yt|trlt|dk(r^|\}}||ytj|}tj|j d}tj |dd|gStj|S)aConvert a dual value to flat array format. Dual values can come in two formats: - Flat array: [lambda, mu1, mu2, ...] (from solver) - Split list: [lambda_array, mu_array] (after save_dual_value) This function normalizes to flat array format. Parameters ---------- dual_value : Optional[Any] Dual value in either format, or None. Returns ------- Optional[np.ndarray] Flat array [lambda, mu1, mu2, ...] or None if input is None. NrDrEr) isinstancerBlennp atleast_1dflatten concatenate) dual_valuet_valx_valt_arrx_arrs r'_get_flat_dualrVs&*d#J1(<! u =EM e$ e$,,3,7~~uRay%011 == $$r&ct|trt|jSt|tr |j hSt|t r|j|jhSt|trW|jh}|jt|j|jt|j|StS)zGet all constraint IDs from a decomposition tree. Parameters ---------- tree : DecompositionTree The decomposition tree to traverse. Returns ------- set Set of all constraint IDs (SOC and NonNeg) in the tree. )rKrsetr r)r*r.r/r0r3update_get_cone_ids_from_treer5r6)treeidss r'rZrZs$ #4??## D( # ~ D) $!!4#4#455 D) $  ! *49956 *4::67 5Lr&c|| td|j}|dk(r4t|}|j|t d|j fS|dk(rd|j d}t||z }t||z}|j||gt d|j |j fS|dk(rLtt||j d} |j| t| j S|d k(rt} |jt| |dd} |d} tt| | j d} |j| t| | g}tt||j d}|j|t| j |j d S|dzdz}|d|} ||d}t}t}|jt||jt|t|| j d||}t||j d||}t||g}tt||j d}|j|t|j |||dz S)aDecompose a single ||x|| <= t constraint into tree of exactly 3D cones. This function recursively decomposes an n-dimensional SOC constraint into a tree of 3D SOC constraints using binary splitting. Parameters ---------- t_expr : Expression The scalar bound expression (should have size 1). x_expr : Expression The vector argument (1D expression). soc3_out : List[SOC] Output list to append generated 3D SOC constraints to. nonneg_out : List[NonNeg] Output list to append generated NonNeg constraints to. Returns ------- DecompositionTree Tree structure for dual variable reconstruction. Raises ------ ValueError If t_expr or x_expr is None, or if t_expr is not scalar. Nz t_expr and x_expr cannot be Nonerr)rr rDrErJ)r*r+r1)r/r0r)r0r5r6r) ValueErrorsizerappendridrOextendrrHr)rrr._decompose_soc_singler3)t_exprx_exprsoc3_out nonneg_outncx_flatc1c2conesx_leftx_lastcone1root_xcone2midx_rights1s2 left_tree right_tree root_cones r'rcrcsB~;<< A Av 6N!qaddW== Avc*FVO $ FVO $2r(#qbeeRUU^DD Av#F+V^^#^-FG(( Av J&)$$Q'c)BCF $$V,fnn3n.GH   q5Q,C DS\FSTlG B BfRj!fRj!&b&..s.*CXzZI&r7???+ExQ[\JRH F$V,fnn3n.GHI OOI \\ U  r&ct|tr|jdk(r|S|jdk(rt|jdk(r|j |jd}|j |jd}||yt tj|jd}t tj|jd}||z ||<|dzS|St|trW|j |j}|yt|} | t| dkry| dd} t| } | |||| z|| zSt|tr|j |j} |j |j} | | yt| }t| }||yt|dk\r|d||<|d||dz<|dz }t|dk\r |d||<|dz }|St|t r3t#|j$|||}|yt#|j&|||Sy)a#Collect x-component duals from leaf cones into pre-allocated array. For an SOC constraint ||x|| <= t, the dual is a flat array [lambda, mu1, mu2, ...] where lambda is the dual for t and mu is the dual for x. This function traverses the decomposition tree and writes all mu components from leaf cones into the output array in order. Parameters ---------- tree : DecompositionTree The decomposition tree structure. dual_vars : Dict[int, Any] Mapping from constraint ID to dual variable value. out : np.ndarray Pre-allocated output array to write duals into. offset : int Current write position in the output array. Returns ------- Optional[int] New offset after writing, or None if reconstruction failed. rrJrNr+)rKrrrLr getfloatrMrNflatr)r*rVr.r/r0r3_collect_x_duals_into_arrayr5r6)r[ dual_varsoutoffset alpha_rawbeta_rawalphabetadual_rawdualx_dualn_write leaf_dual_raw root_dual_raw leaf_dual root_dual new_offsets r'rrsI<$ #    !M   ! #DOO(<(A" dooa&89I }}T__Q%78H H$4"-- 277:;Ex055a89D,CKA:  $!==.  h' <3t9q=abf+'-F6G#$$ "! d&7&78 ! d&7&78  M$9"=1 "=1   1 y>Q #A,CK'lC O aKF y>Q #A,CK aKF $ "0IsFS  *4::y#zRR r&ctt|tr7|jdk(rdt|jdk\rK|j |jd}|+t tj|jdSy|jdk(rt|jdk(r|j |jd}|j |jd}||yt tj|jd}t tj|jd}||zSyt|tr@|j |j}|yt|}|t|dk\r|dSdSt|tr@|j |j}|yt|}|t|dk\r|dSdSt|tr@|j |j}|yt|}|t|dk\r|dSdSy)arGet the t-component dual (lambda) from the root cone. Parameters ---------- tree : DecompositionTree The decomposition tree structure. dual_vars : Dict[int, Any] Mapping from constraint ID to dual variable value. Returns ------- Optional[float] The dual value for t from the root cone, or None if not available. rrNrJ)rKrrrLr r|r}rMrNr~r)r*rVr.r0r3)r[rrrrrrrs r'_get_root_t_dualrs$ #    !4??#q($==);<' x!8!=!=a!@AA   ! #DOO(<(A" dooa&89I }}T__Q%78H H$4"-- 277:;Ex055a89D4< $!==.  h'*s4yA~tAwG4G$ "==!2!23  h'*s4yA~tAwG4G$ "==!2!23  h'*s4yA~tAwG4G r&ct||}|y|jdz }|dk(rtj|gStj|}t |||d}|ytj |g|gS)aReconstruct the original SOC dual from decomposed cone duals. For an SOC constraint ||x|| <= t, the dual is a flat array [lambda, mu1, mu2, ...] where lambda is the dual for t and mu is the dual for x. This function reconstructs the original dual by: 1. Getting lambda from the root cone 2. Collecting all mu components from leaf cones in order Parameters ---------- tree : DecompositionTree The decomposition tree structure. dual_vars : Dict[int, Any] Mapping from constraint ID to dual variable value (flat arrays). Returns ------- Optional[np.ndarray] Reconstructed dual as flat array [lambda, mu1, mu2, ...] or None if failed. Nrr)rrrMarrayemptyrrP)r[rt_dualx_sizex_duals final_offsets r'_reconstruct_soc_dualr5s2dI .F ~   "F {xx!!hhvG.tYKL >>F8W- ..r&c4eZdZdZddZddZ ddZy) SOCDim3a$Convert n-dimensional SOC constraints to dimension-3 SOC constraints. This reduction enables solvers that only support 3D SOC to handle arbitrary dimensional SOC constraints. The decomposition uses a binary tree structure: - Dimension 1 (||[]|| <= t): Convert to NonNeg(t) - Dimension 2 (|x| <= t): Pad with auxiliary variable to 3D - Dimension 3: Pass through unchanged - Dimension 4: Special chain structure (two 3D cones) - Dimension n > 4: Recursively split into tree of 3D cones Example ------- >>> x = cp.Variable(4) >>> t = cp.Variable(nonneg=True) >>> prob = cp.Problem(cp.Minimize(t), [cp.norm(x, 2) <= t]) >>> reduction = SOCDim3() >>> new_prob, inv_data = reduction.apply(prob) >>> # new_prob has only 3D SOC constraints cy)aCheck if this reduction accepts the given problem. This reduction accepts any problem. Parameters ---------- problem : Problem The optimization problem. Returns ------- bool Always True. Tr)selfproblems r'acceptszSOCDim3.accepts}sr&c*ti|j}td|jD}|s||fSg}|jD]}t|tr{|j d}|j d}|j }|dk(r |j}t|jdk(r&t||jdfd} t|} n|} |} | j} | jd| k7r$| dkDrtd| d| jdd g} g} g}t| D]G}| dkDr| |n| d}| dkDr | d d |fn| d d df}t||| |}| j!|I|j#| |j#||j%}t'| | |r|dnd | |j(|j*<|j!|t-j.|j0|}||fS) aApply SOCDim3 decomposition to all SOC constraints. Parameters ---------- problem : Problem The optimization problem to transform. Returns ------- new_problem : Problem Problem with all SOC constraints decomposed to dim-3. inverse_data : SOCDim3InverseData Data needed to reconstruct original dual variables. )r?r@c3<K|]}t|tyw)N)rKr).0ris r' z SOCDim3.apply..sFQjC(FsrrrDrEzDimension mismatch: t has z elements but X has z columnsNr+)r9r:rr;)r= constraintsanyrKrargsr;TrLshaperr_rHr^rangercr`rb cone_sizesr8r?rarr objective)rr inverse_datahas_socnew_constraintscontXr; X_reshaped t_reshapedr: all_treesrfrgit_ix_ir[r new_problems r'applyz SOCDim3.applys9*#// F'2E2EFFL( ( "&&7 ,C#s#HHQKHHQKxx19Aqww<1$!(QVVQKs!CJ!1!!4J!"J!"J&OO ##A&)3 A $4YK@!!+!1!1!!4 5X? 68 &(+- y)+A+4q=*Q-jmC.7!m*QT*AqDAQC0c8ZPD$$T* + &&x0&&z2!^^- 1<#'2<A! 2 &&svv. &&s+o7 ,r)h&&():):OL L((r&c D|jr|jjni}|js-t|j|j |i|j Si}t}|jjD]-}|jD]}|jt|/|jjD]\}} ||vs | ||<|jjD]\} }|j} t| dk(r"t| d|j} | <| || <Bg} d}| D]/}t||j} | d}n| j!| 1|s}t#j$| Dcgc]}|d c}}t#j&| Dcgc]}|dd c}}|j(dk(r |j*}||g|| <t|j|j |||j Scc}wcc}w)aReconstruct solution with original SOC dual variables. Parameters ---------- solution : Solution Solution from the decomposed problem. inverse_data : SOCDim3InverseData Data from apply() containing tree structures. Returns ------- Solution Solution with reconstructed dual variables. rrNTF) primal_varscopyrrstatusopt_valattrrXr?valuesr9rYrZitemsrLrr`rMr column_stackr;r)rsolutionrpvarsdvarsdecomposed_cone_ids tree_datar[cidrorig_idr9 reconstructed all_dualssuccessdt_dualsrs r'invertzSOCDim3.inverts(08/C/C$$))+!!HOOX-=-=ub(--X X!#$'5%//668 JI! J#**+B4+HI J J "++113 "IC--!c  " #/"8"8">">"@ 8 GYOOE5zQ 5eAh@R@R S  ,%2E'N/1 !4D$9$@R@R$SM$,"'$$]3 4!hhi'@!'@AG ooi.Hqu.HIG ~~*")))&-w%7E'N7 8:)9)95%WW(A.Hs  H 4 H N)rr returnbool)rr rz"Tuple[Problem, SOCDim3InverseData])rrrr=rr)r!r"r#r$rrrrr&r'rres<."U)nFXFX)FX  FXr&r)rGrrr)rQz Optional[Any]rOptional[np.ndarray])r[r4rrX) rdrrerrfz List[SOC]rgz List[NonNeg]rr4) r[r4rDict[int, Any]rz np.ndarrayrrrz Optional[int])r[r4rrrzOptional[float])r[r4rrrr)3r$ __future__r dataclassesrrtypingrrrr r r r cvxpy.problems.problemr numpyrMcvxpy.atoms.affine.reshapercvxpy.atoms.affine.vstackrcvxpy.constraints.nonposrcvxpy.constraints.second_orderrcvxpy.expressionsrcvxpy.expressions.expressionrcvxpy.expressions.variablercvxpy.reductions.reductionrcvxpy.reductions.solutionrrr)r.r3r4r8r=rHrVrZrcrrrrrr&r'rs%N#(III..,+.&3/0.  $& $     $. $4*h 9DE  (  8 8  8$ * %F>p p pp p  pnd dd d  d  dN;|)/ )/)/)/`FXiFXr&