Questions tagged [convex-optimization]

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.

Filter by
Sorted by
Tagged with
0 votes
0 answers
29 views

Reformulate a problem with concave objective function into a QP

I would like to convert this problem into a QP (Quadratic program). $$\text{Maximize } \sum_{k=1}^{K}\sum_{n=1}^{N}log2(1+p_{kn}b_{kn})\\ \text{subject to } \sum_{k=1}^{K}\sum_{n=1}^{N}p_{kn}\leq P_{0}...
user avatar
  • 1
0 votes
1 answer
49 views

Efficiently solving SDP relaxation of an integer quadratic program

I have an integer quadratic program of the form, \begin{align} \underset{x}{\max}&\;\;\|Ax-b\|_2^2\\ \text{subject to}&\;\;x\in{\bf Z}\geq0 \end{align} I'm currently using the (admittedly ...
user avatar
  • 443
0 votes
0 answers
74 views

optimization problem with L2-norm constraint

I am currently trying to solve a regression problem, which leads me to an optimization problem. Say that we have measured data ($\hat{S}(\omega)\in \mathbb{C}^{N\times N}$), and each entry of this ...
user avatar
  • 1
1 vote
0 answers
63 views

Help with CVXPY and Disciplined Convex Programming

I'm trying to recreate Figure 1 in this paper. This requires maximizing equation (19), which I have convinced myself is concave, but I am having trouble implementing it in CVXPY. Here is the code I ...
user avatar
1 vote
0 answers
27 views

Problem in parameterizing a CVXPY program

I am trying to parameterize a CVXPY program as I need to repeatedly solve the problem, but I noticed that when my parameters are complex numbers, CVXPY models the problem in each iteration. For ...
user avatar
  • 111
3 votes
1 answer
122 views

Questions regarding the result of the CVXPY

