Formulate and solve a simple conic programs in cvxpy language [closed]

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 1

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).