Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
1answer
10 views

Reducing KKT system

I was using CVXOPT library to solve one of my quadratic programming problem. I found that, CVXOPT library solves KKT system efficiently by reducing a 3x3 matrox into 2x2 blocks which has the following ...
0
votes
0answers
8 views

maximize a sum of unit fractions (without containing a subset of sum 1)

Let $ u \ge 2 $ be fixed. Then consider: $ S(u)=\max\left\lbrace \sum_{i=1}^{u+1} \frac{c_i}{t_i} \, \middle| \, 2 \le t_1 \le t_2-1 \le \ldots \le t_{u+1}-1, \, t_i \in \mathbb{N}, \, c_i \in \...
1
vote
0answers
9 views

Benders decomposition Master Problem

I am currently working on implementation of Bender's Decomposition for MIP. I am looking at the simplest model \begin{equation} \begin{split} \min_{x,y} &\; c^Tx + f(y)\\ s.t. & \; Ax + Dy \ge ...
3
votes
2answers
58 views

Minimize $\mbox{trace}(AX)$ over $X$ with a positive semidefinite $X$

I want to minimize $\mbox{trace}(AX)$ over $X$, under the constraint that $X$ is positive semidefinite. I guess the solution should be bounded only for a positive semidefinite $A$, and it's zero, or ...
2
votes
1answer
15 views

Canonical forms which have “minimal” Gershgórin discs, do they exist?

I'm wondering about if there is some way to define, uniquely or not a canonical form which has minimal radii for Gersgórin discs. To be more specific for a given matrix $\bf A$, find $\bf C$ and $\bf ...
1
vote
1answer
38 views

Are minimizing a function and root finding the same?

What is the relationship between minimizing a function and finding a root of an equation? Are the the same? I know in both problem we have similar algorithms, such as gradient decent, or newton's ...
0
votes
1answer
427 views
0
votes
1answer
29 views

How can this be minimized?

I have the following function of $x_1$ and $x_2$: $$e(x_1,x_2)= (x_1^2+x_2^2)(a+n)+2a(-x_1+x_1x_2-x_2)+a^2$$ where $a$ and $n$ are real numbers. I want to find the values of $x_1$ and $x_2$ that ...
2
votes
2answers
100 views

How to maximize Std Dev given a range of possible values, a number of values, and a specific mean?

(I'm asking here and not stats.stackexchange because I'd like a mathematical proof of this) In this question: Prove how to maximize Standard Deviation given a certain mean $\bar{x}$ and set of values;...
1
vote
0answers
24 views

minimize quadratic form

In question Minimize Energy using Gauss-Seidel method with successive over- relaxation., when $$ E = \sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 + \lambda\sum_{i,j}\|\mathbf N_i - \mathbf N_j\|^2 = \...
1
vote
0answers
28 views

In Nonsmooth Optimization, whats the point of $x \in G$ being a local minimum results in $0 \in \delta\ f(x)+N_G(x)$

I'm reading about nonsmooth optimization and specially the book 'Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control' by Marko M. Mäkelä, Pekka Neittaanmäki. At page ...
1
vote
4answers
37 views

$\cos2\theta +\cos\theta +k = 0 $ - set of all values of $k$ for which there is a solution

The set of all values of $k$ (real), such that the equation $\cos2\theta +\cos\theta +k = 0 $ admits a solution for $\theta$ is? MY ATTEMPT: I substituted $\cos2\theta$ with $2\cos^2\theta - 1 $. On ...
6
votes
0answers
142 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
0
votes
1answer
10 views

Formulating a problem involving sets with ILP

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost ...
4
votes
1answer
49 views

How can I experiment with Lagrange multiplier in QCQP?

Suppose we want to solve following optimization problem (it is a PCA problem in this post) $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \mathbf w^\top \...
1
vote
0answers
12 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
2
votes
0answers
22 views

Finding a maximum with some constraints

