0
# Transform Functions
1

2
Problem transformation utilities for advanced optimization techniques including linearization, partial optimization, and support function transformations in CVXPY.
3

4
## Capabilities
5

6
### Linearization
7

8
Linearize expressions around current variable values for successive linear programming and sensitivity analysis.
9

10
```python { .api }
11
def linearize(expr, var_id=None):
12
    """
13
    Linearize expression around current variable values.
14
    
15
    Parameters:
16
    - expr: Expression to linearize
17
    - var_id: Variable ID to linearize around (None for all variables)
18
    
19
    Returns:
20
    - Expression: linearized expression (affine approximation)
21
    """
22
    ...
23
```
24

25
Usage examples:
26

27
```python
28
import cvxpy as cp
29
import numpy as np
30

31
# Successive linear programming example
32
x = cp.Variable(2)
33
y = cp.Variable(2)
34

35
# Non-convex constraint: x[0] * y[0] + x[1] * y[1] >= 1
36
nonconvex_expr = x[0] * y[0] + x[1] * y[1]
37

38
# Initialize variables
39
x.value = np.array([1.0, 1.0])
40
y.value = np.array([0.5, 0.5])
41

42
# Solve sequence of linearized problems
43
for iteration in range(10):
44
    # Linearize the non-convex expression
45
    linear_approx = cp.linearize(nonconvex_expr)
46
    
47
    # Solve linearized problem
48
    objective = cp.Minimize(cp.sum_squares(x) + cp.sum_squares(y))
49
    constraints = [linear_approx >= 1, x >= 0, y >= 0]
50
    problem = cp.Problem(objective, constraints)
51
    
52
    problem.solve()
53
    
54
    print(f"Iteration {iteration}: obj = {problem.value:.4f}")
55
    print(f"x = {x.value}, y = {y.value}")
56
    
57
    # Check convergence
58
    if iteration > 0 and abs(problem.value - prev_obj) < 1e-6:
59
        break
60
    prev_obj = problem.value
61

62
# Sensitivity analysis using linearization
63
# Perturb a parameter and use linearization to estimate effect
64
A = cp.Parameter((3, 2), value=np.random.randn(3, 2))
65
b = cp.Parameter(3, value=np.random.randn(3))
66
x = cp.Variable(2)
67

68
original_problem = cp.Problem(
69
    cp.Minimize(cp.sum_squares(x)),
70
    [A @ x == b, x >= 0]
71
)
72
original_problem.solve()
73
original_obj = original_problem.value
74

75
# Linearize objective around current solution
76
obj_linear = cp.linearize(cp.sum_squares(x))
77

78
# Perturb parameter and estimate new objective
79
b_new = b.value + 0.1 * np.random.randn(3)
80
b.value = b_new
81

82
# Solve with linearized objective (approximation)
83
approx_problem = cp.Problem(cp.Minimize(obj_linear), [A @ x == b, x >= 0])
84
approx_problem.solve()
85
approx_obj = approx_problem.value
86

87
# Solve exactly for comparison
88
b.value = b_new
89
original_problem.solve()
90
exact_obj = original_problem.value
91

92
print(f"Original objective: {original_obj:.6f}")
93
print(f"Approximated objective: {approx_obj:.6f}")
94
print(f"Exact objective: {exact_obj:.6f}")
95
print(f"Approximation error: {abs(exact_obj - approx_obj):.6f}")
96
```
97

98
### Partial Optimization
99

100
Partially optimize over a subset of variables while keeping others as parameters.
101

102
```python { .api }
103
def partial_optimize(problem, opt_vars, opt_params=None):
104
    """
105
    Partially optimize a problem over specified variables.
106
    
107
    Parameters:
108
    - problem: Problem to partially optimize
109
    - opt_vars: list of variables to optimize over
110
    - opt_params: list of parameters to treat as optimization variables
111
    
112
    Returns:
113
    - Expression: optimal value as function of remaining variables
114
    """
115
    ...
116
```
117

118
Usage examples:
119

