Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
2 votes
2 answers
92 views

Can this problem be solved using convex optimization?

I have the following problem: $$\begin{align} \max & \quad \frac{\mu^\top x - c^\top|x - x_0|}{x^{\top}\Sigma x} \tag{1} \\ \text{subject to } & \quad x \leq \mathbb{1} \tag{2}\\ & \quad ...
ron burgundy's user avatar
2 votes
0 answers
67 views

How to solve this nonconvex problem in python

I have the following problem to solve minimize $$\sum_{i=1}^I\sum_{k=1}^Kx_{i,k}.$$ The constraints are as follows: $$\sum_{i=1}^I\sum_{j=1}^J\ln(c+x_{i,k}A_{i,j,k})\geqslant B_k,\forall k,$$ and $$\...
zdm's user avatar
  • 121
1 vote
1 answer
79 views

How does the slack variable work in the problem formulation?

Recently I am reading a paper. In it, after they achieve eq(15), which is $$ \operatorname{Tr}(\boldsymbol{Q})-\sqrt{2 \ln (1 / \rho)} \sqrt{\|\boldsymbol{Q}\|_F^2+2\|\boldsymbol{r}\|^2}+\ln (\rho) \...
tyrela's user avatar
  • 133
2 votes
0 answers
61 views

Equivalency of lasso problems

In the literature, I've seen the lasso problem phrased as the minimization of: $$\frac12x^tAx-x^tb+\lambda||x||_1$$ or of: $$\frac12||Ax-b||_2^2+\lambda'||x||_1=\frac12x^tA^tAx-x^tA^tb+b^tb+\lambda'||...
GS101's user avatar
  • 21
0 votes
1 answer
72 views

Why using large bound to supplement inifinity in interior point method can be bad

