Tagged Questions
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.
2
votes
1answer
66 views
+50
How to transform this SOCP to the format required by cvxopt
I'm new to SOCP and want to try to get familiar with the format and how to solve it with cvxopt in python. However, for a simple toy example I'm struggling to get ...
0
votes
1answer
48 views
How to efficiently solve a QCQP with “dynamic” constraints in Python?
I want to solve a QCQP in Python. It is a problem from finance: maximise return (linear function) given some linear constraints and one quadratic constraint that turns it into a QCQP. Formally,
$$\...
0
votes
0answers
39 views
Metric selection and scale-based preconditioning in quadratic optimization problem
I'm going to use scale-based preconditioning in a quadratic optimization problem: minimize $ x^T Q x + p^T x$ such that $ A x + b = 0$ and $D x + E \leq 0$, I want to speed up finding the optimal $x$ (...
1
vote
1answer
169 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
1
vote
0answers
102 views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
1
vote
0answers
31 views
Best Possible Convex bounds for optimization problems
Suppose we have a primal problem
$$
p^{*}=\min_x f(x), \\\text{s.t.}~~ h_i(x) \leq 0,
$$
where $f(.)$ and $h_i(.)$ are possibly non-convex.
Then its Lagrangian is
$$\mathcal{L}(x,z_i)= f(x) + \...
2
votes
0answers
21 views
Domain for convex perspective function
The perspective of a function $f : \mathbb{R}^n \to \mathbb{R}$ is the function $g: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}$ where $g$ is defined as $$g(x,t) = tf(x/t)$$ with $$\mathbf{\text{dom}...
1
vote
0answers
57 views
Nonlinear least square optimization
Problem description
Given data at many time instance $t$,
$$\min _{\alpha, \Lambda, \beta} \lVert y(t) - \alpha e^{\Lambda t} \beta \rVert_F$$
with $$ \lVert \alpha \rVert_2^F = 1 $$
where $y(t) \...
3
votes
2answers
129 views
How do I check if a loss function can achieve its minimum?
For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
6
votes
1answer
198 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
0
votes
0answers
50 views
Clarifying a dual problem solution
I’m referring to this question on MathSE about the sum of $k$ largest eigenvalues of a symmetric matrix as an SDP-problem.
I want to solve the maximization problem. As the dual problem is always ...
0
votes
0answers
31 views
Convergence rate of alternate convex search
Is there any reference regarding the convergence rate of alternate convex search? I tried to find it on google but got no luck.
Alternatively, do u think it can be found/proved just like gradient ...
1
vote
1answer
151 views
How to Solve Optimisation Problems using Penalty Functions in Python
I am working on a implementing a simple quadratic optimisation problem:
$$\min _x \; {\underline{x}}^T Q {\underline{x}}$$
$$s.t. \,\quad {\underline{\mu}}^T{\underline{x}} = R^*$$
$$ \quad \quad \...
1
vote
0answers
12 views
How does the MADS algorithm work in practice
Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization
I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
1
vote
2answers
63 views
Making difference of log constraints convex
I have the discrete likelihood estimation problem $\max \sum m_i\log p_i $ where $m$ is a given vector of length $n$. The constraints are $0 \preceq p \preceq 1$, $\sum_{i=1}^n p_i = 1, $ and one ...
5
votes
2answers
127 views
What is the most appropriate derivative free optimization algorithm
We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$.
If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
0
votes
1answer
153 views
How to define the derivative for Scipy.Optimize.Minimize
I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...
4
votes
1answer
106 views
Ways to speed up solving an LP with Google's ortools
I'm having an issue solving an LP of the form:
$$\min z = c^Tx$$
$$\text{s.t.}$$
$$Ax \geq b$$
$$x\geq p$$
$1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$
The specific problems I'm running into ...
1
vote
0answers
44 views
Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs
A standard Quadratically Constrained Quadratic Program (QCQP) is of the form:
$$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x
$$
$$
subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
4
votes
0answers
34 views
Obtainting KKT for QSDP for the trace inequality constraint
I am working on developing my own solver(for implementation on hardware), based on IPM for following problem:
\begin{equation}
\begin{split}
\min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\
\text{...
4
votes
3answers
134 views
How can I use Projected Gradient Descent for this optimization problem with constraint?
Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that
$$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
1
vote
0answers
86 views
Reformulate a strictly convex QP problem containing absolute value term
Can the following strictly convex optimization problem be reformulated into a standard form that is also a strictly convex problem?
$$\begin{align}
&\text{Minimize }\frac{1}{2} x^T Q x + c^T|x| \\...
3
votes
1answer
118 views
Why do active set methods or the simplex method pivot only one variable at a time?
Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
1
vote
1answer
150 views
How can I solve on a computer a large projection problem with redundant constraints?
This question is the essence of this one. After we remove all the cruft, we can recast it as follows:
Problem: Given $b \in \mathbb{R}^n$, $C\in \mathbb{R}^{n\times m}$, and $g\in \mathrm{Range}(C^...
3
votes
1answer
138 views
Imposing special structure on Positive Semi-Definite matrix
I am trying to implement the algorithm described in reference 1 using cvxpy. However I am struggling to constrain the matrix $Z_j$ as described in equations (33-35)....
4
votes
2answers
293 views
Quadratic programs with rank deficient positive semidefinite matrices
Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
3
votes
1answer
48 views
Linear programming with stochasticity?
Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution.
Now, I would like to solve the same problem but with stochasticity ...
4
votes
1answer
196 views
Translating a nuclear norm constraint to an LMI constraint
I'm attempting to solve a convex optimization problem where one of the constraints is
$$\|M\|_* \leq a$$
where $\|M\|_*$ denotes the nuclear norm of matrix $M$. I'm using CVXOPT in Python to solve ...
0
votes
1answer
150 views
Line search bracketing for proximal gradient. Is it good idea?
Maybe my question is obvious but i cannot find any good source which answers it
I trying to learn about proximal gradient. One thing which is not clear for me is particular algorithm for line search.
...
5
votes
1answer
114 views
Largest hypercuboid inside a polyhedron
Given a polyhedron $\mathbf{Ax} \leq \mathbf{b}$, how to find the largest hypercuboid, with unknown center $\mathbf{x_{0}}$ and side lengths $2\epsilon_{i}$, which are aligned along the co-ordinate ...
2
votes
1answer
115 views
Minimize the number of unique elements in a vector
I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector).
Note that I'm not asking for minimization of nonzero elements (rank ...
1
vote
0answers
71 views
Generate discrete set of points in a feasible region
I have two vectors which specify the bounds $x_{min}$ and $x_{max}$ of the sample space. Also, it has to satisfy the linear constraint $Ax \leq b$.
How to generate an evenly spaced set of points, ...
1
vote
1answer
26 views
constraint satisfaction via an LD solution
I'm going through the article in the following link lately and one point confuses me a lot. https://arxiv.org/pdf/1509.05001.pdf
So, the goal of this paper is to solve the following constrained ...
0
votes
1answer
99 views
lagrangian dual and linear programming
I'm going through an article lately and there is one point which is very confusing. So, we have the following original constrained binary quadratic problem as the following. The pre-assumption of ...
4
votes
0answers
71 views
linear relaxation of an optimization problem
I'm reading an article lately, and there is one point which confuses me. So, we have the following constrained binary quadratic problem.
min $x^{T}Qx$
with the constraints that $Ax≤b$
and $x\in {0,...
0
votes
1answer
60 views
Perturbation in bounds given the perturbation to constraints
Given a feasibility problem with both inequality and equality constraints, I'm interested in the sensitivity of the bounds of the region to changes in the constraints. To help with answering the ...
1
vote
0answers
122 views
Variable elimination in linear programming
I have a linear program of the form
$$\underset{P,\;g}{\text{Minimize}}\hspace{3mm}c^Tg$$
\begin{align}
\hspace{17mm}\text{Subject to}\hspace{3mm}AP_{\cdot,j}&=\begin{bmatrix}
-g\\
d
\end{...
1
vote
0answers
50 views
Is there any implementation of Nesterov's paper: Gradient methods for minimizing composite functions
I worked on a method based on this paper, "Gradient methods for minimizing composite functions". But unfortunately, every time I code it doesn't work. Even I investigate inequalities of the paper ...
3
votes
3answers
202 views
How to debug a constrained optimization algorithm?
I have implemented a saddle point optimization problem based on the algorithm by Prof. Nesterov, primal-dual[1].
Unfortunately, it doesn't work. It seems it is converging. But unfortunately, not to ...
1
vote
1answer
97 views
SOCP: Recovering primal from dual
Consider the following second-order cone program (SOCP):
$$
\begin{array}{rl}
\min_x & c^\top x\\
\mathrm{s.t.} & \|A_ix+b_i\|_2 \leq c_i^\top x+d_i \ \forall i
\end{array}
$$
Suppose I solve ...
3
votes
1answer
146 views
Minimizing linear objective on intersection of convex sets
Suppose I wish to solve the following optimization problem:
$$
\begin{array}{rl}
\min_{\mu\in\mathbb{R}^n} &\mu^\top c\\
\textrm{subject to} & \mu\in C_1\cap C_2\cap\cdots\cap C_k,
\end{array}
...
2
votes
2answers
89 views
Question concerning accumulation point
Suppose that we have to find an optimal solution $x^*$ to an optimization problem involving some function $f$, such that $0\in\partial f(x^*)$ where $\partial$ denotes the subdifferential.
Let $(x_n)...
1
vote
1answer
142 views
How to deal with quadratic constrain in semidefinite programming
I am using CVX to solve an optimization problem. One of my constraints in the problem is
$$M \succeq \eta {\eta}^T$$
where $M$ is a square matrix and $\eta$ is a column vector (both $M$ and $\eta$ ...
5
votes
0answers
340 views
Precision of ratio constraint in a linear program [closed]
I am trying to solve a LP in which one of my constraints is of the form
$$\frac{A(x)}{B(x)} = 1$$
I transform this constraint into a linear one
$$A(x) - B(x) = 0$$
However when CPLEX solves the ...
0
votes
1answer
80 views
An efficient algorithm to solve this convex optimization problem
I have a convex optimization problem as follows:
\begin{align*}
maximize_{x\in R^n} &\sum_{i=1}^n a_i log(x_i)\\
st\quad & \sum_{i=1}^n p_{ij} (x_i-1) = 0 \quad \forall j\\
...
3
votes
0answers
62 views
“Solution path” for quadratic program as regularizer changes
I am solving a quadratic program with regularization parameter $\alpha\geq0$ to get the solution to a problem of the form
$$
p(\alpha):=
\arg\min_{p\in\mathbb{R}^n}\ [\alpha(v^\top p)+f(p)],
$$
where $...
1
vote
0answers
147 views
Open Source Quadratic Programming with Piecewise Linear Objective
I am looking for an open source solver to solve the a quadratic programming problem with an additional piecewise linear objective, as show below. The problem is fairly small ($\mathbf{x}$ is a vector ...
1
vote
0answers
319 views
Are linear programming algorithms faster than quadratic programming algorithms?
I have an objective function that I can write either in quadratic programming (QP) such as
$$\sum_{i=1}^N \sum_{j=1}^N C_{ij}^2$$
or as an LP problem
$$\sum_{i=1}^N \sum_{j=1}^N |C_{ij}|$$
which can ...
8
votes
2answers
590 views
Why are convex problems easy to optimize?
Motivated by this top answer to the question: Why is convexity more important than quasi-convexity in optimization?, I am now hoping to understand why convex problems are easy to optimize (or at least ...
2
votes
1answer
57 views
Doubt regarding principled approach towards approximating the Hessian
In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