120
```python
121
import cvxpy as cp
122
import numpy as np
123

124
# Bilevel optimization example
125
# Lower level: min_y ||Ay - b||^2 subject to y >= 0
126
# Upper level: min_x f(x) subject to x in optimal solution set of lower level
127

128
# Problem dimensions
129
m, n = 10, 5
130

131
# Upper level variables
132
x = cp.Variable(n)
133

134
# Lower level variables and data
135
y = cp.Variable(m)
136
A = cp.Parameter((m, n), value=np.random.randn(m, n))
137
b = cp.Parameter(m)
138

139
# Lower level problem (parameterized by x)
140
b.value = A.value @ np.ones(n)  # Make problem feasible
141
lower_obj = cp.sum_squares(A @ y - (b + x))  # b depends on x
142
lower_constraints = [y >= 0]
143
lower_problem = cp.Problem(cp.Minimize(lower_obj), lower_constraints)
144

145
# Partially optimize over y to get upper level constraint
146
try:
147
    # This creates an expression in terms of x
148
    optimal_lower_value = cp.partial_optimize(lower_problem, [y])
149
    
150
    # Upper level problem
151
    upper_obj = cp.sum_squares(x) + optimal_lower_value
152
    upper_constraints = [cp.norm(x, 'inf') <= 1]
153
    upper_problem = cp.Problem(cp.Minimize(upper_obj), upper_constraints)
154
    
155
    upper_problem.solve()
156
    print(f"Optimal x: {x.value}")
157
    print(f"Upper level objective: {upper_problem.value}")
158
    
159
except Exception as e:
160
    print(f"Partial optimization failed: {e}")
161

162
# Portfolio optimization with transaction costs
163
# Outer problem: choose target portfolio
164
# Inner problem: minimize transaction costs to reach target
165

166
n_assets = 5
167
w_current = cp.Parameter(n_assets, value=np.random.rand(n_assets))
168
w_current.value = w_current.value / np.sum(w_current.value)  # normalize
169

170
# Target portfolio (outer variable)  
171
w_target = cp.Variable(n_assets)
172

173
# Trade amounts (inner variables)
174
w_buy = cp.Variable(n_assets, nonneg=True)
175
w_sell = cp.Variable(n_assets, nonneg=True)
176

177
# Transaction cost parameters
178
cost_buy = 0.01   # 1% transaction cost for buying
179
cost_sell = 0.01  # 1% transaction cost for selling
180

181
# Inner problem: minimize transaction costs to reach target
182
transaction_costs = cost_buy * cp.sum(w_buy) + cost_sell * cp.sum(w_sell)
183
rebalancing_constraint = w_current + w_buy - w_sell == w_target
184

185
inner_problem = cp.Problem(
186
    cp.Minimize(transaction_costs),
187
    [rebalancing_constraint, w_buy >= 0, w_sell >= 0]
188
)
189

190
# Outer problem: choose target portfolio considering transaction costs
191
expected_return = cp.Parameter(n_assets, value=0.1 * np.random.rand(n_assets))
192
risk_param = 0.5
193

194
try:
195
    # Partially optimize over trading variables
196
    min_transaction_cost = cp.partial_optimize(inner_problem, [w_buy, w_sell])
197
    
198
    # Outer objective: maximize return minus transaction costs
199
    portfolio_return = expected_return.T @ w_target
200
    outer_obj = cp.Maximize(portfolio_return - risk_param * min_transaction_cost)
201
    
202
    # Portfolio constraints
203
    outer_constraints = [
204
        cp.sum(w_target) == 1,  # fully invested
205
        w_target >= 0           # long-only
206
    ]
207
    
208
    outer_problem = cp.Problem(outer_obj, outer_constraints)
209
    outer_problem.solve()
210
    
211
    print(f"Optimal target portfolio: {w_target.value}")
212
    print(f"Current portfolio: {w_current.value}")
213
    print(f"Expected net return: {outer_problem.value}")
214
    
215
except Exception as e:
216
    print(f"Bilevel portfolio optimization failed: {e}")
217
```
218

219
### Support Function
220

221
Transform expressions using support function representations for convex analysis.
222

223
```python { .api }
224
def suppfunc(expr, vars=None):
225
    """
226
    Compute support function of expression.
227
    
228
    Parameters:
229
    - expr: Expression to compute support function for
230
    - vars: Variables to compute support function over
231
    
232
    Returns:
233
    - Expression: support function
234
    """
235
    ...
236
```
237

238
Usage examples:
239