Here in the documentation of mosek (https://docs.mosek.com/latest/pythonfusion/debugging-numerical.html) we see: Never use a very large number as replacement for infinity . Instead define the ...
Matt Frank's user avatar
2 votes
1 answer
123 views

How to formulate a convex expression to minimize the difference between Frobenius norm of a positive semidefinite matrix and a positive value

So what I am trying to do is to minimize the distance between the Frobenius norm of a PSD matrix and a real positive value, which can be formulated as $$\min \left|\|\textbf{P}\|_F - J\right|^2$$ ...
tyrela's user avatar
  • 133
0 votes
1 answer
79 views

How to formulate the convex hull which is a regular polygon on the complex plane

Suppose that I have a convex regular polygon with $k$ vertices on the complex plane, and the first vertex lies on the positive real axis. Is there a neat way to formulate the convex hull with the ...
tyrela's user avatar
  • 133
0 votes
0 answers
88 views

How to determine whether the symmetric stiffness matrix is positive definite or not? Is it related to the problem?

For two-dimensional or three-dimensional elliptic equations, when will the stiffness matrix be asymmetric and positive definite? This affected the solution efficiency so much that I had to choose an ...
Darcy's user avatar
  • 21
3 votes
0 answers
61 views

What 2nd-order optimization algorithms have convergence guarantees for strictly- but not strongly-convex problems?

A function $f$ is strictly convex if $$f((1 - \lambda)x + \lambda y) \le (1 - \lambda)f(x) + \lambda f(y)$$ with equality if and only if $x$ and $y$ are equal. This implies that the second derivative ...
Daniel Shapero's user avatar
1 vote
1 answer
45 views

Name this optimum-within-convex-hull algorithm: State is a convex combination of hull vertices; Nonnegativity ensured by reparameterization

I'm looking for the "official" name(s) for a procedure for optimizing a convex loss function over a convex subset. This seems to be a default/naïve algorithm that folks come up with before ...
MRule's user avatar
  • 153
1 vote
0 answers
54 views

Beyond the LP relaxation of binary least squares

I have a binary quadratic program with a convex objective function, of the form, \begin{align} \text{minimize}\;\;& x^tAx+b^tx\\ \text{subject to}\;\;& x_i\in\{0,1\} \end{align} where $A$ is ...
Set's user avatar
  • 503
1 vote
0 answers
66 views

min(f(x)) is convex or concave based on type of f(x)

i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
Maria's user avatar
  • 11
2 votes
0 answers
98 views

Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?

Crossposted at MathOverflow Consider a quadratic programming problem with the following format: $$ \text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\ $$ $$ \text{s.t.} Ax\leq b, \\ x\geq 0 $$ where $D$ is a $...
ximeng fan's user avatar
3 votes
1 answer
94 views

A question related with $p$-Laplacian and conjugate gradient method

I have the following energy functional of $p$-Laplacian equation: $$ E(u) = \frac{1}{p} \int_{\Omega} |\nabla u|^p dx $$ for $2.8 \leq p \leq 5$. My goal is to minimize the energy functional by using ...
User124356's user avatar
1 vote
1 answer
162 views

Space complexity of a semidefinite program

What is the space complexity of a semidefinite program (SDP)? What is the answer to the same question for convex optimization problems in general?
Gaurav Saxena's user avatar
2 votes
0 answers
99 views

Parameter choice rules for L1 regularization?

I am solving an L1 regularized least squares of the form like: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
yourds's user avatar
  • 121
0 votes
1 answer
56 views

Optimization of the log-absolute: reformulating to DCP-compliant on Julia

I am trying to reformulate this optimization problem in order to get a DCP-complaint expression on Julia (I am using the ...
Rubem Pacelli's user avatar
2 votes
1 answer
86 views

Convex optimization: what is atom library?

By reading the CVX users' guide, I frequently came across with the term "atom library", which I suppose to be a set of functions that one must use to construct mathematical expressions on ...
Rubem Pacelli's user avatar
6 votes
1 answer
226 views

Minimum distance from point to surface

I’m looking for code that is well-suited to solving a fairly simple minimization problem: I have a reference point $\mathbf p$ in 3D space, and I want to minimize $\|\mathbf x - \mathbf p\|^2$ subject ...
bubba's user avatar
  • 119
3 votes
2 answers
854 views

Why slack variables for inequality constraints?

When solving constraint optimization problems with (primal dual) interior points methods, I often read (e.g. on slide 17) that one should not use the inequality constraints $g(x)\leq 0$ directly, but ...
Manuel Schmidt's user avatar
0 votes
1 answer
78 views

Distributed Optimization of Least Powers

I have $F_i \in \mathbb{R}^{m}$, $y_i \in \mathbb{R}$, $\beta_i \in (1,\infty)$ for $i = 1,\ldots, n$. I would like to solve the following convex optimization problem $$\min_{x} \sum_{i = 0}^n |F_i\...
JEK's user avatar
  • 23
3 votes
1 answer
140 views

Rewriting quadratically-constrained optimization problem as a semidefinite program

Suppose $A,H$ are positive definite matrices and $\alpha,t$ are scalars. Is there a way to massage the following problem into a form suitable for a specialized solver? $$\begin{array}{ll} \underset{\...
Yaroslav Bulatov's user avatar
2 votes
0 answers
40 views

Unconstrained convex optimization: correlation between dimensionality and Lipschitz constant

The author of the SIAM News article "Optimization Theory and Perspectives on the Field of Machine Learning" mentions: ... For unconstrained convex optimization, GD (gradient descent) ...
Anton Menshov's user avatar
  • 8,672
1 vote
2 answers
505 views

What algorithm does CVXPY actually use to solve semidefinite programs with the constraints of the form $\sum\limits_i E_iXE_i^T \succ B$?

Crossposted on Mathematics SE CVXPY is a famous software as a solver for optimization problems. Nowadays, I use it to run a program presented in a paper, the Example 7.1, and the program runs as ...
qmww987's user avatar
  • 113
0 votes
0 answers
43 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}...
amhen's user avatar
  • 1
0 votes
1 answer
142 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 ...
Set's user avatar
  • 503
0 votes
0 answers
844 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 ...
Hector's user avatar
  • 1
1 vote
0 answers
157 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 ...
Hudson Hochstedler's user avatar
1 vote
0 answers
289 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 ...
Nash J.'s user avatar
  • 111
3 votes
1 answer
833 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^...
The One's user avatar
  • 133
0 votes
1 answer
448 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$...
Sahil Gupta's user avatar
0 votes
0 answers
218 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?
lichgo's user avatar
  • 109
14 votes
2 answers
4k 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 ...
physicsnovice's user avatar
2 votes
1 answer
99 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 ...
Matt Frank's user avatar
0 votes
0 answers
65 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$$ ...
kevin811's user avatar
0 votes
1 answer
200 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 ...
Israa Ahmed's user avatar
0 votes
1 answer
68 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 ...
Israa Ahmed's user avatar
6 votes
1 answer
241 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 ...
tjufan's user avatar
  • 81
2 votes
0 answers
128 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 ...
Bruno's user avatar
  • 21
1 vote
0 answers
109 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 $...
Marcin Kotowski's user avatar
0 votes
0 answers
71 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 ...
asdf's user avatar
  • 131
0 votes
0 answers
228 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 ...
nkyraf33's user avatar
7 votes
1 answer
207 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 ...
Daniel Shapero's user avatar
3 votes
1 answer
253 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))$, ...
nick.schachter's user avatar
0 votes
0 answers
145 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 $\...
Hans's user avatar
  • 121
1 vote
1 answer
386 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 ...
S i's user avatar
  • 11
5 votes
1 answer
796 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. \...
FooBant's user avatar
  • 153
3 votes
0 answers
160 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....
J.Galt's user avatar
  • 203
2 votes
0 answers
240 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 ...
Supremum's user avatar
2 votes
1 answer
1k 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} \...
Supremum's user avatar

1
2 3 4 5 6