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!

| cite | improve this question | | | | |
$\endgroup$
  • $\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 '19 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).

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks! BTW, i fixed a typo in the question: objective should be $b^Tx$ not $a^Tx$. $\endgroup$ – dohmatob Jan 22 '19 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 '19 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 '19 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 '19 at 16:03
  • $\begingroup$ Answer accepted. Thanks for the ref on DGP. $\endgroup$ – dohmatob Jan 28 '19 at 7:59

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