Formulate and solve a simple conic programs in cvxpy language

An answer to this question on the Scientific Computing Stack Exchange.

Question

Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $|a|2 \le r$. Define $C(a) := {x \in \mathbb R^p | |x+a|_2 \le r,;|x|\infty \le \epsilon}$, and assume it is non-empty.

Question

  • (A) How to formulate and solve the problem problem $\sup_{x \in C(a)} b^Tx$ in the cvxpy language ?
  • (B) Same question with $|a|2 = r$ and $C(a) := {x \in \mathbb R^p | |x+a|_2 = r,;|x|\infty \le \epsilon}$

Related to: https://math.stackexchange.com/q/3080805/168758

Disclaimer: I've never done cvxopt / cvxpy before. I plan to learn the syntax later. For now, I just want something to plug-and-play. Thanks!

Answer

You can solve Question A as a second-order cone program like so:

#!/usr/bin/env python3
import cvxpy as cp 
import numpy as np
##########################
#Question A
##########################
n = 50                          #Arbitrary number of dimensions
r = 10                          #Arbitrary radius
e = 3                           #Epsilon value
a = np.random.random(size=50)   #Generate random a vector
a = a/np.linalg.norm(a, ord=2)  #Scale to unit length
a = r*a                         #Scale to radius
x = cp.Variable(shape=n)        #x, a variable to be optimized
cons = []                       #List of constraints
#See cvxpy's atoms here: https://www.cvxpy.org/api_reference/cvxpy.atoms.html
cons += [cp.norm(x+a,2)<=r]     #Note that we are using cvxpy's `norm` function!
cons += [cp.norm_inf(x)<=e]
#Objective
obj = cp.Maximize(cp.sum(a*x))
#Formulate problem
prob = cp.Problem(obj, cons)
#Solve problem
optval = prob.solve()
print("Optimum value = {0}".format(optval))
print("x = {0}".format(x.value))

Question B you can't solve using plug-and-play with cvxpy because the problem is non-convex (you're optimizing over the surface of an ellipsoid).