240
```python
241
import cvxpy as cp
242
import numpy as np
243

244
# Support function of a norm ball
245
x = cp.Variable(3)
246
y = cp.Variable(3)  # dual variable
247

248
# L2 ball: {x : ||x||_2 <= 1}
249
# Support function: sup_{||x||_2 <= 1} y^T x = ||y||_2
250
l2_ball_constraint = cp.norm(x, 2) <= 1
251
try:
252
    support_func = cp.suppfunc(y.T @ x, [x])  # Should give ||y||_2
253
    print("L2 ball support function computed")
254
except Exception as e:
255
    print(f"Support function computation failed: {e}")
256

257
# Support function in robust optimization
258
# Robust least squares: min_x max_{||u||_inf <= delta} ||Ax + u - b||^2
259

260
n, m = 5, 10
261
A = cp.Parameter((m, n), value=np.random.randn(m, n))
262
b = cp.Parameter(m, value=np.random.randn(m))
263
x = cp.Variable(n)
264
delta = 0.1  # uncertainty level
265

266
# Uncertainty set: ||u||_inf <= delta
267
u = cp.Variable(m)
268
residual = A @ x + u - b
269

270
try:
271
    # Worst-case residual over uncertainty set
272
    worst_case_obj = cp.suppfunc(cp.sum_squares(residual), [u])
273
    uncertainty_constraint = cp.norm(u, 'inf') <= delta
274
    
275
    # Robust optimization problem
276
    robust_obj = cp.Minimize(worst_case_obj)
277
    robust_problem = cp.Problem(robust_obj, [uncertainty_constraint])
278
    
279
    robust_problem.solve()
280
    print(f"Robust solution: {x.value}")
281
    
282
except Exception as e:
283
    print(f"Robust optimization with support function failed: {e}")
284

285
# Fenchel conjugate computation
286
# For convex function f(x), conjugate is f*(y) = sup_x (y^T x - f(x))
287

288
x = cp.Variable()
289
y = cp.Parameter(value=1.0)
290

291
# Conjugate of f(x) = x^2/2 should be f*(y) = y^2/2
292
f_x = 0.5 * x**2
293
linear_term = y * x
294

295
try:
296
    conjugate = cp.suppfunc(linear_term - f_x, [x])
297
    print("Fenchel conjugate computed")
298
    
299
    # Evaluate conjugate at different points
300
    for y_val in [-2, -1, 0, 1, 2]:
301
        y.value = y_val
302
        conjugate_problem = cp.Problem(cp.Minimize(-conjugate))  # max -> min
303
        conjugate_problem.solve()
304
        analytical = 0.5 * y_val**2  # True conjugate value
305
        print(f"y={y_val}: computed={conjugate_problem.value:.4f}, "
306
              f"analytical={analytical:.4f}")
307
        
308
except Exception as e:
309
    print(f"Fenchel conjugate computation failed: {e}")
310

311
# Game theory: computing Nash equilibrium
312
# Player 1: min_x max_y x^T Q y
313
# Player 2: max_y min_x x^T Q y  
314
# where x, y are in probability simplexes
315

316
n_strategies = 3
317
Q = cp.Parameter((n_strategies, n_strategies), 
318
                 value=np.random.randn(n_strategies, n_strategies))
319

320
x = cp.Variable(n_strategies, nonneg=True)  # Player 1 strategy
321
y = cp.Variable(n_strategies, nonneg=True)  # Player 2 strategy
322

323
# Probability simplex constraints
324
x_simplex = cp.sum(x) == 1
325
y_simplex = cp.sum(y) == 1
326

327
try:
328
    # Player 1's worst-case payoff: min_x max_y x^T Q y
329
    payoff = cp.quad_form(x, Q, y)  # This might not work directly
330
    player1_worst_case = cp.suppfunc(payoff, [y])
331
    
332
    # Nash equilibrium computation
333
    nash_problem = cp.Problem(
334
        cp.Minimize(player1_worst_case),
335
        [x_simplex, x >= 0, y_simplex, y >= 0]
336
    )
337
    
338
    nash_problem.solve()
339
    print(f"Nash equilibrium strategies:")
340
    print(f"Player 1: {x.value}")
341
    print(f"Player 2: {y.value}")
342
    
343
except Exception as e:
344
    print(f"Nash equilibrium computation failed: {e}")
345
```
346

347
### Indicator Function
348

349
Transform expressions using indicator functions for set membership constraints.
350

351
```python { .api }
352
def indicator(constraints):
353
    """
354
    Indicator function for a set defined by constraints.
355
    
356
    Parameters:
357
    - constraints: list of constraints defining the set
358
    
359
    Returns:
360
    - Expression: indicator function (0 if constraints satisfied, +inf otherwise)
361
    """
362
    ...
363
```
364

365
### Scalarization Functions
366

367
Transform multi-objective problems into single-objective problems using scalarization techniques.
368

369
```python { .api }
370
def log_sum_exp(expr, axis=None, keepdims=False):
371
    """
372
    Log-sum-exponential scalarization: log(sum(exp(expr))).
373
    
374
    Parameters:
375
    - expr: expression
376
    - axis: axis to sum along
377
    - keepdims: whether to keep singleton dimensions
378
    
379
    Returns:
380
    - Expression: log-sum-exp scalarization
381
    """
382
    ...
383

384
def max(expr, axis=None, keepdims=False):
385
    """
386
    Max scalarization for multi-objective problems.
387
    
388
    Parameters:
389
    - expr: expression or list of objective expressions
390
    - axis: axis to take maximum along
391
    - keepdims: whether to keep singleton dimensions
392
    
393
    Returns:
394
    - Expression: maximum scalarization
395
    """
396
    ...
397

398
def targets_and_priorities(objectives, targets, priorities):
399
    """
400
    Target-based scalarization with priorities.
401
    
402
    Parameters:
403
    - objectives: list of objective expressions
404
    - targets: target values for each objective
405
    - priorities: priority weights for each objective
406
    
407
    Returns:
408
    - Expression: scalarized objective
409
    """
410
    ...
411

412
def weighted_sum(objectives, weights):
413
    """
414
    Weighted sum scalarization.
415
    
416
    Parameters:
417
    - objectives: list of objective expressions
418
    - weights: weight vector for objectives
419
    
420
    Returns:
421
    - Expression: weighted sum objective
422
    """
423
    ...
424
```
425

