0
$\begingroup$

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!

$\endgroup$

closed as too broad by Mauro Vanzetto, GoHokies, Brian Borchers, Christian Clason, Kirill Jan 25 at 14:35

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ better ask over on Stack overflow (tag: cvxpy) and/or the CVXPY Google group. I think you should learn the basic cvxpy syntax sooner, rather than later. Otherwise you can't be reasonably confident that the "plug-and-play" code is correct. $\endgroup$ – GoHokies Jan 21 at 11:01
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! BTW, i fixed a typo in the question: objective should be $b^Tx$ not $a^Tx$. $\endgroup$ – dohmatob Jan 22 at 2:05
  • $\begingroup$ @dohmatob: Were you able to figure out how to incorporate that typo fix into the code above? $\endgroup$ – Richard Jan 27 at 15:22
  • $\begingroup$ lol, sure. BTW, your answer above was precisely what i needed to get me familiarized with syntax and semantics of cvxpy / cvxopt. Thanks! $\endgroup$ – dohmatob Jan 27 at 15:42
  • 1
    $\begingroup$ @dohmatob: Happy to be of service. If this answer adequately answered your question feel free to upvote it by clicking the gray arrow next to it, and/or to accept it by clicking the outline of the checkmark :-) Also, cvxpy has discplined geometric programming which can solve a large class of interesting problems using a similar syntax. $\endgroup$ – Richard Jan 27 at 16:03
  • $\begingroup$ Answer accepted. Thanks for the ref on DGP. $\endgroup$ – dohmatob Jan 28 at 7:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.