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.
4
votes
2answers
72 views
Optimization algorithm selection for 3 variable integer
I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$
it is very expensive to evaluate
$x,y,z \in \mathbb{Z}$
0 < x < 10
0 < y < 30
0 < z < 100
I thought it was convex, not ...
3
votes
2answers
111 views
Quadratic Programming: Quadprog
Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem:
Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to
$e^Tw = 1$ and $w \geq 0$
using a solver I ...
3
votes
1answer
77 views
Biconvex optimization problems
Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
3
votes
3answers
139 views
How to prove that a function is convex?
I'm calculating the gradient of a function with a symbolic math library called theano. Then I'm using gradient descent to find the minimum of the function.
I'd like to prove that the minimum is a ...
0
votes
2answers
51 views
Analytical form of the minimum of a function with absolute values
I would like to find the analytical form of the point which minimizes the following function:
$$
f(x_T) = \frac{1}{T} a_1 (x_T-x_0)^2 + a_2 |x_T-x_0| + T a_3 + \sum_{i=1}^M p_i \left[b_{1i} (x_T - ...
3
votes
2answers
138 views
Finding A and X such that AX = 0, X is positive non-zero, and A is sparse
I apologize if this is a naive question. I'm trying to create some boostrap data for a system of linear, ordinary differential equations at steady state.
Since the equations represent the ...
6
votes
1answer
80 views
Why is the Dual problem preferred for Maximal Margin Classification?
The primal problem is
$$\min_{w,b}\frac{1}{2}w^Tw$$
$$s.t. f_i(w)=1-y_i(w\cdot x_i+b)\leq0$$
Where $y_i=\pm1$.
Instead of using Gradient Descent directly, the dual is usually solved:
...
1
vote
1answer
38 views
Confusion related to convexity of 0-1 loss function
I am a bit confused why the 0-1 loss function is not convex. What's wrong with it?
3
votes
5answers
268 views
MATLAB's CVX Package to minimize $\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$
I would like to minimize in matlab the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ where $S\in \mathcal{M}_{m,m}$ symmetric positive definite which is definitely convex function.
So I ...
1
vote
1answer
45 views
Confusion related to interior point method for optimization
I have this little confusion related to interior point method. In this method we use the log barrier function to approximate the real barrier which is not differential
Now when we find the optimal ...
2
votes
1answer
26 views
Confusion while proving logdet function to be concave
I was going through this lecture related to convex optimization. It was proved that logdet function is concave. However, I didn't get the derivation at a part
I didn't get how the step marked in ...
4
votes
1answer
82 views
Confusion related to convexity and concavity of a function
I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification
In that paper, they have mentioned about ...
0
votes
0answers
31 views
Robust Counterpart of an uncertain LP
Consider the following robust optimization problem:
min c'x
s.t.: $Ax\geq b \;\;\forall (A,b)\in \mathcal{U}$.
Why can the robust counterpart of the problem be written in this form?
$min_x{\{ ...
0
votes
1answer
27 views
Polynomial solvability [duplicate]
Consider the following optimization problem:
Min$_{x}$ $\qquad \sum_{(i,j,t,s)\in I_r}||x_ix_j-x_tx_s||^2$
S.t.: $\qquad x\in \mathcal{C} ;$
where $x=(x_1,x_2,...x_n)$
and $\quad x_j\geq 0\;\; ...
1
vote
1answer
49 views
Feasibility checking
Consider the following optimization problem:
$Min\;\;\; CX$
$AX\geq b$
$x_ix_j= x_s x_t\;\;\; i\neq j \neq s\neq t$
$x_j\geq 0;$
Where $A$ is the adjacency matrix and $C$ is a constant vector.
...
2
votes
1answer
73 views
polynomial time solvability
Consider the following optimization problem:
$Min \qquad C^TX$
S.t.: $\qquad AX=0;$
$x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$
$X=(x_1,x_2,...x_n)$
and $\quad x_j\geq 0\;\; ...
2
votes
1answer
64 views
Nonlinear bad constraints
I have an optimization problem with linear objective function. The constraints are in two different groups. The first set of constraints are linear while the second set is nonlinear. The nonlinear ...
3
votes
1answer
80 views
Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables
I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this.
Read ...
2
votes
1answer
53 views
Extreme points from constraint expression of convex space
I'm looking for the extreme points of the convex set $S\subset [-1,1]^{n\times 3}$ with $r\in S$ such that
\begin{equation}
r_{i} \ge r_{k} \iff i\ge k,
\end{equation}
where the first inequality ...
6
votes
2answers
115 views
Max of a convex combination over a convex hull of real variables
I have the following linear program:
$$
\begin{array}{cc}
\text{Maximize} & a^T x \\
\text{Subject to} & x_{\min} \leq x \leq x_{\max} \\
& \mathbf{1}^T x = 1
...
1
vote
1answer
42 views
Existence of a solution at a stationary equation for quadratics
Given a convex quadratic function $f(x)$, to obtain a solution for which $f(x)$ has minimal value one sets $\nabla f(x)=0$, and solves for $x$. Suppose that the result of differentiation of convex ...
4
votes
1answer
51 views
Minimal point of a intersection of $n$ convex sets is always the minimal point of the intersection of two convex sets?
I have the intuition that the minimal point (in the sense of having the lowest value in one of the Euclidean space dimensions) of a intersection of $n$ convex sets is always the minimal point of the ...
2
votes
2answers
212 views
Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is ...
7
votes
2answers
410 views
CVXOPT VS. OpenOpt
CVXOPT: http://abel.ee.ucla.edu/cvxopt/index.html
OpenOpt: http://openopt.org/Welcome
What's the relation between them?
What are the advantages/disadvantages of them, respectively?
BTW, is there ...
6
votes
2answers
76 views
Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?
I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise.
The other variables in the linear ...
6
votes
3answers
159 views
How to intellligently attempt to rule out convexity?
I want to minimize a complicated objective function, and I'm not sure if it is convex. Is there a nice algorithm that attempts to prove that it is not convex? Of course the algorithm could fail to ...
7
votes
1answer
119 views
How to calculate the maximal ellipsoid in a given polyhedron
I am faced with the problem of finding the ellipsoid $B$ ($B$ is a symmetric positive definite matrix) of maximal volume within a convex set $C$ given as a set of linear inequalities $C=\{x| a_i^T x ...
2
votes
1answer
169 views
Solving PSD matrix in Newton's method
I have functions defined as follows:
$f1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f2(A) = \sum\|x_k-x_l\|^2_A$ where A is PSD matrix, x are number vectors.
Task is to minimize ...
2
votes
1answer
133 views
Polynomial Regression using Semidefinite Programming
I'm trying to design the frequency response function for a low-pass filter. I need the function to be polynomial and to fulfill the following constraints: the coefficients must sum to 1, the function ...
7
votes
2answers
406 views
How is geometric programming different from convex programming?
How is (generalized) geometric programming different from general convex programming?
A geometric program can be transformed into a convex program, and is typically solved by an interior point ...
3
votes
3answers
269 views
What is the best way to solve Ax = b (with A large, spd, sparse, banded and poorly conditioned)?
I'm trying to solve
$Ax = b$
given a vector $b$ and a large, symmetric positive definite, sparse, banded matrix $A$ that has a very poor condition number.
I know several iterative methods that ...
6
votes
3answers
1k views
What are the advantages/disadvantages of interior point methods over simplex method for linear optimization?
As I understand it, since a solution to a linear program always occurs at a vertex of its polyhedral feasible set (if a solution exists and the optimal objective function value is bounded from below, ...
5
votes
3answers
236 views
Does there exist an arbitrary-precision convex optimization solver?
I have a relatively simple convex optimization problem that involves less than 100 variables but contains a terribly ill-conditioned matrix. I have tried CVX and CPLEX; even though both can typically ...