I want to optimize the function $$\min_{X \in \mathbb{S}^{n}_{+}} \mbox{tr} \left( C^T X \right) + \mbox{tr} \left( X^{-1} \right),$$ of which I optimize the equivalent problem $$\min \mbox{tr}\left(C^...
user avatar
  • 133
0 votes
1 answer
64 views

Why is a elementwise max not DCP?

I am trying to formulate a convex optimization problem using CVXPY. Everything works, except a constraint that does not seem to follow DCP rules. Let $D \in \Bbb R^n$ be a decision variable and let $Q$...
user avatar
0 votes
0 answers
58 views

Absolute value constraint in quadratic programming optimization

$$ argmin(x,y)=x^2+y^2+2y $$ $$ s.t.\ \ y=|x-10| $$ How can I convert the absolute value constraint to the constraint matrix (GX<=h, AX=b) in cvxopt?
user avatar
  • 109
12 votes
2 answers
1k views

How do I find the minimum-area ellipse that encloses a set of points?

I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
user avatar
2 votes
1 answer
88 views

Formulating this optimization problem

Suppose I want to minimize below objective function $\sum | g(x_i) \cdot I_{g(x_i)<0} |^2$ i.e, the latter penalty terms like $ |g(x_i)|^2 $ are only computed when $g(x_i)<0$. $|g(x_i)|^2$ are ...
user avatar
0 votes
0 answers
61 views

Comparing minimas of two different functions

The goal is to find vectors $x_u$ and $y_i$, both of the same length $f=64$, and to do this the following loss function is minimized: $$\sum_{u, i} (1 + \alpha \cdot r_{ui})(p_{ui} - x_{u}^{T}y_i)^2$$ ...
user avatar
0 votes
1 answer
82 views

successive convex approximation and Convergence

In successive convex approximation method, can the solution be considered to be an acceptable solution if the algorithm reaches the maximum number of iterations without noticeable convergence? or it ...
user avatar
0 votes
1 answer
62 views

Expressing a Constraint in an optimization problem

If I have a vector of M "continuous" decision variables (say it is called x) , and if I want a constraint to express that only one of them is allowed to have a nonzero value (i.e. no more ...
user avatar
6 votes
1 answer
231 views

Optimization problem

In the expression: $${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}}\, ,$$ $$\text{subject to tr}(\Omega)=1, \Omega \ge 0\, ,$$ where ${\Omega}$ is nonnegative and symmetric ...
user avatar
  • 81
2 votes
0 answers
81 views

Efficient solver of a Integer programming

I am solving an Integer programming using MATLAB, yet the efficiency is low. Here is the problem: Suppose $v$ is a $N \times 1$ vector. For $v_i \in v$, $v_i \in \{0,1\}$. $D$ is a 0-1 matrix, which ...
user avatar
  • 21
1 vote
0 answers
76 views

Maximizing $l_1$-normalized entropy using CVXPY

Suppose that $x = (x_1, ..., x_n)$ is a vector of variables and I would like to maximize the Shannon entropy of $\frac{|x|}{||x||_1}$ (i.e. the vector of absolute values of $x_i$, normalized to have $...
user avatar
0 votes
0 answers
41 views

Can this volume intgral be expressed as a convex function?

This question is related to the following: https://math.stackexchange.com/q/4151405/685910 - the context is summarized below for clarity. In the setting of convex optimization, I am looking for a ...
user avatar
  • 11
0 votes
0 answers
54 views

Equivalence between zero sum games and linear program

It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the ...
user avatar
  • 131
0 votes
0 answers
76 views

Relative interior requirement in Slater's condition

I'm reading Convex Optimization by Boyd and Vandenberghe. This is how they describe Slater's condition: What I don't understand is why it is necessary to enforce that $x$ be in the relative interior ...
user avatar
6 votes
0 answers
94 views

continuous analogues of Newton's method

Suppose we want to minimize some convex functional $J(u)$ where $u$ lives in some Banach space $V$. The classical Newton method $$\mathrm d^2J(u_n)(u_{n + 1} - u_n) = -\mathrm dJ(u_n)$$ can be viewed ...
user avatar
3 votes
1 answer
107 views

Log-Determinant constraints in SDP

This is a belated follow up to my question here, because I didn't want to tack questions onto questions. According to the Mosek documentation here, one possibility for expressing $t \leq log(det(X))$, ...
user avatar
0 votes
0 answers
104 views

CVXOPT intermediate step valuation stepping out of function domain of defintion

I am using CVXOPT, particularly to solve a nonlinear convex optimization problem. Either the objective function or the constraints involve some functions that are only defined in a strict subset of $\...
user avatar
  • 121
0 votes
0 answers
84 views

L2 norm optimization problem

I have an optimization problem where i need to find an image x, that is very close to x' such that: monitor(x') is valid but monitor(x) is invalid. (output is valid when the neural network output is ...
user avatar
  • 1
4 votes
1 answer
290 views

SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)

Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program? Assume my problem is something like $$\min\limits_x. \quad f(x)$$ $$s.t. \...
user avatar
  • 143
3 votes
0 answers
75 views

What is this QR-factorization-based preconditioning called?

I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization....
user avatar
  • 203
2 votes
0 answers
121 views

Understanding Illumination Optimisation Problem

I am a newbie to convex optimisation and I am learning with the aid of CVXPY. I am requesting for clarity on the illumination problem as described in Boyd & Vandenberghe lecture 1 slides here. I ...
user avatar
2 votes
1 answer
421 views

Why is CVXPY throwing a DCP error with cp.sqrt but no error with cp.norm

I am trying to use CVXPY to optimise signal-to-noise-plus interference ratio (SINR) for a visible light communication (VLC) system. I have one of my SINR constraints stated as \begin{equation} \...
user avatar
1 vote
1 answer
228 views

How to best code a problem with scipy, cvxpy or Convex.jl with given generated data

I have a curve fitting problem of the form: $$ \textbf{y} = f(\textbf{x}, a,b,c,d) + \varepsilon $$ $$ f(x, a,b,c,d) = \frac{b}{e^{x\cdot a}+c}+d $$ with the constraint \begin{equation} \begin{aligned}...
user avatar
  • 141
1 vote
2 answers
137 views

Solving a specific sparse linear system without dense materialization

I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form $$ \left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
user avatar
  • 113
2 votes
1 answer
128 views

Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint

I am wondering if there is a well-known transformation allowing one to solve convex optimization problems of the form $$\begin{array}{ll} \underset{x}{\text{maximize}} & r^T x\\ \text{subject to} &...
user avatar
  • 121
5 votes
0 answers
98 views

Generally quadratic convex problem with one non-convex term

How would you approach a standard convex quadratic problem with convex constraints but one non-convex term ? Say $|x|^{0.4}$. $$\min_x \frac{1}{2} x^{T}Qx + g^Tx + c^T \mathrm{sign}(x) |x|^{0.4} $$ ...
user avatar
  • 151
3 votes
1 answer
162 views

Project to nearest point on convex polytope

I have a point $y \in \mathbb{R}^d$ and a convex polytope $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \le ...
user avatar
  • 350
0 votes
1 answer
631 views

Norm constraint in CVXPY

I'm trying to implement the algorithm outlined in https://arxiv.org/abs/1211.5608 on a small scale. I have a linear operator $\mathcal{A}$ which is defined as $$\text{trace}(A^*_l(hm^*))$$ where $$A_l ...
user avatar
1 vote
1 answer
233 views

Solving a linear program with an active set method

Is it possible to solve a linear program with an active set method? If so what would be the similarities and differences to the simplex method?
user avatar
  • 13
7 votes
0 answers
278 views

Finding points inside cells of power (generalized Voronoi) diagram

Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by: $$\...
user avatar
1 vote
1 answer
138 views

Why am I getting this DCPError when my matrix is PSD?

...
user avatar
5 votes
2 answers
725 views

log(det(X)) in Semidefinite Programming

I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
user avatar
4 votes
1 answer
212 views

Underdetermined Minimum Volume Enclosing Ellipsoid

Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
user avatar
1 vote
1 answer
99 views

In which cases does the nonlinear conjugate gradient method take more than $n$ steps?

I have programmed a couple of Matlab implementations of nonlinear Conjugate Gradient methods (Fletcher Reeves and Polak Ribeire). However, I am concerned with how many steps it's taking to optimise ...
user avatar
2 votes
0 answers
136 views

Proving convexity of Frobenius norm and correlation function formulations of an optimization problem

I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting. Firstly, I would like to make the variables I used in the problem and ...
user avatar
  • 21
2 votes
0 answers
63 views

Interior point of convex polytope

Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
user avatar
2 votes
1 answer
141 views

Could the convex problem be tackled by CVX?

I want to solve the convex optimization as follows: \begin{align} \underset{X_1,X_2}{\min} &\ -\frac{1}{N}\sum_{i=1}^N\log\det\left(I+H_i^HX_2H_i\right)-\log\left[1+h^H(X_1+X_2)h\right]\\ &\...
user avatar
1 vote
1 answer
91 views

Disciplined convex programming expression of $x\sqrt{1-x}$

Anyone have an idea for a DCP (disciplined convex programming) representation of the concave function $x\sqrt{1-x}$, which is has domain $[0,1]$? The Taylor series about $x=0$ is $$x - \frac{x^2}{2}...
user avatar
2 votes
1 answer
337 views

Gradient descent in constrained optimization of barrier function

This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained ...
user avatar
  • 31
5 votes
0 answers
111 views

Minimum of quadratic assignment (QAP) with convex objective

Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem: $$ \min_{\textrm{permutation matrices }P} \mathrm{tr}(BP^\top AP+C^\top ...
user avatar
6 votes
1 answer
119 views

Sparsity-Promoting Convex Optimization Over Simplex

Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + ...
user avatar
  • 402
3 votes
1 answer
742 views

Convex optimization with constraints involving matrix inverse

I have the following convex optimization problem. I would like to ask is there any efficient way to solve it in Python? Can I use CVXOPT package? If so, any detailed instruction? Thanks a lot. $$ \...
user avatar
3 votes
0 answers
116 views

A maximization problem, with motivation in machine learning

Consider the minimization problem described this paper. Let $f_{\lambda}$ be the minimizer. As a part of extending my work, I am able to show the following facts $$\lim_\limits{\lambda \to 0}\|f_{\...
user avatar
  • 141
4 votes
1 answer
85 views

Geometric Programming - symbolic version

I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
user avatar
3 votes
2 answers
877 views

Convexity of Sum of $k$-smallest Eigenvalue

If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $. Define the function as $f(A)=\sum_{i=1}^{k} \...
user avatar
  • 89

1
2 3 4 5