I would like to maximize the term $ l_1b_1+l_2b_2+l_3b_3-2 $ such that the following conditions hold: $ 1>l_1>l_2>l_3>0 $, $ l_1,l_2,l_3 \in \mathbb{Q} $, $ b_1,b_2,b_3 \in \mathbb{N} $...
7
votes
0answers
149 views

Optimal decomposition of discrete function into sum of factorised terms

I am trying to solve the following optimisation problem. Let $x_i \in \{1, \ldots, N_i\}$ be discrete variables, and $f(x_1, \ldots , x_n)$ any real-valued function. I want to decompose $f$ into a ...
1
vote
1answer
167 views

Question about Euler's polyhedral formula in a proof of minimum distances

I am confused by a step made in a proof of the following result. Let $f_{2}^{\text{min}}(n)$ denote the maximum number of times the minimum distance can occur among n points in the plane. Then $f_{...
2
votes
1answer
1k views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
0
votes
1answer
35 views

Prove that $-4\leq5\cos\theta+3\cos(\theta+\frac{\pi}{3})+3\leq10$

Prove that $$\color\red{-4}\leq5\cos\theta+3\cos(\theta+\frac{\pi}{3})+3\leq\color\red{10}$$ My attempt:- I simplified the equation to $$\begin{align} &\;\;\phantom{=} 5\cos\theta+3\cos(\...
0
votes
0answers
25 views

Minimum norm of analytic function may not be achieved on the boundary of its domain

I need to show that the minimum modulus of an analytic function may not be achieved on the boundary of its domain. I'm stuck with this question, would appreciate if someone could help me with it. I ...
0
votes
0answers
3 views

Revenue Leakage optimization/Minimize Revenue Leakage

I'm a beginner in Operation research field.I need to do an optimization of Revenue leakage.Can you please suggest me some good reading links where I can get idea about revenue leakage optimization ...
1
vote
0answers
17 views

argmin as projection in the dual averaging algorithm

I am struggling to understand the dual averaging algorithm as presented in this paper. More precisely the update of the parameters given as $$\Pi^\psi_\chi (z,\alpha) := \operatorname{argmin}_{x \in \...
0
votes
0answers
8 views

Acyclic orientation of a mixed graph with minimization of the critical path

I already asked this question as a guest but I was not able to edit it or add comments after I registered with my e-mail address. A apologize for asking the same question again. A mixed graph is a ...
2
votes
1answer
66 views

Minimum of a function in $(0,1) \times (0,+\infty)$

I would like to minimize the function $$ (\alpha,\theta) \mapsto F(\alpha,\theta) := -\theta x^\alpha + \sum_{k=1}^N \ln(1+p_k(e^{\theta \ell_k^\alpha}-1)) $$ where $\theta \in (0,+\infty)$, $\alpha \...
0
votes
1answer
22 views

maximize 3-variable linear function [version 2.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}\frac{x_2}{6}...
0
votes
1answer
37 views

maximize 3-variable linear function [version 1.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}x_2 + \frac{...
0
votes
0answers
26 views

Sum/product of two functions of two variables are to be minimized

I have two functions $f(x,y)$ and $g(x,y)$ whose sum/product (whichever is possible) is to be minimized. The values of $x,y$ can vary in the interval $0<x,y<1$ (hence none of them can have a ...
2
votes
2answers
89 views

Maximizing a linear function over an ellipsoid

Let $A \in \mathbb{R}^{n\times n}$ be a positive definite matrix, $x \in \mathbb{R}^n$ and $c \in \mathbb{R} \setminus \{0\}$. I got to determine the maximum $$\max\{c^Ty:y\in \mathcal{E} (A,x)\}$$ ...
3
votes
3answers
62 views

Find minimum and maximum on range

$f(x,y)=x^{4}-x^{2}+y^{2}$ $B={(x,y)\in \mathbb R, x^{2}+y^{2}\leq 1 }$ I should find minimum and maximum of this function on the range B. I tried it with Lagrange Multiplier and I got these points ...
3
votes
1answer
58 views

Expected number of times a set of 10 integers (selected from 1-100) is selected before all 100 are seen

Suppose I have a set of 100 integers. I randomly choose 10 of those, make a note of which ones I selected, and repeat the process. What is the expected number of times this process must be repeated ...
2
votes
1answer
22 views

Least Squares Sensitivity to data

Let ($x_1$,$y_1$),...,($x_n$,$y_n$) be my data set. I have a function $f(x,{\bf c})$ where ${\bf c}=(c_1,...,c_m)$ is a vector of $m$ parameters. I want to fit to the data using non-linear least ...
3
votes
0answers
14 views

Skew-Symmetric Parts of Stochastic Matrices

It's easy to see that the set $\{W - W^T : W \in \mathbb{R}^{n \times n}\}$ is precisely the set of real skew-symmetric matrices. This continues to be the case if we restrict to (entry-wise) non-...
0
votes
0answers
29 views

Multiplying quaternions vs multiplying rotation matrices

It's a trivial question, but one I'm not 100% clear about. Given two matrices $$P_{\{1,2\}} = \left[ \begin{array}{cc}R & t \\ \textbf{0} & 1 \end{array}\right]$$ where $R$ is a 3x3 ...
3
votes
1answer
716 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
3
votes
3answers
79 views

A convex optimisation problem involving the Euclidean norm

Any ideas on how to approach the following optimisation problem? $$\begin{array}{ll} \text{maximize} & \|Ax\|_2^2+\|Bx\|_2^2+\|Cx\|_2^2 \\ \text{subject to} & \|x\|_2 = 1\end{array}$$
2
votes
2answers
57 views

Let $Ax$ and $Ay$ minimize distance to $b \in \mathbb{R^m}.$ Show $x-y \in \ker(A).$

Let $A$ be an $m \times n$ real matrix and $b \in \mathbb{R^m}.$ Suppose $Ax$ and $Ay$ both minimize distance to $b,$ i.e. $||Ax-b|| = ||Ay-b||.$ Prove that $x-y \in \ker(A).$ Seems like there ...
0
votes
0answers
12 views

Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
0
votes
1answer
424 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are $...
1
vote
1answer
115 views

Largest rotated ellipse inscribed in a rectangle

Let's say I have a parametrized ellipse $$x (t) = a \cos(t) \cos(r) - b \sin(t) \sin(r)$$ $$y (t) = a \cos(t) \sin(r) + b \sin(t) \cos(r)$$ Where $r$ is the rotation around the axis and $t \in [0,2\...
0
votes
0answers
12 views

solve $ \max U = [\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} ]^{{\sigma \over {\sigma - 1}}} $

The problem is $$ \eqalign{ & \max U = [\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} ]^{{\sigma \over {\sigma - 1}}} \cr & s.t.{\rm{ }}...
0
votes
1answer
32 views

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
0
votes
0answers
5 views

Invariance of weighted matrix norms in relation to Quasi-Newton methods

In Fletcher's book page 60, he talks about the invariance property of BFGS-type methods. "To get an invariant formula out of this process it is necessary to use a measure with an invariance property. ...
1
vote
0answers
15 views

Confused about solution to the piecewise constant regression model

I am confused about the solution to the following solution to fitting piecewise constants: Specifically, are we minimising the sum of squares, that is, finding the vector $\beta = (\beta_1,\beta_2, ...
2
votes
1answer
549 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
26 views

The gas cloud covering problem

I'm faced with problem described below. My goal in posting this here is having you guys lead me in the right direction. Maybe there is a scientific article that treats a similar problem? Maybe a ...
0
votes
2answers
46 views

Lagrange multipliers with trigonometric functions. Stucked figuring out x and y values.

I want to find the maximum of the function $f(x,y) = \cos^2(x) + \cos^2(y)$ with the constraint $x-y = \pi/4$. Here are my partial derivatives: $$f_x = -2\cos(x)\cdot\sin(x)$$ $$f_y = -2\cos(y)\cdot\...