426
Usage examples for new functions:
427

428
```python
429
import cvxpy as cp
430
import numpy as np
431

432
# Indicator function example - constrained optimization
433
x = cp.Variable(2)
434
y = cp.Variable(2)
435

436
# Define a constraint set
437
constraint_set = [cp.norm(x, 2) <= 1, x >= 0, y >= -1, y <= 1]
438

439
try:
440
    # Use indicator function to enforce constraints
441
    indicator_expr = cp.indicator(constraint_set)
442
    
443
    # Optimization with indicator function
444
    objective = cp.Minimize(cp.sum_squares(x - y) + indicator_expr)
445
    problem = cp.Problem(objective)
446
    problem.solve()
447
    
448
    print(f"Solution with indicator function: x={x.value}, y={y.value}")
449
    
450
except Exception as e:
451
    print(f"Indicator function example failed: {e}")
452

453
# Multi-objective optimization with scalarization
454
n = 5
455
x = cp.Variable(n)
456
A1 = cp.Parameter((3, n), value=np.random.randn(3, n))
457
A2 = cp.Parameter((4, n), value=np.random.randn(4, n))
458
b1 = cp.Parameter(3, value=np.random.randn(3))
459
b2 = cp.Parameter(4, value=np.random.randn(4))
460

461
# Multiple objectives
462
obj1 = cp.norm(A1 @ x - b1, 2)  # Least squares fit 1
463
obj2 = cp.norm(A2 @ x - b2, 1)  # Least absolute deviations fit 2
464
obj3 = cp.norm(x, 1)            # Sparsity regularization
465

466
objectives = [obj1, obj2, obj3]
467

468
# Weighted sum scalarization
469
weights = [0.5, 0.3, 0.2]
470
try:
471
    weighted_objective = cp.transforms.weighted_sum(objectives, weights)
472
    
473
    weighted_problem = cp.Problem(cp.Minimize(weighted_objective), [x >= -2, x <= 2])
474
    weighted_problem.solve()
475
    
476
    print(f"Weighted sum solution: {x.value}")
477
    print(f"Objective values: {[obj.value for obj in objectives]}")
478
    
479
except Exception as e:
480
    print(f"Weighted sum scalarization failed: {e}")
481

482
# Target-based scalarization
483
targets = [1.0, 0.5, 0.1]  # Target values for each objective
484
priorities = [1.0, 2.0, 0.5]  # Higher priority = more important
485

486
try:
487
    target_objective = cp.transforms.targets_and_priorities(objectives, targets, priorities)
488
    
489
    target_problem = cp.Problem(cp.Minimize(target_objective), [x >= -2, x <= 2])
490
    target_problem.solve()
491
    
492
    print(f"Target-based solution: {x.value}")
493
    print(f"Distance from targets: {[abs(obj.value - target) for obj, target in zip(objectives, targets)]}")
494
    
495
except Exception as e:
496
    print(f"Target-based scalarization failed: {e}")
497

498
# Log-sum-exp scalarization for risk-sensitive optimization
499
# Minimize risk-sensitive cost: log(E[exp(costs)])
500
n_scenarios = 10
501
scenario_costs = [cp.norm(A1 @ x - b1 + 0.1 * np.random.randn(3), 2) 
502
                  for _ in range(n_scenarios)]
503

504
try:
505
    # Stack scenario costs
506
    cost_vector = cp.hstack(scenario_costs)
507
    
508
    # Risk-sensitive objective using log-sum-exp
509
    risk_sensitive_obj = cp.transforms.log_sum_exp(cost_vector) - np.log(n_scenarios)
510
    
511
    risk_problem = cp.Problem(cp.Minimize(risk_sensitive_obj), [x >= -1, x <= 1])
512
    risk_problem.solve()
513
    
514
    print(f"Risk-sensitive solution: {x.value}")
515
    print(f"Individual scenario costs: {[cost.value for cost in scenario_costs]}")
516
    
517
except Exception as e:
518
    print(f"Risk-sensitive optimization failed: {e}")
519
```