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
1 answer
114 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
  • 21
0 votes
1 answer
73 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
  • 21
0 votes
0 answers
66 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
  • 1
3 votes
0 answers
59 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
40 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
50 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
  • 471
1 vote
0 answers
63 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
89 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
143 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
93 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
53 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
81 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
205 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
728 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
131 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
1 vote
0 answers
22 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,602
1 vote
2 answers
387 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
42 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
129 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
  • 471
0 votes
0 answers
714 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
145 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
223 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
725 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
381 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
181 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
13 votes
2 answers
3k 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
96 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
175 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
239 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
123 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
107 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
64 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
178 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
6 votes
1 answer
194 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
210 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
143 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
287 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
696 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
143 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
204 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 vote
1 answer
481 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}...
ecjb's user avatar
  • 141
1 vote
2 answers
144 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{...
ckfinite's user avatar
  • 113
2 votes
1 answer
199 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} &...
Derek's user avatar
  • 121
5 votes
0 answers
104 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} $$ ...
Kreol's user avatar
  • 151
3 votes
1 answer
195 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 ...
D.W.'s user avatar
  • 400

1
2 3 4 5