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)

1
vote
1answer
55 views

Invertibility of bordered Hessian

I have an optimization problem: $max_{x \in C} f(x)$ s.t. $Ax=b$, where $x \in R^n$ and $b \in R^m$, $m \le n$, adn $C$ compact. I know that $f$ is strictly quasi-concave, and that $A$ has rank $m$ (...
1
vote
1answer
20 views

Optimization: Via manifolds point of view of Lagrange multipliers method

My basis on differential manifolds calculus and differential geometry being very superficial, I'm trying to understand this section on WP's article. I'm not being able to realize why most of the ...
0
votes
1answer
625 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 \\...
2
votes
1answer
68 views

Finding the nonnegative integer exponents that minimize a product

I've been trying to solve a problem which seems to be a multiplicative optimization problem: Given a threshold $T > 0$, and a set of integers $b_1, b_2,\dots, b_n > 0$, find integer ...
1
vote
3answers
44 views

Calculus 1 - Optimization of a Box

Can you guys help me out with it? i try to solve it but my answer is so weird that i think im wrong... Question- Someone want to build cardboard box with rectangular base. Knowing thatthe rectangle ...
8
votes
6answers
250 views

Extreme of $\cos A\cos B\cos C$ in a triangle without calculus.

If $A,B,C$ are angles of a triangle, find the extreme value of $\cos A\cos B\cos C$. I have tried using $A+B+C=\pi$, and applying all and any trig formulas, also AM-GM, but nothing helps. On this ...
0
votes
1answer
1k views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
2
votes
0answers
31 views

Sup of a linear function

Let $X$ be a banach space or simply a normed space and $C$ a convex (closed) subset of $X$. It is true that if $x \in C$ is such that $f(x)=\sup f(C)$, (in other words $x$ is a supporting point for $C$...
0
votes
0answers
28 views

Positivity of a function in two variables

Let \begin{align*} \label{} g_{\lambda}(u,v) &=K\,\sqrt{\alpha\,d_1\,u^2+\beta\,d_2\,v^2}\,\big(\lambda -\sqrt{\alpha\,d_1\,u^2+\beta\,d_2\,v^2}\big) \\ \notag &-\alpha\,u\,(\sigma_1-...
3
votes
2answers
742 views

Shortest distance between parallel line and plane

I've been doing questions regarding the shortest distance between lines/planes and points , and I've come across a question asking to find the shortest distance between a line and a plane which are ...
2
votes
0answers
41 views

Minimum of $f(x) = \frac{1}{a}\cos^4 \frac{\pi x}{2} + a \sin^4 \frac{\pi x}{2} +\sin\pi x (b\sin\pi x-c)$ for $x\in [0,1]$?

In my quantum-physics research, I am faced with the following single-variable trigonometric optimization problem that I would wish to solve analytically. Problem: Let $a,b,c, x \in \mathbb{R}$, and ...
1
vote
0answers
19 views

Upper Bound for discrete objective value

I really need your help with the following problem: Let $ N \ge 3 $ be given, then consider $$ L(N)=\max\left\lbrace \sum_{j=2}^{N-1} \frac{c_j}{j} \, \middle| \, c_j \in \mathbb{N}, \nexists 0\le d \...
0
votes
0answers
27 views

Concave optimization on closed unit ball, using penalty function

Background: I want to solve an optimization problem like $$\begin{align*}\text{minimize }&f(x)\\ \text{subject to }&\|x\| \le 1.\end{align*}$$ where $x \in \mathbb{R}^d$, $\|\cdot\|$ is the $...
-1
votes
0answers
25 views

How to find the maximum of an implicit function in matlab

I have an implicit function with 2 variables x(1) and x(2). The variable x(2) can not be written explicitly in terms of x(1). I would like to find the value of x(1) that maximizes x(2). The implicit ...
2
votes
1answer
53 views

Optimal values for $\frac{5-2f(x)-3f(y)}{5-g(x)-2g(y)}$

Let $f,g$ be nondecreasing functions from $[0,1]\rightarrow[0,1]$ with $f(0)=g(0)=0$ and $f(1)=g(1)=1$. Let $X=\{(x_0,y_0)\in[0,1]\}$ be the set of values maximizing the function $$h(x,y)=\frac{5-2f(x)...
0
votes
0answers
58 views

Throwing eggs from flooors, general case [duplicate]

The following problem and its solution is well-known: you have two eggs and you have to measure which is the first floor of a building (that has in this example 36 floors) from which if an egg is ...
1
vote
1answer
29 views

How to describe this relation

The constraint I want to place is $Mx_i-y_i<0$,that is to say when $y_i = 0$ ,then $x_i$ must equal to $0$. However the constraint is only needed when $a>b$ ($a,b$ are both the parameters). Can ...
1
vote
2answers
38 views

Force minimum of quadratic fit to certain data point

I want to fit some data $(x_i, y_i)$ with quadratic function. No problem till there. However, I want the polynomium minimum of the fitted curve to be at certain point $(x_k, y_k)$. If it is possible, ...
4
votes
1answer
111 views

Find closest point, subject to linear inequality constraints

Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is, $$\begin{array}{ll} \text{minimize} & ...
0
votes
2answers
456 views

Minimize Frobenius norm with constraints

As a follow-up on my previous question, I would like to solve the following optimization problem: $\min \Vert MA-B \Vert_F^2-x^HMy\;\;s.t.\;\;M^HM=I$ where $A$ and $B$ are $N\times L$ complex ...
1
vote
0answers
10 views

Second-Order Stochastic Dominance and Cost Minimization

I have to deal with a cost minimization problem with a cost function $c(t)$ at least twice differentiable, where $c'(t)>0$ and $c''(t)<0$. I have two density functions $f(t)$ and $g(t)$. If I ...
1
vote
0answers
54 views

How can show the following function has a global maximum?

I want to show that $$f(\alpha_1, \alpha_2, \ldots, \alpha_m)=\frac{\prod_{i=1}^{m}\alpha_i^{b_i}}{(1+\sum_{i=1}^{m}\alpha_i)^{\sum_{i=1}^{m+1}b_i}\prod_{j=1}^{2}[\sum_{i=1}^{m}\alpha_ic_i+d_j]^{a_j}}~...
2
votes
1answer
529 views

Determine the minimum and maximum values of an integral subject to end conditions

Determine the minimum and maximum values of the integral $$\int_0^1 yy'dx$$ subject to the conditions $y(0)=0$ and $y(1)=1$. There is no explicit dependence on $y$, so our Euler-Lagrange ...
2
votes
2answers
36 views

LP: add extra costs in the objective function for every variable which is not equal to $0$

I am trying to optimise an LP problem but extra costs should be added if a variable is larger than $0$. For example, if we have the following objective function: $$\text{minimize} \qquad 2X_1 + 3X_2 ...
6
votes
2answers
225 views

Constant such that $\max\left(\frac{5}{5-3c},\frac{5b}{5-3d}\right)\geq k\cdot\frac{2+3b}{5-c-2d}$

What is the greatest constant $k>0$ such that $$\max\left(\frac{5}{5-3c},\frac{5b}{5-3d}\right)\geq k\cdot\frac{2+3b}{5-c-2d}$$ for all $0\leq b\leq 1$ and $0\leq c\leq d\leq 1$? The right-hand ...
2
votes
0answers
39 views

Pseudometric without triangle inequality

I'm working on an optimization problem where I aim to minimize the total euclidean distance of the edges of a graph drawn on a fixed-size grid. For convenience, I actually use the maximum of $0$ and ...
0
votes
0answers
9 views

optimisation with workers and jobs, constrained

I would like to solve this problem: Imagine we have i=1...W workers with ability $a_{ij}$ to perform J jobs, $t_{ij}$ is the time worker i spends on job j. We want to maximise output $\sum f_j(t_{ij}*...
2
votes
1answer
49 views

Maximal values of $k(1-F(k))$ and $\frac{k(1-F(k))}{2-F(k)}$

Given a continuous distribution over $(0,1)$ with cumulative distribution function $F$. Let $k_1\in(0,1)$ be the value maximizing $g_1(k)=k(1-F(k))$ and $k_2\in(0,1)$ be the value maximizing $g_2(k)...
3
votes
1answer
49 views

Maximizing $\frac{x(1-f(x))}{3-f(x)}$

Let $f:[0,1]\rightarrow[0,1]$ be a nondecreasing function such that $f(0)=0$ and $f(1)=1$. Let $x_1\in[0,1]$ be the value maximizing $x(1-f(x))$. Let $x_2\in[0,1]$ be the value maximizing $\frac{x(...
1
vote
1answer
32 views

How to prove the equivalence of these optimization problems?

I am reading some lecture notes and in one procedure step it is stated that: $$\min_{\mathbf{x}}\; \langle \mathbf{H}, \mathbf{Rx-Z}\rangle + \frac{\lambda}{2} \|\mathbf{Rx-Z}\|_F^2$$ is equivalent to ...
3
votes
0answers
21 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-...
1
vote
1answer
80 views

Maximizing $\|APBPA\|_2$ subject to $0 \leq P \leq I$

Given positive semidefinite matrices $A,B$, how to compute $$\max_{0 \leq P \leq I}\|APBPA\|$$ where the norm is the spectral norm, i.e., the largest singular value?
0
votes
3answers
267 views

Finding a good difficult example function to minimize

I am comparing some code for non-linear function minimization in multiple variables, like quasi-Newton methods etc. I am looking for a nice function to use as a test case. So far I have been using $f(...
1
vote
3answers
78 views

Binary integer variables in linear programming

Could someone please explain the concept of switch variables (binary integer decision variables) in linear programming? This example has two alternative constraints $$\begin{array}{ll} \text{...
1
vote
0answers
21 views

proximal operator to sum of norm functions

The proximal operator is defined by: $$ prox_{\tau f} = \arg\min_u \frac 1 {2\tau} \|u-u^k\|^2 + f(u) $$ I know the solution when $$ f(u) = \|Au+b\|_1 $$ But I wonder how to derive the solution of ...
0
votes
1answer
208 views

Puzzle question finding Calvin

How to solve this problem. I have reckoned that I need to take as optimization problem finding minimum value for waiting time. Any suggestions? Calvin has to cross several signals when he walks from ...
0
votes
0answers
15 views

Solve $\max_X \mathrm{sum}(AXB \geq \gamma)$, with $X$ being a permutation matrix

I have a problem to find the best permutation matrix $X \in \{0,1\}^{n \times n}$, which would maximizes the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
1
vote
0answers
19 views

Find optimum diagonal matrix $D$ to maximize $ADB$ above a threshold $\gamma$

I have a problem to find the optimum diagonal matrix $D$, which would maximizes the number of elements in $ADB$ which are above a certain positive number $\gamma$. In other words, the problem is ...
1
vote
0answers
35 views

Gradient of a function involving maxima

How do I find the gradient of a function like $f(\vec{v})$ where $$ f(\vec{v}) = \max_{\vec{t}\geq 0} g(\vec{v},\vec{t})$$ For example, I have a function defined as follows: \begin{align} f(\vec{v}) ...
2
votes
0answers
23 views

Does converting an inequality constraint to an equality one have any major impact on an optimization solver?

In an optimization problem, I have an inequality constraint, say $\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}g(x)\le 0 \end{array}$ The function $g(x)$ in general is unknown. So, numerical ...
1
vote
1answer
24 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 ...
1
vote
0answers
12 views

For each of the functions, how to calculate a subgradient of the function at a given $x$.

We have $$f(x)=1/2||Ax-b||_2+||x||_2$$ where $A\in \mathbb{R}^{m\times n}$ and $x\in \mathbb R^n$ and $$f(x)=\inf_y||Ay-x||_\infty$$ where $A\in \mathbb R^{m\times n}$ and $x\in \mathbb R^n $
1
vote
1answer
122 views

Efficient MIP reformulation for binary integer problem

Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$ I want to reformulate this into an efficient mixed-integer programming (MIP) problem. ...
3
votes
0answers
276 views

Bender's Decomposition for Mixed Integer Programs

Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1). $LP_1$ has the form $\...
0
votes
0answers
43 views

Coefficient variation in Objective Function in Mixed Integer programming

Assume we have the following Mixed Integer programming. MIP 1) $Z1=$ Max $Ax+By$ s.t $Cx+Dy<=E$ $x>=0$ and $y: {0,1}$ Now, assume we have the same MIP, and I just converted A to A' MIP2)...
0
votes
1answer
79 views

Checking whether a solution to MIP is optimal

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I \...
0
votes
0answers
18 views

Find permutation matrix $X \in \{0,1\}^{N \times N}$ in order to make $XAX \geq_c B$

I need to solve a problem to find out the best permutation matrix $X \in \{0,1\}^{N \times N}$ which would maximize the number of elements in matrix $XAX$ which are above (component-wise) matrix $B$ ...
1
vote
1answer
39 views

Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system \begin{equation} y = A_1 x_1 + A_2 x_2 \end{equation} subject to the linear constrains \begin{equation} C_1 x_1 + C_2 x_2 \leq d \end{equation} I am looking ...
1
vote
0answers
34 views

Maximizing the trace of a complex matrix

Let's say I have the following maximization problem: $max_U{tr(AU)}$ where $A\in\mathbb{C}$ and $UU^\dagger=1$ I know that for $A\in\mathbb{R}$ and $UU^T=1$ the solution is: $U=XZ^T$ where $X$ ...
6
votes
1answer
644 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...